Getting reliable LL from unreliable hardware

[preda]

Originally Posted by Prime95

Challenge #2
We've convinced ourselves that a Gerbicz PRP reduces the chance of a hardware error to practically zero. We can use checksums to reduce human error in posting results to near zero.

Is there any way to reduce the malicious user error to near zero? I'm trying to imagine some side calculation that the user reports that can be quickly verified but can only be generated if the user did the full PRP test. If such a test existed I'd consider accepting Gerbicz PRP tests as a primality test that did not require a double-check.

The solution is not as elegant as I'd like, but maybe its an idea to be improved upon ("brainstorming")

The goal is:
the client states that he computed 3^(2^p). We want to verify this by doing less work than 100% all over again (which would be a classical double-check).

In brief, the client sends a complete (but sparse) "Gerbicz chain". This chain can be probabilistically verified by the server in [much] less than 100% time.

Now, in a bit more detail:
choosing a step "L" of the chain.
the client sends the N "data bits" at all the Gerbicz points of step L:
d0 = 3^(2^L)
d1 = 3^(2^(2L))
etc., up to
d(N) = 3^(2^(N*L)), such that N*L > exponent.

The server can easily compute the corresponding "check bits" of the chain with N multiplications:
c0 = 3
c(k) = d(k-1) * c(k-1)

And the server can verify any link it chooses in this chain with L multiplications:

c(k-1)^(2^L) * 3 == c(k)

The important point of this probabilistic verification is: if the client spent much less that 100% time to produce the fake data, the server will detect it in exponentially less than 100% time too.

A sizing example:
for a 90M exponent, choosing L = 10M, we have a chain with 10 links.
The client sends 10 "data bits" blocks (each 13MB in size).
The server computes the 10 "check bits" with 10 multiplications (trivial).
The server [randomly] chooses a link (among the 10) to verify, and verifies it with L multiplications (10% of the total-work-time).

Assuming the client faked everything, at this point the server detects the fake. Assuming the client did invest 10% of the full-work-time and computed one link genuinely, the server has 90% chances to detect the fake at this point.

After a successfully verified link, the server can verify a second random link.

There is a trade-off between the amount of data the client sends to the server (the "data-bits" for each of L links) and the amount of compute the server has to do (less verification work with lower L).

[preda]

Before others point this out, I am aware, as per past discussion, that having the client send large amounts of data to the server may be a problem.

My point is: IMO, this is what is needed/required in order to do "fake checking" in less time than a double check; it may not be practical though.

Or maybe somebody proposes a better solution..

[henryzz]

Is this equivalent in size to sending save files?

[kriesel]

Originally Posted by henryzz

Is this equivalent in size to sending save files?

Yes, nearly; multiple checkpoint files per exponent; at 4M fft length, gpuOwL v1.9 save files are about 19MB each, vs. the 13MB he stated for Gerbicz data for 91M (presumably for V2.0). Ten 13MB files is about comparable to 7 of the 4M save files.

It might be practical to do it more concisely. by a factor of 2 or so. clLucas checkpoint files are rather large; 28.6MB for M62.8m., vs. gpuOwL v 1.9 at 19MB for M78m; CUDALucas 2.06 10.2MB at M83.6m. Those correspond to clLucas 0.455B/p; gpuOwL 0.244B/p; CUDALucas 0.122B/p; relative size 3.73, 2, 1.

[GP2]

Do we have a rough theoretical idea of the odds of a bad PRP result despite Gerbicz error checking? I wonder if it might be higher than expected.

There are about 340,000 PRP cofactor results for exponents under 4.5M where the shift count is nonzero. That reduces to 190,000 results if you exclude the ones done by me using AWS cloud servers with ECC memory which so far have a perfect track record for a few thousand LL double-check tests.

Out of those 190,000 results, there are two bad results that I'm aware of:

• M3,866,963
• M4,437,113

There are three more bad results with zero shift count (M37,811, M1,132,997 and M3,167,573) but I'm not counting these since these were presumably done with an older version that didn't do Gerbicz checking.

Two erroneous results out of about 190,000 = 1 in 95,000 which isn't bad at all, but these are for the very small exponents in PRP cofactor testing. For the much larger exponents used in PRP primality testing, would that imply a correspondingly higher error rate?

Would the error rate go up roughly linearly with the exponent size, or would it increase a bit more than quadratically, as the calculation time does?

So the error rate of 1 in 95,000 for tiny exponents under 4.5M might balloon to, say 1 in a few thousand, or even more, for exponents in high 70M range. That would be too many to allow us to avoid double-checking.

This needs more data, but the PRP cofactor double-checking wavefront is only at about 4.7M at the moment. And for PRP primality testing itself, we only have less than 200 double-checked results at the moment.

[axn]

Originally Posted by GP2

Out of those 190,000 results, there are two bad results that I'm aware of:

• M3,866,963
• M4,437,113

Was Gerbicz PRP checking implemented with Type 1 residues? I thought only Type 5 was using that check?

Or maybe all Types are possible with that check

[GP2]

Originally Posted by axn

Was Gerbicz PRP checking implemented with Type 1 residues? I thought only Type 5 was using that check?

Older versions of mprime/Prime95 only implemented Type 1, and didn't do Gerbicz checks.

The latest versions do Gerbicz checks.

If it's a PRP cofactor test, they mostly do Type 5 now but will do a Type 1 if it's a double check of a Type 1 first time result.

If it's a PRP primality test, they mostly do Type 1 unless it's a double-check of a very early gpuOwL result, which used Type 4.

So I think Gerbicz checks are indeed done for Type 1.

[axn]

Originally Posted by GP2

So I think Gerbicz checks are indeed done for Type 1.

Ok. How can we be sure that these particular tests had Gerbicz check done? Are all P95 versions capable of getting Cofactor tests from primenet also set to do Gerbicz check? Or are there exceptions?

[Prime95]

Type 1 does not do Gerbicz error-checking.

[GP2]

Originally Posted by Prime95

Type 1 does not do Gerbicz error-checking.

But I'm looking at preda's recent PRP primality tests, for example for M78424979, and they are all Type 1. And gpuOwL has implemented Gerbicz checks since v 1.0 last August.

Or does Type 1 mean something different for PRP primality vs. PRP cofactor testing?

[axn]

Originally Posted by GP2

But I'm looking at preda's recent PRP primality tests, for example for M78424979, and they are all Type 1. And gpuOwL has implemented Gerbicz checks since v 1.0 last August.

Or does Type 1 mean something different for PRP primality vs. PRP cofactor testing?

Found it. http://www.mersenneforum.org/showthr...due#post468378

Type 5 is specifically for cofactor, and uses "Gerbicz check"-friendly math. Type 1 is applicable for all, but is not GC-friendly for mersenne cofactors.