Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2011-03-18, 20:11   #1
nuggetprime's Avatar
Mar 2007

4568 Posts
Default Probability of factor (TF)

Is there a formula / excel spreadsheet anywhere which lets me calculate the probablility that I find a factor for Mn by trial factoring from x to x+1 bits, with no previously known factor?

nuggetprime is offline   Reply With Quote
Old 2011-03-18, 21:28   #2
Account Deleted
Mini-Geek's Avatar
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default (put in a TF assignment and factoring range, as part of the result it says the chance of finding a factor)
That's the easiest way, since it applies the formula for you.
The actual formula is at:
the chance of finding a factor between 2X and 2X+1 is about 1/x
Pretty simple.
But note that this only counts starting at about log_2(p) bits, since all factors must be of the form 2kp+1.

Whether there is a previously known factor does not make a difference in the distribution of further factors, but the TF depth does.

Last fiddled with by Mini-Geek on 2011-03-18 at 21:32
Mini-Geek is offline   Reply With Quote
Old 2011-03-19, 22:14   #3
Mr. P-1
Mr. P-1's Avatar
Jun 2003

7×167 Posts

the chance of finding a factor between 2X and 2X+1 is about 1/x
That only applies if no prior factoring work has been done, which could have found a factor in that range. If that isn't the case, for example if a P-1 test has been done on the exponent, then the probability of finding a factor with TF will be less.

Last fiddled with by Mr. P-1 on 2011-03-19 at 22:14
Mr. P-1 is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Probability of n-digit factor? roger Factoring 3 2007-05-09 22:51
Probability of finding a factor JuanTutors Software 20 2004-09-26 09:47
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38
Probability of finding a factor in TF eepiccolo Math 4 2003-06-07 05:56
Probability of finding a factor in DC p-1 Deamiter Math 4 2002-12-25 06:06

All times are UTC. The time now is 02:29.

Tue Jun 15 02:29:37 UTC 2021 up 18 days, 16 mins, 0 users, load averages: 2.08, 2.26, 2.00

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.