View Single Post
Old 2005-12-06, 22:17   #11
alpertron's Avatar
Aug 2002
Buenos Aires, Argentina

31×43 Posts

The following is my interpretation of the original poster requirements.

Suppose that we want to run the algorithm in reverse, starting with Sp-2 = 0 (supposing that the number is prime) and we know how to perform the modular square root at the same speed as multiplication (of course, if you know such a method, please let me know).

So the original poster wants to start computing S0 = 4, S1, S2, etc. and at the same time Sp-2 = 0, Sp-3, etc. up to S(p-3)/2. Then we check whether both numbers are equal and if they are, the Mersenne number in question is prime.

I think there is a big problem here. What of the two square root do we have to compute in the reverse computation? It appears that there are two possible values of Sp-3, four values for Sp-4, eight values for Sp-5, etc. How do we know which is the correct one?
alpertron is offline   Reply With Quote