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?
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