-
Notifications
You must be signed in to change notification settings - Fork 35
Home
The [[Great Internet Mersenne Prime Search|https://mersenne.org/] is searching for the next Mersenne prime, which would become the new largest known prime. The search is a distributed computing effort, where participants work through a list of candidates and test them for primality, sendig the result of the test to a central server.
Because the server can't trust either the correctness of a result (which may be affected by software or hardware errors) or the sincerity the user (who may, theoretically, attempt to manufacture a fake result), every result must be verified. The factor-found results (produced through trial factoring (TF) or P-1 testing) are easy to verify and are checked by the server. On the other hand, the Lucas-Lehmer (LL) and the [[Probable-prime (PRP)|PRP-test-for-Mersenne-numbers] results are at the moment validated by re-executing the test, independently by another user, and comparing the outcome. This re-doing of the test is called a double-check (DC) and of course represents an expensive price to pay for confidence in the result correctness.
The Lucas-Lehmer test is able to establish the primality of a Mersenne candidate (deciding between composite and prime) while the PRP test is able to establish only the compositeness of a candidate (deciding between composite and probable prime). OTOH the PRP test can be validated during its execution, which offers strong protection against hardware and software errors thus represents a major advantage over the LL test. In the following we're going to focus exclusivelly on the PRP test (and ignore the LL test).
Recently, the research on VDF (Verifiable Delay Functions) raised the possibility of a compact proof of a PRP result, see in particular Pietrzak's paper.
In the PRP-proof setup, the tester, in addition to running the PRP test, is also constructing a proof of the PRP result. The proof can later be verified by an independent verifier with only a fraction of the cost of running the PRP test again. The verification of the proof can be seen as a cheap double-check of the PRP test.
See more details about the proof file format and the proof verification algorithm.