M727 ... History

[petrw1]

Discussions recently regarding factoring M1061 and a few others seems to suggest that factoring attempts whether P-1 or ECM for all practical purposes seldom go over 60 bits (18 digits). In very rare cases there have been factors reported just over 100 bits (30 digits) ... so how did someone manage to find the nearly 100 digit (over 300 bits) factor of M727?

[fivemack]

Originally Posted by petrw1

Discussions recently regarding factoring M1061 and a few others seems to suggest that factoring attempts whether P-1 or ECM for all practical purposes seldom go over 60 bits (18 digits). In very rare cases there have been factors reported just over 100 bits (30 digits) ... so how did someone manage to find the nearly 100 digit (over 300 bits) factor of M727?

ECM on huge Mersenne numbers can't go very far because individual iterations take so long. On small numbers (say, less than 1000 bits), you can run ECM to a level to find 150-bit factors in about two weeks on a K8/2GHz.

On numbers of less than about 750 bits, and if you've got the resources of a major research group behind you, numbers up to just over 1000 bits, you can run something called SNFS which finds factors regardless of their size. The process is quite complicated; for M727, it would have taken about four months on a K8/2GHz. For M1039, it took roughly two hundred CPU-years, and one part of the calculation required four closely-coupled clusters each of around fifty machines.

[James Heinrich]

I'm not sure on the reasons behind it, but on occasion P-1 will return very large factors, which are (always?) composite. For example, on my stats site you'll see the top-10 P-1 factors are all between 40 and 48 digits long (131-159 bits), but every one of them is composite.
This is a handy quick-check tool for primality testing of factors.

[S485122]

Some time ago P-1 returned a very big factor for a number (it is the biggest one on James page :-) I thought it was a top ten factor, but it was composite :-( The explanation given was :

Originally Posted by Mr. P-1

... what happened was that in this instance there were two prime factors that were k-smooth to the bounds of your P-1 test:

26207295509565505207993-1 = 2^3 . 3 . 7 . 43 . 150107 . 617761 . 39122179

29949590891764532677185481-1 = 2^3 . 3 . 5 . 173 . 1861 . 2087 . 9494491 . 39122179

In this situation, the P-1 test returns the product of the factors, an interesting outcome, but by no means exceptional ...

Jacob