[GAP Forum] Factoring Mersenne numbers

[Jean-Claude Arbaut]

Hello,

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 ?

Best regards,

Jean-Claude Arbaut