found this factor

[tha]

[Sun Jun 17 07:24:58 2007]
P-1 found a factor in stage #2, B1=420000, B2=11970000.
UID: Tha/test25, M33604049 has a factor: 136310731051936404841226250672413144328777911

45 digits, but not checked if it is composite.

[Xyzzy]

294119824093630492221527 × 463453055134913541793

[ewmayer]

463453055134913541793 = 1+2*p*k, with k = 2⁴*3*17*17387*486037,
294119824093630492221527 = 1+2*p*k, with k = 44683*179057*546977,

that's why the composite factor was found in stage 2, but neither of the prime factors popped out after stage 1 - each has a largest factor of k slightly above the stage 1 primes bound.

Apparently Prime95 only does 2 GCDs, one at the end of each stage - a GCD done when stage 2 reached any prime >= 486037 would have revealed the smaller factor, and one done at any p >= 546977 (much smaller than the stage 2 upper bound that was used) would have revealed both.

But stage 2 primes are cheap and GCDs expensive...

[xilman]

Originally Posted by ewmayer

463453055134913541793 = 1+2*p*k, with k = 2⁴*3*17*17387*486037,
294119824093630492221527 = 1+2*p*k, with k = 44683*179057*546977,

that's why the composite factor was found in stage 2, but neither of the prime factors popped out after stage 1 - each has a largest factor of k slightly above the stage 1 primes bound.

Apparently Prime95 only does 2 GCDs, one at the end of each stage - a GCD done when stage 2 reached any prime >= 486037 would have revealed the smaller factor, and one done at any p >= 546977 (much smaller than the stage 2 upper bound that was used) would have revealed both.

But stage 2 primes are cheap and GCDs expensive...

As is factoring small composite integers.


Paul

[ewmayer]

Originally Posted by xilman

As is factoring small composite integers.

True, but irrelevant to the argument that 99% of the stage 2 runtime ended up being unnecessary in this instance.