'twas brillig (translation: 'not needed')

[Madpoo]

Originally Posted by Batalov

Right! Anyone who didn't have a bad residue... ...

Discounting some bad residues in my history that I can chalk up to Prime95 errors (shift count being with a certain proximity of the exponent itself, for instance), I still have some in the distant past that ended up bad, which I can only attribute to machine error.

All told I think there are about 27 bad ones in my past (mostly from the v4 days), like this one:
http://www.mersenne.org/M1843147

Curiously that one got retested by me recently when I triple-checked everything below 2M.

EDIT: Kind of funny looking back at the bad ones... some were my crappy home machines, some were from my brother and a friend of mine, and surprisingly two of them came from the (infamous) US WEST machines. Weird.

[dbaugh]

Here is a screen scrape of the command window where I found the 80 bit factor of 12827821 using TF.

Date Time | class Pct | time ETA | GHz-d/day Sieve Wait
Nov 09 03:05 | 4524 98.0% | 2664.8 14h03m | 644.70 82485 n.a.%
Nov 09 03:50 | 4535 98.1% | 2665.0 13h19m | 644.66 82485 n.a.%
Nov 09 04:34 | 4536 98.2% | 2665.2 12h35m | 644.60 82485 n.a.%
Nov 09 05:18 | 4539 98.3% | 2664.8 11h50m | 644.70 82485 n.a.%
Nov 09 06:03 | 4544 98.4% | 2664.7 11h06m | 644.71 82485 n.a.%
Nov 09 06:47 | 4548 98.5% | 2664.8 10h21m | 644.69 82485 n.a.%
Nov 09 07:32 | 4551 98.6% | 2664.8 9h37m | 644.69 82485 n.a.%
Nov 09 08:16 | 4556 98.8% | 2664.7 8h52m | 644.72 82485 n.a.%
Nov 09 09:00 | 4559 98.9% | 2665.0 8h08m | 644.64 82485 n.a.%
Nov 09 09:45 | 4560 99.0% | 2665.2 7h24m | 644.60 82485 n.a.%
Nov 09 10:29 | 4563 99.1% | 2665.6 6h39m | 644.50 82485 n.a.%
Nov 09 11:14 | 4571 99.2% | 2666.1 5h55m | 644.39 82485 n.a.%
Nov 09 11:58 | 4580 99.3% | 2665.2 5h10m | 644.59 82485 n.a.%
Nov 09 12:43 | 4583 99.4% | 2666.4 4h26m | 644.30 82485 n.a.%
Nov 09 13:27 | 4584 99.5% | 2666.0 3h42m | 644.40 82485 n.a.%
M12827821 has a factor: 1426192839661371189084169
Nov 09 14:11 | 4595 99.6% | 2666.1 2h57m | 644.39 82485 n.a.%
Nov 09 14:56 | 4599 99.7% | 2665.6 2h13m | 644.50 82485 n.a.%
Nov 09 15:40 | 4604 99.8% | 2665.6 1h28m | 644.50 82485 n.a.%
Nov 09 16:25 | 4611 99.9% | 2665.8 44m26s | 644.46 82485 n.a.%
Nov 09 17:09 | 4616 100.0% | 2665.9 0m00s | 644.43 82485 n.a.%
found 1 factor for M12827821 from 2^80 to 2^81 [mfaktc 0.21 barrett87_mul32_gs]
tf(): total time spent: 29d 17h 52m 0.112s

ERROR: get_next_assignment(): no valid assignment found in "worktodo.txt"

C:\David\mfaktc>

It shows something I did not expect. Even though the factor is 80.24 bits long, it was not found until very near the end of the 2^80 to 2^81 run. I naively would have expected it in the first quarter.

[tha]

Originally Posted by dbaugh

Here is a screen scrape of the command window where I found the 80 bit factor of 12827821 using TF.
C:\David\mfaktc>

It shows something I did not expect. Even though the factor is 80.24 bits long, it was not found until very near the end of the 2^80 to 2^81 run. I naively would have expected it in the first quarter.

Trial factoring ploughs through all work one by one. P-1 does all the work in one run first and then sieves a result, if there is one, out of all the work in the second run, which takes only seconds.

[dbaugh]

What I was trying to say is that I expected the factors being tried in the final classes to be near the upper limit of the bit range being tested when using mfaktc. This does not appear to be the case. TF may do the work one by one but not in the naïve order.

[bloodIce]

The classes have nothing to do with the bitsize of a factor. There are implemented for faster sieving, but in each class you have pretty much the same bit-length range. When you go through the candidates in a class you start from some value close to 2^81 and end close to 2^82, then you go to the next class and start again from 2^81 (for TF81-82). Well, theoretically the last class (4620) should have the largest candidate factor, and class 0 should have the candidate, which is the closest to the start, but the differences between the min and max candidates tested in each class are minute.

[LaurV]

Originally Posted by dbaugh

What I was trying to say is that I expected the factors being tried in the final classes to be near the upper limit of the bit range being tested when using mfaktc. This does not appear to be the case. TF may do the work one by one but not in the naïve order.

It doesn't work like that. One "class" is just the modularity class for k (mod 4620). Your k is (q-1)/(2p)=(1426192839661371189084169-1)/(2*12827821)=55589832429894804, which calculated (mod 4620) gives 4584. This is the class where you found the factor in. This is done to be able to eliminate as many candidates as possible from start. Considering that the factor q has to be prime, and it has to be 1 or 7 (mod 8), there are only 960 remaining classes from 4620, where the factors can be. So, even without any sieving, we would need to test only one in 5 candidates (i.e. 960 /4620) if they are factors or not.

Which 960 classes from 4620 we need to test, this depend on p, but they are always 960, differently distributed along the 4620 total classes. For example, your p is 12827821, which is 2701 (mod 4620).

If a number k is in class 4584 (as in your case, k=4584 (mod 4620)) then when we compute q (mod 4620) we will get q=2kp+1=2*4584*2701 (mod 2*4620) which is 8809 (mod 9240). This mean that it is 1 (mod 8) and gcd(8809, 4620)=1, so it can be prime, and it can be a factor so we need to test this class.

If a number k is in class (say) 1500, k=1500 (mod 4620), then when we compute q (mod 4620) we will get q=2kp+1=2*1500*2701 (mod 2*4620) which is 8760 (mod 9240). Now gcd(8760, 4620)>1, so q can not be prime, therefore we can skip all candidates in this class.

So, mfaktc uses modularity of p to 4620 to check which classes to keep and which to skip when looking for factors. If you factor at (say) bitlevel from 70 to 71, and your m=2^p-1 has a factor q in first tested class, it will be found first, no matter if it is close to 70 or to 71 bits. Viceversa, if the factor is in last class, it will be found last, no matter if it is small (close to 70 bits) or big (close to 71 bits).

This is how it works.

Again, your work seems legit. You spent 844 minutes to finish 19 classes, which would mean 42644 minutes for all 960 classes. That is 29 days, 14 hours, and few minutes. Your time is quite right, if your computer was sometime busier (like watching a movie) which extends the time. Also it seems that it worked without interruption for those 29 days, as there is no sign of resuming the work. Honestly I don't think you went to the trouble to falsify that, is a hell of work. This time I believe you really did that work. So yes, you convinced me this time. Now you should do something about it, because I don't know for how long...