mersenneforum.org I'm not a mathematician but this is really interesting!
 Register FAQ Search Today's Posts Mark Forums Read

 2012-10-30, 22:25 #1 Sam Kennedy     Oct 2012 2×41 Posts I'm not a mathematician but this is really interesting! Lately I've been obsessed with factoring semi-primes. The fastest algorithm I've managed to implement so far is Pollard's Rho algorithm. I'm guessing the next step is either ECM or the Quadratic Sieve, I know there are variations such as Pollard's p-1 and William's p+1, but I don't think they are that much faster than the Rho algorithm (Please correct me if I'm wrong though!) My problem is that I don't know a whole lot of number theory, so I quickly become lost when reading explanations of Lenstra's ECM or the Quadratic Sieve. Are there any good explanations of either factoring method, for someone who has a good knowledge of programming, but very little knowledge of mathematics and number theory? Are there any other interesting and/or fast factoring methods for large semi-primes? At the minute my algorithm can factor a 128 bit semi prime in just over an hour and a half.
2012-10-31, 00:18   #2
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by Sam Kennedy Are there any other interesting and/or fast factoring methods for large semi-primes?
No faster than other numbers of similar size. Semiprimes with both prime factors of roughly equal size are the hardest sort of numbers to factor for their size.

Quote:
 Originally Posted by Sam Kennedy I'm guessing the next step is either ECM or the Quadratic Sieve
ECM is good if the prime factors are of unequal size: one small and the other much larger (say, the large one is bigger than the cube of the small one). The quadratic sieve (or variants like MPQS and SIQS) is better when the two are of comparable size.

The quadratic sieve becomes unusable when the number to be factored gets bigger than about 10^110 or 10^120. ECM becomes unusable when the smaller prime factor is bigger than 10^45 or so.

(In a pinch you could push both further. In practice the NFS takes over for the QS variants around 10^100 or 10^105.)

Quote:
 Originally Posted by Sam Kennedy Are there any good explanations of either factoring method, for someone who has a good knowledge of programming, but very little knowledge of mathematics and number theory?
I don't think it's possible without a good understanding of number theory! Crandall & Pomerance is a good text if you're willing to learn (and it does teach much of the basics).

 2012-10-31, 00:21 #3 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 2×3×1,669 Posts Maybe look at this: http://en.wikipedia.org/wiki/Ellipti...ethod#See_also
2012-10-31, 00:53   #4
Sam Kennedy

Oct 2012

10100102 Posts

Quote:
 Originally Posted by CRGreathouse I don't think it's possible without a good understanding of number theory! Crandall & Pomerance is a good text if you're willing to learn (and it does teach much of the basics).
Is the book "Prime Numbers - A Computational Perspective"?

 2012-10-31, 02:05 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100101011000112 Posts That's the one. I've got mine from Amazon for $30 almost unused. There's one right now for$42. Try http://www.bestwebbuys.com/books/ ; if you wait for a few days, a deal might come up. ISBN is 0387252827 Last fiddled with by Batalov on 2012-10-31 at 02:07
 2012-10-31, 09:06 #6 akruppa     "Nancy" Aug 2002 Alexandria 246710 Posts A very accessible introduction to the Quadratic Sieve and NFS (although for the latter you can't avoid a bit of theory of algebraic number fields) is Pomerance, A Tale of Two Sieves. It does not give many technical details, but outlines the general strategy of the algorithms in broad strokes, and makes a useful foundation for reading more technical texts afterwards.
 2012-10-31, 16:18 #7 pbewig   Feb 2011 St Louis, MO 32 Posts Like you, I am a programmer, not a mathematician, and interested in prime numbers and integer factorization. My blog, Programming Praxis, includes descriptions and implementations of several prime-number algorithms; in the menu bar, click on Exercises, then Themes, and select Prime Numbers. Feel free to contact me off line if you wish.
2012-10-31, 16:37   #8
Sam Kennedy

Oct 2012

8210 Posts

Quote:
 Originally Posted by pbewig Like you, I am a programmer, not a mathematician, and interested in prime numbers and integer factorization. My blog, Programming Praxis, includes descriptions and implementations of several prime-number algorithms; in the menu bar, click on Exercises, then Themes, and select Prime Numbers. Feel free to contact me off line if you wish.
Phil, don't you remember me? Haha :)

I've been reading your exercises on elliptic curve factorisation, but I'm still not 100% sure what I'm doing, I'm going to read up on elliptic curves so I have a better idea of what is actually going on.

 2012-10-31, 17:12 #9 bsquared     "Ben" Feb 2007 2×1,789 Posts I also like Factorization and Primality Testing by David M. Bressoud. Perhaps a smidge more accessible then C&P as far as algorithm implementation goes. (ISBN-10: 0387970401)
2012-10-31, 17:49   #10
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

25·5·37 Posts

Quote:
 Originally Posted by bsquared I also like Factorization and Primality Testing by David M. Bressoud. Perhaps a smidge more accessible then C&P as far as algorithm implementation goes. (ISBN-10: 0387970401)
What algorithms does this cover? I assume it covers ecm. Is NFS too new?

2012-10-31, 18:48   #11
bsquared

"Ben"
Feb 2007

2·1,789 Posts

Quote:
 Originally Posted by henryzz What algorithms does this cover? I assume it covers ecm. Is NFS too new?
NFS is not too new for the book, but is beyond the scope so it isn't covered. It has nuts-n'-bolts type explanations of most of the other algorithms (fermat, rho, p-1, p+1, ecm, qs) including pseudo-code for several (rho, p-1, p+1, ecm). It mentions possible improvements in several cases and provides references, but doesn't go into much detail (e.g. Brent's improvment, stage 2 methods, MPQS and large primes). The explanations and pseudo-code allow one to see how an algorithm works from a programming perspective and I was able to get initial versions up and working for p-1, p+1, ecm, and QS because of this (there are also descriptions of several useful tools like the Legendre symbol, a gaussian eliminination solver, moduler exponentiation, etc.). Optimizations beyond the very basics would require more than this book has to offer though. C&P would be the next step, IMO.

 Similar Threads Thread Thread Starter Forum Replies Last Post davieddy Lounge 0 2011-04-28 14:05 cheesehead Lounge 20 2009-06-05 20:24 jasonp Math 1 2007-11-14 22:07 R.D. Silverman NFSNET Discussion 0 2007-10-11 14:54 clowns789 Hardware 1 2003-12-20 12:36

All times are UTC. The time now is 07:02.

Sun Oct 24 07:02:11 UTC 2021 up 93 days, 1:31, 0 users, load averages: 1.59, 1.52, 1.58