1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Factoring large N into prime factors

  1. Mar 15, 2012 #1
    Hi, I am writing up a project based on an algorithm for factoring large numbers, I have reached seemingly simple point where I am stuck, I wonder if anyone can help me?

    I am trying to factor a large N such that N=pq for unknown primes p and q, I have described a method to find a value for (p-1)(q-1) from N and now have the problem of recovering p and q.

    So N is given and (p-1)(q-1) is given, how do I carry on? Thanks
  2. jcsd
  3. Mar 15, 2012 #2
  4. Mar 15, 2012 #3
    thanks, that's perfect.

    The way in which i found (p-1)(q-1) is to take a set of sequences of powers of x mod N for x=1,2,...,N-1 and work out their periods, each period turns out to be a divisor of (p-1)(q-1), if a large enough number of divisors is taken, then the value of (p-1)(q-1) can be predicted with high probability. That's basically all I've got, if anyone knows the specific theorem I am exploiting here it would be greatly appreciated as I should include it in my work, I know it's Euler but I'm having trouble finding a specific name so I can reference it and perhaps find a proof.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook