20121030, 22:25  #1 
Oct 2012
2×41 Posts 
I'm not a mathematician but this is really interesting!
Lately I've been obsessed with factoring semiprimes. 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 p1 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 semiprimes? At the minute my algorithm can factor a 128 bit semi prime in just over an hour and a half. 
20121031, 00:18  #2  
Aug 2006
3·1,993 Posts 
Quote:
Quote:
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.) 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). 

20121031, 00:21  #3 
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 
20121031, 00:53  #4 
Oct 2012
1010010_{2} Posts 

20121031, 02:05  #5 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010101100011_{2} 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 20121031 at 02:07 
20121031, 09:06  #6 
"Nancy"
Aug 2002
Alexandria
2467_{10} 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.

20121031, 16:18  #7 
Feb 2011
St Louis, MO
3^{2} 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 primenumber algorithms; in the menu bar, click on Exercises, then Themes, and select Prime Numbers. Feel free to contact me off line if you wish.

20121031, 16:37  #8  
Oct 2012
82_{10} Posts 
Quote:
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. 

20121031, 17:12  #9 
"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.
(ISBN10: 0387970401) 
20121031, 17:49  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{5}·5·37 Posts 

20121031, 18:48  #11 
"Ben"
Feb 2007
2·1,789 Posts 
NFS is not too new for the book, but is beyond the scope so it isn't covered. It has nutsn'bolts type explanations of most of the other algorithms (fermat, rho, p1, p+1, ecm, qs) including pseudocode for several (rho, p1, 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 pseudocode allow one to see how an algorithm works from a programming perspective and I was able to get initial versions up and working for p1, 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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lapsed Mathematician  davieddy  Lounge  0  20110428 14:05 
LowStress Job with High Potential? Mathematician  cheesehead  Lounge  20  20090605 20:24 
A Mathematician's Apology  jasonp  Math  1  20071114 22:07 
Interesting Question  R.D. Silverman  NFSNET Discussion  0  20071011 14:54 
Something Interesting  clowns789  Hardware  1  20031220 12:36 