Factor is terribly slow about primes.jl HOT 12 OPEN

Currently, factor(big"2"^128 + 1) also takes a very long time. But we can do better!

As an experiment, I implemented the Continued Fraction Factorization Method (CFRAC) in Julia, which is able to factorize 2^128 + 1 in just 4.5 seconds. Some optimizations may be possible.

The code is available at:
https://github.com/trizen/julia-scripts/blob/master/Math/continued_fraction_factorization_method.jl

It works best for numbers with 30-50 digits in size that do not have small factors.

Additionally, a very simple implementation of the Elliptic Curve Factorization Method (ECM) in Julia:
https://github.com/trizen/julia-scripts/blob/master/Math/elliptic-curve_factorization_method.jl

It can find very quickly factors of about 10-17 digits in size, without strongly depending on the size of n.
For example, it takes just 1.5 seconds to find a factor of 2^128 + 1.

Feel free to use both methods inside the Primes module if you want.

More special-purpose factorization algorithms are described at:
https://trizenx.blogspot.com/2019/08/special-purpose-factorization-algorithms.html

from primes.jl.

@trizen would you be willing to re-license ecm to an MIT license?

I removed any license restrictions. Life is too short to care about licenses and arbitrary restrictions. :)

from primes.jl.

Can you confirm I haven't done anything especially stupid here? #104

Looks good to me.

Also, how hard do you think it would be to add the second stage of the algorithm? According to https://www.rieselprime.de/ziki/Elliptic_curve_method it can significantly increase the success chance.

Should be doable, although I haven't tried implementing the second stage. Maybe @danaj can provide some help here.

See also: https://github.com/danaj/Math-Prime-Util-GMP/blob/master/ecm.c#L487

from primes.jl.

#50

this is pull request.

from primes.jl.

number = reduce(*, 1, Primes.PRIMES)

Did you mean number = reduce(*, big(1), Primes.PRIMES)?
Note that I have an optimized version of the pollardfactors! for BigInt which I just need to review before submitting a PR.

from primes.jl.

@rfourquet that's what I did on my machine, but I forgo to change it on GitHub, where I was preparing this issue. This number however avoids calling Pollard Rho at all.

from primes.jl.

I think we can close this now that #93 is merged. Using either of the strategies mentioned by @trizen would probably be good, but at this point, the initial issue from this PR gets solved in 0.45 seconds and other numbers with a few big factors are still somewhat reasonable.

from primes.jl.

@trizen would you be willing to re-license ecm to an MIT license? I would be interested in adding them to Primes.jl for factoring numbers.

from primes.jl.

Can you confirm I haven't done anything especially stupid here? #104

from primes.jl.

Also, how hard do you think it would be to add the second stage of the algorithm? According to https://www.rieselprime.de/ziki/Elliptic_curve_method it can significantly increase the success chance.

from primes.jl.

Regarding the second stage of the ECM, the SymPy library has very nice and readable code for it: https://github.com/sympy/sympy/blob/master/sympy/ntheory/ecm.py

Just for fun, I also made two translations of the Python code (a slightly older version), which can also be used for reference:

• Perl: https://github.com/trizen/perl-scripts/blob/master/Math/elliptic-curve_factorization_method_with_B2_stage.pl
• Sidef: https://github.com/trizen/sidef-scripts/blob/master/Math/elliptic-curve_factorization_method_with_B2_stage.sf

from primes.jl.

I got most of the way time with a Julia implementation in #104

from primes.jl.