Who does the early trial factoring?
 

According to the GIMPS "The Math" page, exponents are "Trial Factored" up to a predetermined level (i.e. 70 bits for numbers currently being factored in the 40M range. But I notice these numbers have already been factored up to 63 bits before they are put on the "available" list. Who factors them up to this starting level of 63 bits?

And as a curiosity once this trial factoring is done what percentage of the original list of prime exponents has been "cleared"? This same math page suggests 95% of exponents are cleared by factoring yet the total of the Factored column is only about 60% of the Numbers column in the Status chart.

Check out this forum here: <http://www.mersenneforum.org/forumdisplay.php?f=12>.

The "Lone Mersenne Hunters" are a group of people looking for factors of mersenne numbers outside the range of numbers available on primenet. Several of them try to factor the numbers as high as they can before they are made available on primenet.

[QUOTE=petrw1;105466]And as a curiosity once this trial factoring is done what percentage of the original list of prime exponents has been "cleared"? This same math page suggests 95% of exponents are cleared by factoring yet the total of the Factored column is only about 60% of the Numbers column in the Status chart.[/QUOTE]
60%. The reference to 95% on the math page is to potential factors of a single Mersenne number that are eliminated as possible factors by the first stage of trial factoring.

[QUOTE=bhebden;105467]The "Lone Mersenne Hunters" [/QUOTE]

While it is true that LMH does the trial factoring, I'm pretty sure that Roy Rogers and Sons of the Pioneers do the trail factoring. You know - "Happy Trails to you until we meet again ..."

[QUOTE=petrw1;105466]And as a curiosity once this trial factoring is done what percentage of the original list of prime exponents has been "cleared"? This same math page suggests 95% of exponents are cleared by factoring yet the total of the Factored column is only about 60% of the Numbers column in the Status chart.[/QUOTE]You misread the math page, it states that "This process eliminates roughly 95% of potential factors.", not that it eliminates 95 % of all exponents.

As for the number of factored Mersennes with prime exponents the Status page gives a percentage of 63 % for the ranges that have been factored.

It is difficult to estimate the impact of the P-1 factor search from the data available : one can only suppose that factors found outside the upper bound of trial factoring have been found by the P-1 stage. One could know the exact impact of P-1 by analysing the results turned in, but that data is not available as such as far as I know.

Jacob

We doubt this is relevant but one time we got bored and P-1 tested a pile of exponents and found around 19,000 factors.

[URL]http://www.teamprimerib.com/rr1/bin/cleared_sum.php?so=p[/URL]

Look at the 4th column from the right.

At the time we did that work a lot of the smaller exponents had not been P-1 factored very far.

[QUOTE=Xyzzy;105524]We doubt this is relevant but one time we got bored and P-1 tested a pile of exponents and found around 19,000 factors.

[URL]http://www.teamprimerib.com/rr1/bin/cleared_sum.php?so=p[/URL]

Look at the 4th column from the right.

At the time we did that work a lot of the smaller exponents had not been P-1 factored very far.[/QUOTE]

If in your bored state you P-1 tested exponents whose primality was unknown then you would have eliminated the need for a lot of LL and DC tests.

[quote]If in your bored state you P-1 tested exponents whose primality was unknown then you would have eliminated the need for a lot of LL and DC tests.[/quote]
If we remember correctly (and it has been a long time, so we could be wrong) the exponents we P-1 tested had already been tested and double checked.

Okay, I'll throw in my clarifications, too. :-)
[quote=petrw1;105466]This same math page suggests 95% of exponents are cleared by factoring[/quote]Your misunderstanding has already been corrected by others, but I'll point out that the exact wording on the page is:

"This process eliminates roughly 95% of potential factors."

[I]not[/I] "This process clears roughly 95% of exponents by factoring."

[quote]the total of the Factored column is only about 60% of the Numbers column in the Status chart.[/quote]If you save a copy of the current Search Status page, then compare it to the page after the next update, then the next and the next ..., you'll see that the total at the bottom of the Numbers column stays constant (because that is the unchanging number of prime numbers between 0 and 79,300,000), while the total under the Factored column always increases (or, very rarely, might stay the same).

Those column headings need to be understood within the context of the GIMPS project.

Under "Mersenne", "Numbers" means "Number of prime numbers, and, thus, number of potential Mersenne primes (if only the primality of the exponent is considered) in these ranges". "Primes" means "Number of Mersenne primes found so far with exponents in these ranges".

The "Composite" heading means "Number of Mersenne numbers with prime exponents in these ranges that have been found to be composite". "Factored" means "Number of Mersenne numbers with prime exponents in these ranges for which a specific factor has been found". "TwoLL" means "Number of Mersenne numbers with prime exponents in these ranges for which two LL tests have had matching nonzero residues, but for which no specific factor has been found". "OneLL" means "Number of Mersenne numbers with prime exponents in these ranges for which at least one LL test has had a nonzero residue, but for which there have not yet been two LL tests with matching nonzero residues, and for which no specific factor has been found".

BTW, the sum of the totals under the "Primes", "Factored", "TwoLL", "OneLL", and "Status Unknown" columns should equal the total under the "Numbers" column. (As I write this, it's off by 1 -- 4,630,914 vs. 4,630,913. Hint: "OneLL".)

Thanks for the clarification ....

Maybe I am still missing something fundamental about Mersenne primes.

As of this writing out of 4,630,913 total exponents, 44 are prime and all but 1,048,005 (status unknown) have been tested at least once. So 3,582,908 have a "status known". Granted not all of these have been DC's yet but for the purposes of my question let us ignore that small probability of error.

So, 0.001228% of the KNOWN are primes ... but yet of the almost 99.999% believed to be composite only 63% have been factored???

Granted I don't understand the distribution of factors in very large MP's; but it seems odd to me that considering the sieving and early factoring done that so relatively few (i.e. 63%) are factored ... I would have expected that when looking for factors up to 2^60 or 70 that a much larger percentage would be cleared as factored. This implies to me that 37% of these numbers have only large factors...larger than a couple hundred digits.

Oh well, chalk it up to my education.

[QUOTE=petrw1;105611]Granted I don't understand the distribution of factors in very large MP's; but it seems odd to me that considering the sieving and early factoring done that so relatively few (i.e. 63%) are factored ... I would have expected that when looking for factors up to 2^60 or 70 that a much larger percentage would be cleared as factored. This implies to me that 37% of these numbers have only large factors...larger than a couple hundred digits.[/QUOTE]

Others may want t put more precise numbers on this, but as a rule of thumb, roughly half of M(p) will have at least one small factor q = 2*k*p+1, where by "small" the best measure (i.e. least dependent on the size of the exponent p) is based on the size of k (what I call the "factor index", though this is not standard terminology). To put some GIMPS-representative numbers on this, let's say that for exponents p ~= 2[sup]24[/sup], on average 50% of the corresponding M(p) will have factors of 60 bits or less, i.e. q < 2[sup]60[/sup] (k < 2[sup]35[/sup]). I cast this in terms of the factor index k because I believe (although I need to double-check this) for numbers having factors of a special for like this, the probablity of finding a factor between adjacent power-of-2 bounds k =2[sup]x[/sup] and 2[sup]x+1[/sup]is roughly proportional to 1/x, at least as long as k is much smaller than M(p). So if TFing up to q = 2[sup]60[/sup] (k= 2[sup]35[/sup]) has a 50% chance of turning up a factor, going up to q = 2[sup]70[/sup] (k=2[sup]45[/sup]) increases our chance of finding a factor by roughly

0.50*(1+1/35)*(1+1/36)*(1+1/37)*(1+1/38)*(1+1/39)*(1+1/40)*(1+1/41)*(1+1/42)*(1+1/43)*(1+1/44) ~= 0.643,

which is quite close to the 63% figure you mention. The remaining 37% will only have factors > 2[sup]70[/sup], which means of roughly 21 decimal digits or more, not the "couple hundred digits" you cite.

Again, the above formula is just a rough heuristic, which works reasonably well for small factor bounds - if you extend the above calculation to k larger than 50 bits you start getting probabilities over 100%, which are of course nonsensical.

The main point is that increasing the TF depth gives rapidly diminishing returns, since the smaller k's give most of the factors.