To make a concrete suggestion that might help, Julia might benefit from One Line Factor and Lehman's algorithm (misspelled in my previous post). There are C implementations here:
https://github.com/wbhart/flint2/blob/trunk/ulong_extras/factor_one_line.c https://github.com/wbhart/flint2/blob/trunk/ulong_extras/factor_lehman.c These are efficient up to around numbers of 44 bits or so. They have heuristic complexity O(n^1/3). If you want to go up to 64 bits, you probably want SQUFOF with a fallback to Lehmer. That gives you at least heuristic complexity O(n^1/4): https://github.com/wbhart/flint2/blob/trunk/ulong_extras/factor_SQUFOF.c Feel free to derive BSD or MIT licensed versions of these for Julia. 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). >> >
