Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   Linear & Abstract Algebra (http://www.physicsforums.com/forumdisplay.php?f=75)
-   -   Euler's Totient Function (http://www.physicsforums.com/showthread.php?t=584239)

squire636 Mar5-12 11:46 PM

Euler's Totient Function
 
I understand that for m = pq where p and q are prime numbers, [itex]\Phi[/itex](m) = (p-1)(q-1). Is there any way that, knowing the numerical value of m and [itex]\Phi[/itex](m), we could deduce p and q, the prime factors of m?

Thanks!

squire636 Mar6-12 12:01 AM

Re: Euler's Totient Function
 
Specifically, I know that a huge number m is the product of two primes and I know [itex]\Phi[/itex](m)...but I can't figure out which primes those are and I don't want to figure it out by brute force.

I like Serena Mar6-12 01:05 AM

Re: Euler's Totient Function
 
If you know m=pq and Φ=(p-1)(q-1), then define S=m-Φ+1=p+q.

So you have the product m and the sum S.
That means p and q are the solutions of the quadratic x2 - Sx + m = 0.


All times are GMT -5. The time now is 08:20 AM.

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums