I should mention that if you want to use the factor_one_line.c file unmodified under a BSD or MIT license, I'd have to seek permission from the other copyright holder (who is unlikely to withhold permission). Reimplementing them in Julia is definitely fine.
On 16 March 2015 at 07:56, Bill Hart <[email protected]> wrote: > 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). >>> >> >
