I'm not a mathematician but this is really interesting!

[Sam Kennedy]

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.

[CRGreathouse]

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.

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.)

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).

[Uncwilly]

Maybe look at this:
http://en.wikipedia.org/wiki/Ellipti...ethod#See_also

[Sam Kennedy]

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"?

[Batalov]

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

[akruppa]

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.

[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.

[Sam Kennedy]

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.

[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)

[henryzz]

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?

[bsquared]

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.