How did Prof.Cole factor M67?

[JeppeSN]

forprime(p=2,2^(67/2),(2^67-1)%p==0&&return(p))

(PARI/GP) That is the worst method I can imagine. It tries every prime (ignoring the fact that Mersenne divisors have a special form), it even recalculates 2^67 every time without modular optimization. And still you have the answer in less than 5 seconds on a slow machine.

OK, the primes were pre-sieved. If you try all whole numbers, it actually becomes kind of slow (over a one minute on my slow machine): for(p=2,2^(67/2),(2^67-1)%p==0&&return(p))

Any slower?

/JeppeSN

[retina]

Originally Posted by JeppeSN

Any slower?

Slower is easier to achieve than faster.

Work your way downwards, trial divide from 2^67-2 to sqrt(2^67).

[CRGreathouse]

There is a glorious algorithm proudly posted on Stack Overflow:

isPrime(testNum)
{
    if ( testNum <= 1 )
        return false;
    for ( primeFactor = 2; primeFactor < testNum; primeFactor++ )
        if ( isPrime(primeFactor) )
            if ( testNum % primeFactor == 0 )
                return false;
    return true;
}

which could be adapted for this purpose. It would take over 10^978123027341497027 recursive calls to isPrime() to determine the primality of 2^67-1 with this algorithm.

[bsquared]

Originally Posted by CRGreathouse

There is a glorious algorithm proudly posted on Stack Overflow:

isPrime(testNum)
{
    if ( testNum <= 1 )
        return false;
    for ( primeFactor = 2; primeFactor < testNum; primeFactor++ )
        if ( isPrime(primeFactor) )
            if ( testNum % primeFactor == 0 )
                return false;
    return true;
}

which could be adapted for this purpose. It would take over 10^978123027341497027 recursive calls to isPrime() to determine the primality of 2^67-1 with this algorithm.

That... is a work of art. Finely crafted inefficiency.

[edit]
2731988490 calls to prove 127 prime.