I'm not sure what you mean by "big". Without ECM or QS you won't efficiently factor numbers bigger than about 20 digits (except in random cases where you happen to get lucky).
Bill. On 16 March 2015 at 07:42, Hans W Borchers <[email protected]> wrote: > 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). >> >
