View Single Post
Old 2021-06-17, 20:51   #16
Viliam Furik
Viliam Furik's Avatar
"Viliam Furík"
Jul 2018
Martin, Slovakia

32·79 Posts

Originally Posted by JuanTutors View Post
(from another thread)

Please see my above post where I modified my suggestion. As you see above I suggested performing the PRP test with 3^(2pE) instead of with 3, and then stopping at the m = millionth or so iteration and taking GCDs of 3^(2pE(2^m+k)) for various well-chosen values of k.

There are alternate variations of this, but to answer your question, which was, take the GCD and then ... what? If the GCD is not 1, we know that a factor exists from the test, and therefore Mp is not prime. Yes, its' true that we will not know the factor of Mp, because we will not know the factors of 2^m+k, but we will know that Mp is not prime, which has always been the goal of the PRP test. We could, in the future if motivated, factor 2^m+k for as long as it takes to find that factor of Mp, or not.
Do we need to factor the 2^m+k? It's my understanding of GCD that if for any number, in this case, some power of 3, we do GCD of it (minus 1) and the Mersenne number, and we get result other than 1, the result will directly be a factor of Mersenne number, per definition of GCD. If the factor isn't the Mersenne number itself, we are good.

It sounds like a reasonable feature if it works as promised.

Using the PRP test as a free booster to speed up the ride is a great idea, IMO. If we start the test with a modular residue of 3^(2*p*E), where E is computed using B1=1,000,000, and we compute the entire PRP test with this value, what we get in the end is 3^(2*p*E*(2^p-1)), which can still give us a factor, and has the added benefit of determining PRP, because if Mp is prime, then the residue of 3^(k*(2^p-1)) is still 3 (mod 2^p-1). However, in the case of a composite, residues will no longer match for different runs, i.e. with different B1 sizes, but certification should still be possible because we are still doing the same test, but with a different starting value (others should correct me on that if I am wrong because I'm not sure).

It could also be done the other way around. First, perform the PRP test. Then, use the residue in P-1, instead of 3.

As I think about it, it is quite possible it will give no benefit, one way or the other. I think that the only way it could benefit the P-1 would be when the 2^m+k would have just the right factors that are higher than B1.

What do you think?
Viliam Furik is offline   Reply With Quote