Revision history [back]

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!