mersenneforum.org  

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

Reply
 
Thread Tools
Old 2003-12-10, 22:12   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

12268 Posts
Question How large a factor can P-1 testing find ?

In trial factoring for the bigger mersennes it will test factors that are upto 72 bits long ( to just below 2^72 ).

The software may support slighty higher for factor overide but not sure about it.

What is the max size factor P-1 factoring can find in either stage 1 or stage 2 ?
Why is that ( whatever it is ) the limit ? memory, software, math ?

Perhaps, this is also a math question.
dsouza123 is offline   Reply With Quote
Old 2003-12-11, 00:00   #2
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

See http://www.loria.fr/~zimmerma/records/Pminus1.html for the largest factors found by the P-1 method.

I don't know of any theoretical upper limit. I think this is what makes P-1 factoring more interesting than trial factoring, there is always the possibility that you will find a record factor.
geoff is offline   Reply With Quote
Old 2003-12-11, 00:09   #3
nfortino
 
nfortino's Avatar
 
Nov 2003

16510 Posts
Default

There is no hard limit, only a probable one. P-1 factoring finds factors p of a number if all of the factors of p-1 are less than a certain limit most people call B1. Using an extension, p-1 factoring finds all factors p if all but one factor of p-1 is less than B1, and the remaining factor is less than B2. It is conceivable that this method could find an arbitrarily large factor, it is just highly unlikely. Almost all factors found by this method will be less than 35 or 40 digits.
nfortino is offline   Reply With Quote
Old 2003-12-11, 00:48   #4
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default

Thanks for the informative replies,

I checked the link and for the largest mersenne listed 2^17504141 - 1 , it had a p-1 factor = 426315489966437174530195419710289226952407399

which is 45 digits ( roughly 149 bits), it is much larger than what is produced from trial factoring (72 bits at the upper end).

The summary of the conditions for stage 1 and stage 2 answered alot about p-1 that was vaque before.
dsouza123 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Manual Testing LL result syntax (where to find documentation) preda GPU Computing 15 2017-04-17 15:02
Can Pollard Rho cycles be used to find a factor? wwf Factoring 26 2013-09-30 04:24
Best Way to find large factors mahnouman Information & Answers 19 2013-02-22 06:11
PFGW can't find a small factor. Arkadiusz Software 7 2013-02-18 12:43
How much ECM does it take to find a given factor? geoff Factoring 5 2004-09-29 20:14

All times are UTC. The time now is 21:36.

Tue Oct 27 21:36:24 UTC 2020 up 47 days, 18:47, 2 users, load averages: 2.46, 2.13, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.