Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   General Math (http://www.physicsforums.com/forumdisplay.php?f=73)
-   -   Factoring large N into prime factors (http://www.physicsforums.com/showthread.php?t=587366)

bert2612 Mar15-12 04:36 PM

factoring large N into prime factors
 
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

dodo Mar15-12 04:58 PM

Re: factoring large N into prime factors
 
Hi, Bert,
see this thread:
http://www.physicsforums.com/showthread.php?t=584239

It would be interesting if you can comment on your method, as finding phi(n) for large semiprimes is hard.

bert2612 Mar15-12 05:16 PM

Re: factoring large N into prime factors
 
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.


All times are GMT -5. The time now is 02:01 AM.

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