View Single Post
Old 2019-03-14, 00:45   #8
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

7×983 Posts
Default PRP residue types

Woltman describes and discusses PRP residue types 1 through 5 in https://www.mersenneforum.org/showpo...&postcount=209
Quoting in part: "Here is my PRP residue proposal:

There are (at least) 5 PRP residue types:
1; Fermat PRP. N is PRP if a^(N-1) = 1 mod N
2: SPRP variant, N is PRP if a^((N-1)/2) = +/-1 mod N
3: Fermat PRP variant. N is PRP if a^(N+1) = a^2 mod N
4: SPRP variant. N is PRP if a^((N+1)/2) = +/-a mod N
5: Fermat PRP cofactor variant, N/d is PRP if a^(N-1) = a^d mod N/d

I encourage programs to return type 1 residues as that has been the standard for prime95, PFGW, LLR for many years."

Note there is also a type 0, associated with gpuowl PRP-1 runs (combined PRP and P-1), involving computing powers of a base other than 3, mod Mp. https://www.mersenneforum.org/showpo...postcount=1005
https://www.mersenneforum.org/showpo...postcount=1006


Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1

Last fiddled with by kriesel on 2019-11-19 at 16:06
kriesel is offline