[GAP Forum] Factoring Mersenne numbers

[Stefan Kohl]

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