PRP residues

[Keroberts1]

Exactly what are these for? I understand that by comparing them you can eliminate the chances that a test could have returned a wrong result but can they in any way be used to hurry up the testing process? It seems like an aweful waste of time ot retest everything but at the same time if we had missed a prime that would have again been such a waaste of effort no all of the test that would have been done in the mean time. I don't know any of the mat hbehind it so I'm just thinking outloud here. if anyone feels the need to explani any of the math behind the prp test I'd be willing to read the post at least. But i of course dont' expect anyone to do it. I just wish i could understand some of the things that people talk about in some of the client threads.

[MJX]

hello

as i understand it :
prping involves floating point operations that are rounded at every fft exponentation step. Roundoff errors may occur and a prp result may be a false negative (in the gimps project, double checking shows that more than 1,5 % (and sometimes up to 4% around fft size limits) of the results are erroneous). Double checking permits to check the correctness of the results by comparing the two residues (a signature depending of all the previous steps of the calculus). The probability that two erroneous runs produces the same residue (every time you start a test in gimps, initial conditions are slighty perturbed so that a bug can't have the same effect on two computations) is almost zero so you have 2 configs :
- the two residues matches > all is ok and the number is composite with an extremely high level of confidence.
- the two residues differs > one of the run was wrong (maybe the two)> redo.

missing a prime in the 1,5 millions digits range may be a lost of many, many cpu years so checking results is important.

hope this is understandeable. try to have a look at the gimps project for other explanations...

Best regards.

Philippe.

[Keroberts1]

i believe i understand the idea of the error ratio i was just curious if there was any way to run the test faster now that the residue is already available. Perhaps stopping halfway throug hwhen it appears sufficient that they are going to be the same

[MJX]

the proth test or ll test response is a one bit response : yes this number is prime or no. it relies on many modular exponentiations. if the last one is false then the result is false. so, if you have 10 million steps, the residues are the same until an error occurs (maybe in the lastest ones, see the false announcement of the 40th mersenne number at gimps, due to a computation error).

I know an article called "f24.pdf" about the compositness of the 24th fermat numbers (title : "the twenty fourth fermat number is composite", from R Crandall, E Mayer...). It says that some kinds of fft residues may permit to verify the integrity of the computations (determinisitic chain) without using fft transforms (without roundoff errors) and without redoing the whole test. This verification is certainly not sufficient because they have done the computations two times in parrallel with two different machines and softwares, comparing the final residues... I must say i didn't really understand the maths in the paper and don't know if such "deterministic chains" are feasible for proth test...:rolleyes:

I join the first page of the article (postscript zipped) so that you can read the summary and see if you want to download the whole article (found with google)

goodbye.

Philippe.