From: "Dann Corbit" Subject: Re: Factoring n = p*q, product of 2 primes Date: Tue, 5 Oct 1999 14:54:00 -0700 Newsgroups: sci.math Keywords: examples using MIRACL Lynn Killingbeck wrote in message news:37FA6BEB.6D7@phoenix.net... > S. Morgan wrote: > > > > I'm a little new to this, so please help. > > > > Problem: Given a number "n", the product of 2 primes, find the factors > > (primes). > > > > What is the popular name of this problem? What are some good reference > > books or web sites? Here is the best prime number site I know of: http://www.utm.edu/research/primes/ > > For numerical calculations of the solution, what is the most efficient > > algorithm (that is, the least number of multiplies or divides)? I have > > written an algorithm to solve this and I want to compare my method to > > "the experts". Thanks. I thought I had come up with something clever once. I multiplied all the primes between 2 and 65535 together, and did a gcd with a fast modulus (since I only needed the remainder I could throw away the quotient part). It turns out it was not even original. Someone else had written the procedure as the exercicse for a book. It would be worth checking to see if someone has already done it. > > S. O. Morgan > > Have you tried your algorithm on factoring a moderate size number such > as (picking a couple of prime number out of a classic book) > (2^31-1)*(2^32+5)? This takes but a fraction of a second with the factoring tools from MIRACL: C:\tmp>factor 18446744090889420795 first trying brute force division by small primes PRIME FACTOR 3 PRIME FACTOR 3 PRIME FACTOR 3 PRIME FACTOR 3 PRIME FACTOR 5 PRIME FACTOR 17 PRIME FACTOR 47 PRIME FACTOR 257 now trying 1000 iterations of brent's method PRIME FACTOR 65537 PRIME FACTOR 3384529 > That number fits in the math coprocessor of the Intel family of chips, > so you don't even need high-precision arithmetic routines, if you are > careful with the design. > > A ready reference is Knuth, 'The Art of Computer Programming', vol. 2, > 'Seminumerical Algorithms', section 4.5.4, 'Factoring Into Primes'. > > After you factor the above example, see how your algorithms fares with > (2^64-59), which is prime. See Table 2, 'Useful Prime Numbers', of the > above TAOCP. Any good factoring program should test for prime *first* since a test for primeness is so much easier than factoring: C:\tmp>factor 18446744073709551557 this number is prime! > I'm not an expert by any means (if I need something factored, I just run > a program I downloaded a long time back - ususally works for a couple of > hunderd decimal digits, but sometimes gives up), but this reference > should get you headed in a useful direction. By the way, be careful that > the bookkeeping does not dominate the number of multiplies and divides! > For very small numbers, the fastest way is a brute-force table look-up. I would suggest downloading the MIRACL package by Michael Scott. ftp://ftp.compapp.dcu.ie/pub/crypto/ If the new method is of value, it might be worth trying something a bit more challenging. This takes less than one second: D:\MIRACL>factor 111111111111111111111111111111111111111111111111111111123 first trying brute force division by small primes PRIME FACTOR 3 PRIME FACTOR 89 now trying 1000 iterations of brent's method now trying william's (p+1) method phase 1 - trying all primes less than 10000 phase 2 - trying last prime less than 1000000 PRIME FACTOR 2871856525523 PRIME FACTOR 144905039602014436839144472051006730679203 This takes about 30 seconds: D:\MIRACL>factor 1111111111111111111111111111111111111111111111111111111237777777777777777777 777777779 first trying brute force division by small primes PRIME FACTOR 3 now trying 1000 iterations of brent's method PRIME FACTOR 1681033 now trying william's (p+1) method phase 1 - trying all primes less than 10000 phase 2 - trying last prime less than 1000000 now trying pollard's (p-1) method phase 1 - trying all primes less than 100000 phase 2 - trying last prime less than 5000000 now trying lenstra's method using 10 curves curve 1 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 PRIME FACTOR 2555732279 now trying 80 more curves curve 1 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 2 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 3 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 4 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 5 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 6 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 PRIME FACTOR 2332316211478831 PRIME FACTOR 36962148508570020415017140465324607987029748804137329 This takes about one minute: D:\MIRACL>factor 1111111111111111111111111111111111111111111111111111111237777777777777777777 77777777988812290487124 first trying brute force division by small primes PRIME FACTOR 2 PRIME FACTOR 2 PRIME FACTOR 71 PRIME FACTOR 1783 PRIME FACTOR 4079 PRIME FACTOR 4327 now trying 1000 iterations of brent's method PRIME FACTOR 2546311381 now trying william's (p+1) method phase 1 - trying all primes less than 10000 phase 2 - trying last prime less than 1000000 PRIME FACTOR 893580235290023 now trying pollard's (p-1) method phase 1 - trying all primes less than 100000 phase 2 - trying last prime less than 5000000 PRIME FACTOR 5146074383 now trying lenstra's method using 10 curves curve 1 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 2 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 3 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 4 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 5 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 6 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 7 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 8 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 9 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 curve 10 phase 1 - trying all primes less than 20000 phase 2 - trying last prime less than 2000000 finally - the multiple polynomial quadratic sieve - with large prime (*) using multiplier k= 1 and 1785 small primes as factor base working... 1738 trying... PRIME FACTOR 32440304142384444843369351719 PRIME FACTOR 32729635203273072803399 > You might find more in a newsgroup such as sci.crypto, since factoring > large numbers is the basic idea behind many (most? all?) public-key > cryptography. RSA is the only one I know that uses it. They do talk a lot about factoring over there. -- C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html "The C-FAQ Book" ISBN 0-201-84519-9 C.A.P. Newsgroup http://www.dejanews.com/~c_a_p C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm