mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-10-30, 22:25   #1
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

2×41 Posts
Default 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.
Sam Kennedy is offline   Reply With Quote
Old 2012-10-31, 00:18   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by Sam Kennedy View Post
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 View Post
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 View Post
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).
CRGreathouse is offline   Reply With Quote
Old 2012-10-31, 00:21   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×3×1,669 Posts
Default

Maybe look at this:
http://en.wikipedia.org/wiki/Ellipti...ethod#See_also
Uncwilly is online now   Reply With Quote
Old 2012-10-31, 00:53   #4
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

10100102 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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"?
Sam Kennedy is offline   Reply With Quote
Old 2012-10-31, 02:05   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101011000112 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2012-10-31, 09:06   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-10-31, 16:18   #7
pbewig
 
Feb 2011
St Louis, MO

32 Posts
Default

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.
pbewig is offline   Reply With Quote
Old 2012-10-31, 16:37   #8
Sam Kennedy
 
Sam Kennedy's Avatar
 
Oct 2012

8210 Posts
Default

Quote:
Originally Posted by pbewig View Post
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.
Sam Kennedy is offline   Reply With Quote
Old 2012-10-31, 17:12   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

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)
bsquared is offline   Reply With Quote
Old 2012-10-31, 17:49   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

25·5·37 Posts
Default

Quote:
Originally Posted by bsquared View Post
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?
henryzz is online now   Reply With Quote
Old 2012-10-31, 18:48   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lapsed Mathematician davieddy Lounge 0 2011-04-28 14:05
Low-Stress Job with High Potential? Mathematician cheesehead Lounge 20 2009-06-05 20:24
A Mathematician's Apology jasonp Math 1 2007-11-14 22:07
Interesting Question R.D. Silverman NFSNET Discussion 0 2007-10-11 14:54
Something Interesting 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.