Getting reliable LL from unreliable hardware

[ewmayer]

Originally Posted by R. Gerbicz

This reliable error checking idea here http://mersenneforum.org/showthread.php?t=22510
from me is just working for Mersenne numbers also!

Why not do a Fermat pseudoprime test for base=3, but (for p>2) in the
equivalent form of res=3^(2^p) mod mp, where mp=2^p-1.

We are talking about improving the odds of catching 'silent' (in the sense that they don't trip the standard kinds of data-integrity checks, most notably the excess-fractional-part check in the carry step) hardware errors *within* such a long computation, whether it be an LL test, base-3 pseudoprime test, whatever. For M(p), replacing LL with a Fermat pseudoprime test only means that any hardware errors of this type will now lead to an erroneous Fermat pseudoprime residue, rather than an erroneous LL-test one. Since both methods have virtually identical runtimes assuming equivalently good implementations, I fail to see how this offers any advantage. (And that is assuming that an analogous kind of persistent checksum exists for the Fermat-PRP case - if not, it is in fact a step backward.)

[R. Gerbicz]

Originally Posted by ewmayer

We are talking about improving the odds of catching 'silent' (in the sense that they don't trip the standard kinds of data-integrity checks, most notably the excess-fractional-part check in the carry step) hardware errors *within* such a long computation, whether it be an LL test, base-3 pseudoprime test, whatever.

For my algorithm it doesn't matter where comes from the error, if in the i-th square operation r!=res^2 mod mp then it will be detected with an incredible high probability (not immediately, in the next j-th operation, where j is divisible by L^2), much higher than the smallish 0.5 probability. In fact the error will be detected in all cases, if there was a single erroneous square in L^2 consecutive squares.

Originally Posted by ewmayer

(And that is assuming that an analogous kind of persistent checksum exists for the Fermat-PRP case - if not, it is in fact a step backward.)

What checksum (algorithm) for the Lucas Lehmer test?

[ATH]

I just tried the Jacobi symbol in GMP 6.1.2 with Mp = 2^75000007-1 and a simulated residue by just subtracting some random numbers from Mp.

I'm not sure what I'm doing wrong because instead of the reported 31 sec and 55 sec it only takes ~18 milliseconds. I did check that both variables was 22,577,252 digits.

[axn]

Originally Posted by ATH

by just subtracting some random numbers from Mp.

How big were these random numbers? Were they about the size of the Mp itself or some small numbers?

[preda]

Originally Posted by ATH

I just tried the Jacobi symbol in GMP 6.1.2 with Mp = 2^75000007-1 and a simulated residue by just subtracting some random numbers from Mp.

I'm not sure what I'm doing wrong because instead of the reported 31 sec and 55 sec it only takes ~18 milliseconds. I did check that both variables was 22,577,252 digits.

You could generate random bits for the residue instead of subtracting. Because Jacobi basically does "remove trailing 0-bits, flip around, take modulo, repeat", if the two numbers are related by a small difference the modulo loop would end much faster.

[ATH]

Originally Posted by axn

How big were these random numbers? Were they about the size of the Mp itself or some small numbers?

They were small so both the "residue" and Mp was 22,577,252 digits. That is why I'm curious it was so fast. Preda you reported it took 55 seconds and then later you showed a timing of 31 seconds:


Edit: You were right. With a random number it took ~29 seconds. Previously I had also tried dividing Mp with a small number and then subtracting random numbers, I thought that was enough to change the "residue", but I guess it was still much easier to calculate than a random number.

[R. Gerbicz]

3rd attempt to explain the algorithm. I would say somewhere I'm qualifying for the longest algorithm explanation of a 5 lines long algorithm.

Quick highlights for those who don't like math/longer reading:
1. Do you know that this algorithm isn't just doing a fermat test, but also detects the
errors at squaring with high probability, so with a saved file we can roll back to a previous state?
2. It runs with almost the same speed as for the standard LLT, but with tiny overhead of 2*p/L mulmods
(more precisely p/L mulmods and p/L squaremods).
We need an additional memory of roughly 2*p bits, to store some numbers.

-----------------------
Main Core of the Method Starts Here!!!!!!!
u[i]=3^(2^i) mod mp, for i=0..p  (with this u[0]=3)
d[t]=prod(i=0,t,u[L*i]) mod mp

d[t]=d[t-1]*u[L*t] mod mp
d[t]=3*d[t-1]^(2^L) mod mp for error checking
And Here it is Ended!!!!!!!
-----------------------

we calc. the sequence of u[] with iteration res --> res^2 mod mp
(store only res, not the whole sequence)
if i is divisible by L, then we do d=prev_d*res mod mp
if i is divisible by L^2 or (i is divisible by L and i+L>=p) then we do the actual error checking
..... if d != 3*prev_d^(2^L) mod mp (yes, here you need to do L squaremod, and one cheap mult. by 3)
............ then there was an error in squaring somewhere earlier (or here), we roll back
,,,,,else (if there was no roll back){saved_i=i;saved_u=res;saved_d=d}
if i%L==0 and not rolled back, then set prev_d=d

if u[p]=9 mod mp, then we found a prp nmuber, call the standard LLT for a true primality test.
if u[p]!=9 mod mp, then mp is composite.

To be able to roll back we store the last u[i] (in pari it was saved_u), where i is divisible by L^2
, for d we store also in a variable the last d[t] (in code it was saved_d), where t is divisible by L
(observe that i=t*L, so we stored the pair in the same iteration, it is not accidental)
and also the saved index (it was saved_i).

Additional Costs
the overhead in running time is p/L+p/(L*L)*L=2*p/L mulmods.
we need to store:
res,prev_d and d (for the d sequence calculation),saved_u and saved_d (to be able roll back)
the overhead in memory is only 2*p bits (to store prev_d and d), because we store saved_u and saved_res in file.
on disk the overhead is p bits (to store also saved_d, because you would store store for the LLT the res=saved_u, a saved residue of the LLT)
but if you would save the fermat residue regularly, say every 30 minutes, then the calculated overhead is 3*p bits in disk. (you need to store res,prev_d also, and save this after you done with the "if i%L==0 and not rolled back, then set prev_d=d")


What you (don't) understand from this alg?

Where existing software is able to identify squaring errors with such a high probability (without
the FFT's standard and costly sum-of-digits test)?
Chosen p=86243 and L=50, and making random squaring errors for i=35507 and i=35548 with 100 runs:
(if you prefer larger p values, but to be honest I see also the algorithm's goodness from smaller p values)

the test code

p=86243;errpos=vector(p,i,0);errpos[35507]=1;errpos[35548]=1;
cnt=0;for(h=1,100,cnt+=(prpmersenne(p,50,errpos,1)==9);print());cnt

the output

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=15

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=6

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=11

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=20

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=11

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

m86243 is prp.
Number of errors (corrected and) detected=0

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=6

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=7

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=10

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=8

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=8

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=13

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=6

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=6

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=4

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

m86243 is prp.
Number of errors (corrected and) detected=0

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

m86243 is prp.
Number of errors (corrected and) detected=0

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=8

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=7

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=1

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=20

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

m86243 is prp.
Number of errors (corrected and) detected=0

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=3

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=2

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=7

Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
Found error at iteration=37500, roll back to iteration=35000
m86243 is prp.
Number of errors (corrected and) detected=5

%13 = 100
?

so found ALL errors.

[error]

Originally Posted by R. Gerbicz

3rd attempt to explain the algorithm. I would say somewhere I'm qualifying for the longest algorithm explanation of a 5 lines long algorithm.

Your idea seems like a great concept.

Now we mostly need a change in the general attitude - that a 99.9% correct PRP-test is better than a 97% (or 98.5%) correct P-test.

Perhaps all future first time tests should be done this way.

This necessitates new modalities for the software(s) and the server taking care of the bookkeeping.

The core operations would remain the same.

[Prime95]

Originally Posted by error

Now we mostly need a change in the general attitude - that a 99.9% correct PRP-test is better than a 97% (or 98.5%) correct P-test.

I've been following this new error check test with interest. Bravo to R. Gerbicz.

The biggest problem with implementing such a scheme for Mersenne numbers is the massive changes that would be required outside of prime95. The server would need to track LL vs PRP residues, assign either LL double-checks or PRP double-checks as necessary, all other Mersenne programs would need work do a PRP test and report a PRP residue.

I think this makes a great deal of sense to implement in prime95's PRP code. LLR and openPFGW should as well. I think this would allow some projects to proceed faster by eliminating double-checks completely (SoB for example).

If we could convince ourselves that this scheme could produce 99.9+% reliable results, should GIMPS consider eliminating double-checking? Probably not. But maybe it would no longer be a big deal that double-checking is 8 years behind the first-time testers.

[Prime95]

Originally Posted by ATH

They were small so both the "residue" and Mp was 22,577,252 digits.

Edit: You were right. With a random number it took ~29 seconds. Previously I had also tried dividing Mp with a small number and then subtracting random numbers, I thought that was enough to change the "residue", but I guess it was still much easier to calculate than a random number.

Can you test a number that is 2x and 4x larger? From that we can see if run-time increases as O(n^2) or O(n log n).

Also, can you also time GCD for 22,577,252 digits and 2x and 4x? Thanks, I'm unable to run any tests of my own at present.

Extra credit would be to time prime95's GCD for 22,577,252 digits.

[kriesel]

Originally Posted by error

Your idea seems like a great concept.

Now we mostly need a change in the general attitude - that a 99.9% correct PRP-test is better than a 97% (or 98.5%) correct P-test.

Perhaps all future first time tests should be done this way.

This necessitates new modalities for the software(s) and the server taking care of the bookkeeping.

The core operations would remain the same.

Yes, and in brainstorming it's important to keep the positive tone.

Given the potential gain, and the probable effort required, both openness to the idea and some caution or skepticism are justified. And we did after all ask for ideas!
(Asking periodically, such as every few years, might be a good course going forward.)

And now for a bit, consider the possibilities and ramifications.

Recall that there are many separate code paths in prime95/mprime, specific to various models of Intel cpu chip, that have been carefully profiled and hand tuned in assembly code, over two decades. A lot of the knowledge gained will be applicable to the prp /check algorithm, but still the proposed switch represents a sizable investment of time in coding, debugging, profililng, tuning, documentation, QA, rollout, adaptation of primenet, etc. There is only one individual named prime95 to get the bulk of the coding, debugging, profiliing, tuning, and documentation done.

Also, there are separate programs for performing mersenne primality tests on other architectures, written and refined by others. CUDALucas & others for NVIDIA gpus, clLucas & GpuOwl for OpenCL including AMD GPUs, mLucas for a variety of cpu types, even code for ARM processors. (See the "available software" thread. http://www.mersenneforum.org/showthread.php?t=22450 )

Also there are multiple separate programs for managing work assignments and reporting the results. (See the "available software" thread.)

Since acquiring some GPUs early this year and getting into the GPU computing side of this project, I have spent man-months getting acquainted with the various applications, testing, benchmarking, documenting issues and new feature ideas, and the merest beginnings of further development. A rough estimate of what I've identified for CUDALucas and CUDAPm1 alone looks to me like a man-year or more of effort. Without implementation of new fft lengths or algorithms, which are currently way out of my depth..

There are thousands of people currently active in GIMPS (~6100 in the past year). Yet those with the necessary talent, and time, and inclination to take on any development, much less something as major as implementation of a different approach to primality testing, are a relative few (a fraction of a percent over the past 10-20 years have developed code). The developers in most or all cases are volunteers with lives and other commitments including work and family. I think they are the scarcest most precious resources of the project. It makes sense to be cautious in committing to any major task.

There are many potential applications for the programming talent; taking a few programs I'm familiar with as examples, gpuowl will soon need a longer fft length implemented; CUDALucas and CUDAPm1 input validity checking, bug fixes, logging, improved self test and customization, etc. Smaller "bite-size" tasks are more likely to get addressed. Changing the underlying algorithm occurs to me as a major undertaking.

If there was an equivalent error-checking algorithm applicable to the LL sequence, the time budget required would be lower, the chance of coming up with enough development resources higher, and the release date sooner.

My recollection is that proth / prp testing for exponent p takes longer than LL test for exponent p. (If it were not so, we'd probably already be using it.) It may be the case that prp is close enough in run time to LL for same p that it speeds up computing progress.
Status quo, LL tests:
first-test 1
double check 1
3% error rate triple check .03
occasional additional checks .0091
total ~2.04 status quo
This is under the assumption that double checks "cost the same" as first-time LL tests. Some argue they don't; that they are postponed until years later when they can be run much more cheaply. Following that argument, the performance threshold for prp to meet or beat is not 2.04 but ~1.31 (less if willing to wait longer for DC than the current DC backlog of several years).

Let's stay with the 2.04 threshold for a bit, and suppose prp takes 30% longer, than LL if "well-coded" (a quick accurate adaptation of gwnum for example, if that's possible).
prp
first test by prp 1.3
for a slim fraction 0.1%, LLtest .001
for an even slimmer fraction, double, triple, quadruple check 4e-5? (bad LL or newfound prime)
total ~1.30104

add the error check to the prp at 0.1% or even 1% additional time, assumed to take the amount of time indicated by the person proposing the method::
~1.3023 or ~1.314

Project speedup is ~2.04/1.31 = 1.56 times (56% more progress per month) And recall the "double-checks are cheaper" argument supports a considerably lesser gain, perhaps 1.31/1.3023= 1.0059x, almost a wash. If the prp/LL ratio is a bit less than the assumed 30% additional, perhaps 1.25x, it's still interesting, but much less compelling. (Double check at current DC wavefront takes about 30% of the time of an LL test at its current wavefront; any resultant triple or quad checks also)

It would make sense to prp test the untested exponents first. It would not make sense to use prp as a double check for already-LLtested-once exponents; another LL test is faster as a double check. The prp test would not help with the current multi-year backlog of exponents waiting for double checking, except as a means of limiting how many more are added to the queue per month.

Now suppose there was a generalization of the prp error checking technique that applied to any iterative b*c(*d...).-a mod n computation performed via IBDWT fft that ran in no more than 0.5% overhead and a repeat was needed 1% of the time. This would apply both to the LL test and P-1.
LL 1.005
DC 1.005*0.01=.01005
total 1.01505
status quo is about 2.03

P-1 runtime .025 (at ~100M) (anyone have a well grounded opinion of what fraction of factors get missed by P-1 due to computational error & lesser qualification of code and hardware? I'll assume 10% here)
& has probability ~.035 of saving 1.015 LL tests if correct; 10% * .035 * 1.015 is a cost estimate of P-1 error per exponent, 0.1*.035*1.015=0.003552...; new run time is .02525
(Retuning of P-1 for the change would be simple; just have primenet indicate a single LL test saved on any P-1 assignment would be very close)

Combined status quo LL + P-1 is 2.03+.025=2.055;
Hypothetical new would be 1.015*(1-0.1*.035)+.02525= 1.0367
Improvement would be 2.055 / 1.0367= 1.982 times.

And again recall the DC is cheaper argument, which supports viewing it as a considerably lesser gain, perhaps 1.31/1.0367=1.26x.

Now suppose instead the prp takes 2.1 times an LL.
2.1>the current 2.04. Using prp would be slower than LL test plus double check plus the occasional additional checks under that assumption, so would not be used.

If someone has current data on the relative run times of prp efficiently implemented and LL efficiently implemented (such as prime95 or the gpu equivalents) for p~80M or ~100M, on same hardware (cpu or gpu), please share the specifics.