Cleared exponents that never made it into data files

[GP2]

We extract all unique exponents from cleared.txt (cleared exponents), dated 14 Sep 2003 20:00 UTC.

Then we extract all unique exponents from BAD, LUCAS_V.TXT, HRF3.TXT, and factors (all exponents that have ever had an LL-test returned or a factor returned), from the Sept 9 2003 data files (updated roughly weekly).

Then we look for unique exponents that are found in cleared.txt but not in any of those data files.

There are 1522 exponents. However, we eliminate any cleared result with a return date after 09-Sep-03 (results returned more recently than the last edition of the data files).

When we do that, however, we still get 15 results:

14572163  66     0x96FCC960D47A09__                19-Nov-02 00:14  S78380         CD2AD6EAD
15370879 103   F  7757301118393895425291596492654  19-Sep-02 15:40  S09625         C2EE070A4
15729167 102   F  4489874295809814634906444128101  20-Sep-02 12:17  S09625         C2EE070A4
15953537  66     0xAB132582134FD2__                09-Jan-03 10:47  S81293        C0B531E29
16878139  65     0x80C974D551468F__                14-Mar-03 07:03  eteo           teerex
18050569  67     0xF5C8DA9CAFCE13__                25-Mar-03 13:40  timesau        1_gigr
18167557  67     0xB016E51AB1002C__                24-Mar-03 21:55  typhoonmike    Biohazard
18583559  67     0x7A1E8002C69347__                24-Jul-03 06:00  S38041         C85D4A152
18734293  67     0xE3F3F278A93C42__                29-Aug-03 06:53  dramacutie303  Katherine_B
18956551  67     0x53FF8EF6D6CAAF__                18-Aug-03 12:31  mkroska        web-ws-lfh
19634569  66     0x21:__                           17-Jun-03 13:15  RichJacot      yoda
19857121  67     0x12EE5DB062B25C__                20-Jun-03 03:12  transcend      pope
21558739  61   F              2782804445561117561  07-May-03 06:16  S103771        CC0AD6257
23180177  58   F               224966031444110303  30-Jul-03 14:44  ricsodre       PlasmaWall
33238477  69     0xD12F51397BCA23__                01-Sep-03 14:16  S67532         C7364A0E9

The residue for 19634569 is garbage, naturally.

Checking the factors by verifying whether (2^p - 1) mod f == 0, using an extended-precision math package, it turns out that first two huge ones (103 and 102 digits) are bogus, but the final two smaller ones are perfectly valid, yet are not in the factors database!

By the way, one of those 15 exponents just happens to be 33238477, mentioned in the missing? thread, with a return date of 01-Sep-03, which prompted this latest investigation. A rather amazing coincidence.


George?

[NickGlover]

Originally posted by GP2
Checking the factors by verifying whether (2^p - 1) mod f == 0, using an extended-precision math package, it turns out that first two huge ones (103 and 102 digits) are bogus, but the final two smaller ones are perfectly valid, yet are not in the factors database!

Very large factors are truncated in the Primenet reports which is why the 102 and 103 bit factors appear bogus. The actual factors found are actually larger than 102 and 103 bits, and the correct factors do get to George, even if they don't show up on Primenet correctly.

Also, the server will reject any factors that don't pass a simple verification calculation. That's how we know that no bad factors have ever caused us to miss a prime.

[Prime95]

Prime95 sends two messages to the primenet server when an exponent completes. The text based one I use to maintain my databases, the other one is used by the server to update its databases and print the cleared exponents report. In eleven of these cases, the server got its message, but I never got the text based one.

I've added the nine LL tests and the two missed factors to my database.

Thanks data guru!

[GP2]

Originally posted by NickGlover
Very large factors are truncated in the Primenet reports which is why the 102 and 103 bit factors appear bogus. The actual factors found are actually larger than 102 and 103 bits, and the correct factors do get to George, even if they don't show up on Primenet correctly.

Hmmmm, you're quite right.

cleared.txt has the following:

16091291 103   F  7362770625422642419324076409959  05-Dec-02 04:11  S24590         4
18965599 103   F  8602653675602192712514732427431  30-Apr-03 04:46  S58485         CHERRY
33475447 103   F  7621901790064563660031276374525  14-Aug-03 17:44  eipi           ulka

Whereas the actual factors are
16091291,117362770625422642419324076409959
18965599,34488602653675602192712514732427431
33475447,7621901790064563660031276374525079
(1st = 2 digits truncated at the start)
(2nd = 4 digits truncated at the start)
(3nd = 3 digits truncated at the end)

Now, if we were missing the above actual factors, we could still reconstruct them based on the cleared.txt values. This can be done by running a script that adds every combination of up to 6 digits at the start or the end of the truncated factor, and then checking each new value for (2^p - 1) mod f == 0 using an extended-precision arithmetic package like libgmp on Linux. This takes about a minute or so on a 2.8 GHz P4.

However, I was unable to reconstruct the factors (if they actually exist) for the original exponents in question:
15370879
15729167
I tried every combination of up to extra 6 digits at the start or up to 6 at the end, without any luck.

However, there's also some weird stuff in cleared.txt. Check this out:

 8276539 103  DF  7411192628700266363789140779170  18-Nov-02 00:48  Team_Prime_Rib Tasuke18
17699497 103   F  8254656556609760068242738155742  26-Mar-03 08:12  Team_Prime_Rib KL_MLChan
18129493 103   F  8754500160125057908417949485956  24-Feb-03 07:26  curtisc        wde3100-09

What's wrong with this picture?
1) These are all bogus factors.
2) Even assuming they were truncated by up to 6 digits at the start or up to 6 digits at the end, they're still bogus.
3) Much smaller known factors exist:
8276539,67600209174876814543
17699497,73630130820677243353
18129493,303330458703290742127

There are a number of similar examples, I haven't yet investigated how many, with many different users. I singled out a couple of Team_Prime_Rib exponents: maybe you guys can contact those folks and ask them what's in their results.txt.

Maybe we can figure out why huge bogus factors are getting sent to the server...

And I'm guessing that
15370879
15729167
are also bogus in the same way as the above (with the only difference being, for those two cases, we don't have any much-smaller known factors, in fact no known factors at all).

Also, the server will reject any factors that don't pass a simple verification calculation. That's how we know that no bad factors have ever caused us to miss a prime.

Actually, we also can do the (2^p - 1) mod f == 0 test on the entire factors database. With a 2.8 GHz P4, the entire database of 2,651,013 factors can be verified in a couple of minutes. I've done this, and there are indeed no bad factors.

[NickGlover]

Note that sometimes when P-1 finds a really large factor, the factor itself is not prime and may be the product of multiple factors. George will usually factor these large P-1 factors and put only the smallest prime factor into his database.

So, you may find that the factor you find in George's factors.cmp is completely different from what is on Primenet. This doesn't really invalidate your attempts at finding the actual factor for the three factors you listed. My best guess is that trying 6 digits on either side is not enough. I think the largest P-1 prime factor ever found is something greater than 50 digits (166 bits), so it is plausible that those three factors are some part of the digit sequence for a product of valid prime factors of the Mersenne numbers in question.

[apocalypse]

GP2 -

for the following numbers:

 8276539 103  DF  7411192628700266363789140779170  18-Nov-02 00:48  Team_Prime_Rib Tasuke18
17699497 103   F  8254656556609760068242738155742  26-Mar-03 08:12  Team_Prime_Rib KL_MLChan
18129493 103   F  8754500160125057908417949485956  24-Feb-03 07:26  curtisc        wde3100-09

Since the bit length of these numbers is significantly above the upper limit for trial factoring, these must have been found by the P-1 factoring step. P-1 factoring can find composite factors of M numbers, and when this happens, the server factors the reported factor and saves only the smallest prime factor of the reported number, i.e. the smallest known prime factor of the M number.

This is probably what happened here.

On a side note, the reported factors are 66, 66, and 69 bits, respectively. This means the server has an upper limit on the number of bits it reports.

[Prime95]

The factors for 15370879 and 15729167 do not exist. I did get the text message for those and the factors were bogus.

[smh]

My best guess is that trying 6 digits on either side is not enough. I think the largest P-1 prime factor ever found is something greater than 50 digits (166 bits), so it is plausible that those three factors are some part of the digit sequence for a product of valid prime factors of the Mersenne numbers in question.

The largest factor found with P-1 has 47 digits. The largest GIMPS factor found with P-1 has 45 digits.

http://www.loria.fr/~zimmerma/records/Pminus1.html

the server only displays factors upto about 31 or 32 digits corectely. So i guess you'll have to add 1 or 2 extra digits in your test.

[NickGlover]

Well, if a factor could be 45 digits and the report is only showing 31 or 32, I would think GP2 would need to try up to 14 digits in either direction. Also, if the factor is a product of prime factors, then GP2 may need to try even more than 14 digits to find the factor.

[smh]

The link above shows the 10 largest factors ever found with P-1 (if the file is up to date). Only 3 of these were found with prime95/mprime.

Factors found with p-1 above 39 digits are rare (although i'm convinced many more will be found if more time is spend running P-1 compared to ECM).

If it takes 1 minute to test for 6 missing digits it will take about 190 years to test for 14 missing digits.

I't might be faster to rerun P-1 with high memory limits to see if the factor can be found again.

[Xyzzy]

I can run those P-1s if someone tells me what the worktodo.ini line should be...

(I can't use Pfactor because I don't know what bit depth they were trial factored to, and I can't use Pminus1 because I don't know what bounds were used!)