Thanks, I know. When I need to factor large numbers I can use specialized software, and for mid-sized problems I can easily live with PARI/GP (or perhaps Flint in the future). And I can live with probabilistic prime testing.
All that is not my problem. I would like to have factor() in Julia work as fast as in R or Python, and certainly not try to factor big integers with trial division. Elliptic curve or quadratic sieve methods may come later. On Monday, March 16, 2015 at 7:14:00 AM UTC+1, Bill Hart wrote: > > Factoring large integers is an open research problem. The issue is > definitely nothing to do with Julia's handling of bignums, or its use of > GMP (there is no competitive factoring algorithm in GMP). > > Fixing that problem properly is on the order of about 120,000 lines of C > code, if you want to be truly up-to-date. > > Here is a list of algorithms you need to factor big numbers fast: > > trial division > perfect power testing > lehmer > pollard rho > SQUFOF > p-1 > p+1 > elliptic curve method > quadratic sieve (self initialising, multiple polynomial, small, large and > double large prime variants) > general number field sieve (active open research area) > > then you need to be able to check for primality reliably to certify that > you have actually fully factored your numbers, for which you will want > > a lookup table for small primes > trial division > strong probable prime test > Lucas test > Baillie-PSW > Miller-Rabin > Pocklington-Lehmer p-1 test > Morrison's p+1 test (+ Brillhart, Lehmer, Selfridge improvements) > APR-CL or ECPP > > You might like to look at the msieve library and the GMP-ECM library. That > will take most of the burden off you. If you want to factor numbers bigger > than about 100 decimal digits, you need something like CADO-NFS. If you > want to factor numbers bigger than 200 digits you need a miracle. > > Hopefully flint will also have something relatively competitive by the end > of the summer, though it isn't specialised just on those problems. We are > still missing APR-CL, qsieve, ECM which we plan to add over the next few > months to a year, and we don't have any plans for a general number field > sieve at this point. > > Note that the primality testing in GMP is for probable prime testing only. > It sometimes (exceedingly rarely) says composite numbers are prime. It does > no primality proving (i.e. it has no APR-CL or ECPP). >
