mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2007-11-05, 17:31   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

5·953 Posts
Default M727 ... History

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?
petrw1 is offline   Reply With Quote
Old 2007-11-05, 17:40   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

3·19·113 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
fivemack is offline   Reply With Quote
Old 2007-11-11, 12:53   #3
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

66568 Posts
Default

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.
James Heinrich is offline   Reply With Quote
Old 2007-11-11, 15:37   #4
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

2×13×67 Posts
Default

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 :
Quote:
Originally Posted by Mr. P-1 View Post
... 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
S485122 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
M39761383 history bgbeuning Information & Answers 2 2016-01-29 03:19
History ET_ Operazione Doppi Mersennes 15 2012-09-19 13:11
Strange history lidocorc PrimeNet 1 2008-12-21 16:21
History Greenbank Octoproth Search 1 2007-02-16 23:41
History of 3*2^n-1 Citrix 3*2^n-1 Search 2 2006-11-16 00:13

All times are UTC. The time now is 08:00.


Tue Oct 19 08:00:35 UTC 2021 up 88 days, 2:29, 0 users, load averages: 1.10, 1.12, 1.12

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.