Mersenne number with exponent 333333367 is composite

[Mark Rose]

Originally Posted by Madpoo

The smaller would have been found by only trial factoring to 37 bits, and the second one by TF to 49 bits. Doing either of those tests are trivial and would have finished in (seconds? couple minutes)?

On a GTX 580 without any particular tuning:

./mfaktc.exe -d 1 -tf 333333367 1 49
<snip>
found 2 factors for M333333367 from 2^ 1 to 2^49 [mfaktc 0.21 75bit_mul32_gs]
tf(): total time spent: 0.724s

[Dr Sardonicus]

Originally Posted by TheGuardian

PS. May I ask how these huge numbers came to be factored? Surely most deterministic algorithms would take ages to complete.

In this particular case, the small factor is easily found by trial:

? p=333333367;for(i=1,1000,q=2*i*p+1;if(Mod(2,q)^p==Mod(1,q),print("q = 2*k*333333367 + 1 is a factor of M_333333367 for k = "i".  The  factor q is "q".");break))

q = 2*k*333333367 + 1 is a factor of M_333333367 for k = 137.  The  factor q is 91333342559.

[GP2]

Originally Posted by TheGuardian

PS. May I ask how these huge numbers came to be factored? Surely most deterministic algorithms would take ages to complete.

For Mersenne numbers ( 2^p−1 ), all factors must be of the form 2kp + 1 for some integer k.

That eliminates most factors immediately: for instance, for M333333367 the smallest theoretically possible factor would be 666,666,735 and not 3 or 5 or whatever. That's 2kp + 1 for k=1, or 2×1×333333367 + 1

And we only need a partial factorization. In fact we only really care about finding one factor. For M333333367, it turns out that the value of k which provides the first factor is k=137, and that is small enough to find almost immediately.

If you have an NVIDIA GPU, you can search for factors using the program mfaktc. It uses additional math to eliminate about 80% of the possible k values for any given p, and then trial factors the rest.

[Dr Sardonicus]

Originally Posted by GP2

For Mersenne numbers ( 2^p−1 ), all factors must be of the form 2kp + 1 for some integer k.
<snip>
If you have an NVIDIA GPU, you can search for factors using the program mfaktc. It uses additional math to eliminate about 80% of the possible k values for any given p, and then trial factors the rest.

Amusingly, half of the candidates k are eliminated by the requirement that for p > 2, q = 2*k*p + 1 must be congruent to 1 or 7 (mod 8). This means that k must be congruent to 0 or -p (mod 4).

To get down to 20% of candidate k's, you have to eliminate 60% of the remaining 50%. That ain't chopped liver. Good job!