[GAP Forum] Factoring Mersenne numbers

[Jean-Claude Arbaut]

Thanks !

So there is indeed a table of factors... I know some of the factorization
methods cited, but I wasn't aware of this optimization.

Jean-Claude Arbaut



2013/6/18 Stefan Kohl <stefan at mcs.st-and.ac.uk>

> Dear Forum,
>
> Jean-Claude Arbaut wrote:
> > While I was playing with FactorsInt and FactInt, I was quite impressed by
> >
> > FactorsInt(2^467 - 1);
> >
> > FactorsInt(2^919 - 1);
> >
> > 467 and 919 are prime. The factors found are quite large: 58 decimal
> digits
> > for
> > the first, and 126 for the other. These are not the largest factors, but
> > the second largest,
> > and I would have expected the task to be harder.
> > I'm almost sure they are not "cached", since factorization can take hours
> > for other
> > Mersenne numbers, even with much smaller factors (M604 seems to be harder
> > for GAP, with a second-largest factor of "only" 32 digits).
> >
> > On the other hand, Yafu takes much more time to factor these two numbers.
> > Of course, factorization speed depends on the method used, the choice of
> > parameters... and luck (some numbers will be better broken with the right
> > combination of parameters I bet).
> >
> > Now, is this only luck, or is there some good reason for GAP (algorithm
> > better suited to Mersenne numbers ?) to find these factors so fast ?
>
> The integer factorization routine implemented in the FactInt package
> makes use of a combination of various factoring methods. These include:
>
>   - Trial division,
>   - Database lookup,
>   - Caches (single factors and complete factorizations),
>   - Various tricks for special cases,
>   - Pollard Rho,
>   - Pollard p-1 / Williams' p+1,
>   - ECM (Elliptic Curves Method) and
>   - MPQS (Multiple Polynomial Quadratic Sieve)
>
> For Mersenne numbers (or more generally, for numbers of the form a^b +/- 1
> for small a and b), it uses Richard P. Brent's Factor Tables
> (http://maths-people.anu.edu.au/~brent/factors.html). The copy shipped
> together with FactInt has been updated for the last time on June 16, 2011.
>
> The issue with 2^604-1 is simply that the database does not contain
> the factor 130530323901899210670077, which therefore needs to be found
> by doing 'actual work' (I tried it on my Laptop, and the factor was found
> by ECM in about half a minute).
>
> Best regards,
>
>     Stefan Kohl
>
>
>