3

I need to get phi-function (Euler's) of some randomly generated 128-bit numbers. I tried to use this code below but computer is just thinking too much.

import fractions

def phi(n):
    amount = 0        
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1
    return amount

Is there something faster?

J. Doe
  • 229
  • 3
  • 15
  • Possible duplicate of [Computing Eulers Totient Function](https://stackoverflow.com/questions/18114138/computing-eulers-totient-function) – Alfabravo Sep 10 '18 at 17:17
  • @Alfabravo The code here is exactly the same as the code in the accepted answer there. Which of the other answers do you think answers this question? – Patrick Haugh Sep 10 '18 at 17:20
  • Related: [Super speedy totient function](https://codegolf.stackexchange.com/q/26739/11006) – r3mainer Sep 10 '18 at 17:32
  • @Alfabravo, none of the suggested answers in the question helped. Actually, the code I used is the same as in the mostly voted answer of that question. – J. Doe Sep 10 '18 at 17:35
  • Geeze, all of the answers there are absurdly inefficient. None of them are appropriate for 128-bit numbers. The one that comes closest to being a reasonable choice for 128-bit numbers is hampered by a stopping condition that stops at the square root of the original `n` value instead of the working `n` value, and anyway, trial division stops being a good choice well before 128 bits. – user2357112 Sep 10 '18 at 17:35
  • It is quite the same. It has no accepted question AND many of those are not as efficient as desired. Still, it is the same question, isn't it? I'd bounty it up to get a better answer. Else, the code could be reviewed in [codereview](https://codereview.stackexchange.com/). – Alfabravo Sep 10 '18 at 18:14

1 Answers1

12

For 128-bit numbers, you're going to want to efficiently compute the prime factorization of n, then use

totient = n
for factor in prime_factors(n):
    totient -= totient // factor

The hard part is the factorization. For 128-bit numbers, simple trial division is going to be horribly inefficient. Something like elliptic curve factorization or a quadratic sieve would be better, but writing those by hand is hard. It's probably better to use a library.

The best Python implementation of a large-number factorization algorithm I've found is, believe it or not, this answer by primo on codegolf.stackexchange.com. It's a multiple-polynomial quadratic sieve.

primefac (Python 2) and labmath (Python 3) incorporate a quadratic sieve, but it's based on an old, somewhat slow and buggy version of the Code Golf answer. If you want the fixed version, you'll want to go to the Code Golf answer. (Also, be aware that labmath.factorint defaults to not using the mpqs implementation.) labmath and primefac also include elliptic curve factorization, and a few other algorithms that are less likely to be useful for this input size.

Aside from that, there's sympy.ntheory.factorint, but it had problems with large factors in my tests, and it only has trial division, pollard rho, and pollard p-1 factorization.

Anyway, use one of those existing factorization options, or implement your own, or whatever, and then build your totient function on top of that. For example, using primefac:

# primefac.factorint(n) returns a factor:multiplicity dict
from primefac import factorint

def totient(n):
    totient = n
    for factor in factorint(n):
        totient -= totient // factor
    return totient
user2357112
  • 260,549
  • 28
  • 431
  • 505