# euler_phi() computing time

Hello! I have a question regarding the euler_phi() function. Computing euler_phi(n) for a very large number (20+ digits) is very fast. However I'm not allowed to use this function => university. I tried computing it with pollard rho factorization (p-1)(q-1) but it takes ages (not finished yet). I looked up the src code for euler_phi() and I saw "len([i for i in range(n) if gcd(n,i) == 1])" which doesnt work in my code because of range() overflow, using srange() also takes ages. How does the sage euler_phi() work? Is some kind of binary magic involved? Is there a way to compute phi(n) for a 20+ digit number with sage in reasonable time? Thx!

edit retag close merge delete

Sort by » oldest newest most voted

This looks like a homework, so try to implement the own fair version of the following code, based on the formula $$\varphi(n)=n\prod_{p\text{ prime dividing }n}\left(1-\frac 1p\right)\ .$$

sage: def my_euler_phi(n):
....:     return ZZ( n*prod( [ 1 - 1/p for p in ZZ(n).prime_divisors() ] ) )


Test of the two-liner:

sage: euler_phi( 10**27+864291 )
857068852255018256626311168

sage: my_euler_phi( 10**27+864291 )
857068852255018256626311168


Note: The code for a function can be simply inspected in the sage interpreter via ??, in our case for instance ??euler_phi or euler_phi?? . In our case one finds immediately the line with return ZZ(pari(n).eulerphi()) ...

Note: The formula is based on the isomorphism $\mathbb Z/(mn) \cong (\mathbb Z/m)\times (\mathbb Z/n)$ for relatively prime integers $m,n$. This delivers the (so called restricted, or arithmetic) multiplicativity of $\varphi$, in this case $\varphi(mn)=\varphi(m)\varphi(n)$. So it is enough to prove the formula for prime powers...

more