Getting reliable LL from unreliable hardware

[LaurV]

Originally Posted by kladner

Please don't put altered, confusing titles on technical threads.

+1. We really appreciate moderators' fine humor (almost) every time when a thread gets renamed, but we thought this goes only for the misc math or lounge...

[VBCurtis]

I'm a fan of the RDS ecm-thread renaming, gotta say. This one gave me a smile too!

[R. Gerbicz]

Found a likely new, fast, high reliability error detection algorithm (with some restriction)
for Fermat and LLT test's interim or final residue.

Say we know res=a^e mod N or res'=LLT(x0,N,k) [applied k LL iterations starting from x0], and a non-trivial d divisor of N.

Calculate res2=a^e mod d or res2'=LLT(x0,d,k), then the error check is: the obvious res==res2 mod d [in the LLT case res'==res2' mod d] should be true. Since d is small, usually d<10^200, we can get quickly res2 (or res2') if we update at each iteration res2 or res2' (see later an improvement on this).

Ofcourse in this case we should store the full res (so RES64 is not enough), and you have to know d.
It is useful if we find a divisor of N, and we would like to test N/d, because in this case we are in the above situation, if res!=res2 mod d (or res'!=res2'), then there was an error in computation (or in the database). Or in some cases we are already in this setup, because we wanted to test N/d=(k*b^n+c)/d , say N/3=(2^p+1)/3.

For the Fermat case we can reduce further the problem using Euler-Fermat if gcd(a,d)=1 then a^e==a^(e mod eulerphi(d)) mod d.

Since the computation of res mod d takes at least linear time use the error checking say per 10000 iterations. In Fermat case if you are using the previous trick then it is not needed to store at each iteration a^e mod d, in LLT case update x at each iteration using modulus=d.(though there could be also a shortcut here).

This detects the error with high, roughly 1-(1/d) probability.

[GP2]

Originally Posted by R. Gerbicz

Found a likely new, fast, high reliability error detection algorithm (with some restriction)
for Fermat and LLT test's interim or final residue.

This post never got any reaction or followup. I wonder if all the program authors simply have enough on their plate already, finishing up the implementation for Mersenne number testing.

[LaurV]

Originally Posted by GP2

This post never got any reaction or followup. I wonder if all the program authors simply have enough on their plate already, finishing up the implementation for Mersenne number testing.

That may be exactly the effect of thread title morphing...
Not all people have free time on their hands (like us ) to read all topics regardless of title...

[preda]

Originally Posted by R. Gerbicz

Found a likely new, fast, high reliability error detection algorithm (with some restriction)
for Fermat and LLT test's interim or final residue.

Say we know res=a^e mod N or res'=LLT(x0,N,k) [applied k LL iterations starting from x0], and a non-trivial d divisor of N.

My observation is this:
In LL testing, we do a^e mod N, where N is the "mersenne candidate", to find out whether N is prime or not.

The proposed check here requires to have a "non-trivial d divisor of N". If I have such a divisor, I don't have to run LL anymore because I already know N is not prime.

[preda]

I did a simple analysis to find the optimal frequency of the "Gerbicz check" in presence of errors.

I modeled it like this: I have the "Gerbicz step" L = 1000 fixed, and I can verify at any multiple of L iterations. I want to find out the value k that is optimum for verification at every k*L iterations, given the probability p that one step of L iterations fails.

Assuming p is small, we approximate the prob. of "at least one error in k steps" with k*p.

I call a "block" a sequence of k steps, followed by one more step for verification.

The cost of one block is k*L + L if there is no error. But if there is an error detected at the end of the block, the whole block must be repeated. The probability of a repeat is k*p.

So, the cost of one block is approximated:
block cost = k*L + L + k*p*(k*L + L)
(assuming at most one repeat per block).

Re-defining the "block cost" in multiples of k*L iterations, we have:

block cost = 1 + 1/k + k*p + p

So, the optimum k is reached when 1/k + k*p is minimized, which is reached when 1/k == k*p.

This has an intuitive interpretation: the optimum check frequency is reached when the check overhead (1/k) is equal to the repeat overhead (k*p).

And a small table. The "p" is the probability of having an error in L (=1000) iterations.

p                           k
-----------------------
1%                10
0.1%              30
0.01%           100
0.0001%      1000

[kriesel]

Originally Posted by LaurV

That may be exactly the effect of thread title morphing...
Not all people have free time on their hands (like us ) to read all topics regardless of title...

That's one factor. Another is it is simply a busy time of year. Another is many other code improvements (of smaller scope) have already been identified; the queue is quite deep. Another, at least for me, and perhaps for other non-mathematicians too, is Mr. Gerbicz's useful and novel posts can be hard to understand and absorb.

[kriesel]

Originally Posted by R. Gerbicz

Found a likely new, fast, high reliability error detection algorithm (with some restriction)
for Fermat and LLT test's interim or final residue.

Say we know res=a^e mod N or res'=LLT(x0,N,k) [applied k LL iterations starting from x0], and a non-trivial d divisor of N.

Calculate res2=a^e mod d or res2'=LLT(x0,d,k), then the error check is: the obvious res==res2 mod d [in the LLT case res'==res2' mod d] should be true. Since d is small, usually d<10^200, we can get quickly res2 (or res2') if we update at each iteration res2 or res2' (see later an improvement on this).

Ofcourse in this case we should store the full res (so RES64 is not enough), and you have to know d.
It is useful if we find a divisor of N, and we would like to test N/d, because in this case we are in the above situation, if res!=res2 mod d (or res'!=res2'), then there was an error in computation (or in the database). Or in some cases we are already in this setup, because we wanted to test N/d=(k*b^n+c)/d , say N/3=(2^p+1)/3.

For the Fermat case we can reduce further the problem using Euler-Fermat if gcd(a,d)=1 then a^e==a^(e mod eulerphi(d)) mod d.

Since the computation of res mod d takes at least linear time use the error checking say per 10000 iterations. In Fermat case if you are using the previous trick then it is not needed to store at each iteration a^e mod d, in LLT case update x at each iteration using modulus=d.(though there could be also a shortcut here).

This detects the error with high, roughly 1-(1/d) probability.

Please elaborate on what are the restrictions, for the case of an LLT of a mersenne number for which the factorability is unknown. (The usual trial factoring and P-1 factoring attempts have been made and yet the primality vs. factorability is unknown.)

[R. Gerbicz]

Originally Posted by preda

The proposed check here requires to have a "non-trivial d divisor of N". If I have such a divisor, I don't have to run LL anymore because I already know N is not prime.

That is correct.
But it is also a possible case that you discover the d divisor of N after a completed LL/Fermat test, in this case ofcourse you don't need a 2nd test, but with this d you can quickly see if the (stored) full residue was good or not with high probability, hence you can find bad residues/computers.

Not written, but trivially with this algorithm if you know a non-trivial divisor of N, then in the first stage of the P-1 factorization method you have a rather quick error check! (if d<<N then it is a cheap test)

Originally Posted by kriesel

Please elaborate on what are the restrictions

The "only" restriction is that you should know a non-trivial divisor of N, you should know this before or after(!) the test.

[kriesel]

Originally Posted by R. Gerbicz

Not written, but trivially with this algorithm if you know a non-trivial divisor of N, then in the first stage of the P-1 factorization method you have a rather quick error check! (if d<<N then it is a cheap test)

The "only" restriction is that you should know a non-trivial divisor of N, you should know this before or after(!) the test.

Re your P-1 comment above, that might be very useful for those seeking multiple factors of known composites, by employing P-1 to seek factors larger than are practical with the fastest available trial division.

Re the restriction, that's a big one, for the common general case of unknown primality LL test. Now, if you found a way to remove the restriction, maybe we would start to call it the Lucas-Lehmer-Gerbicz test!

Thanks, and keep the insights, comments, and clarifications coming!