View Single Post
Old 2007-06-18, 19:44   #4
xilman's Avatar
May 2003
Down not across

11·17·59 Posts

Originally Posted by ewmayer View Post
463453055134913541793 = 1+2*p*k, with k = 24*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.

xilman is offline   Reply With Quote