Ask Your Question
0

euler_phi() computing time

asked 2017-10-23 07:33:49 -0600

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-10-23 15:19:23 -0600

dan_fulea gravatar image

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

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2017-10-23 07:33:49 -0600

Seen: 41 times

Last updated: Oct 23