Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler's Totient Function

  1. Mar 5, 2012 #1
    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?

  2. jcsd
  3. Mar 6, 2012 #2
    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.
  4. Mar 6, 2012 #3

    I like Serena

    User Avatar
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook