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

7×983 Posts
Default PRP residue types

Woltman describes and discusses PRP residue types 1 through 5 in
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.

Top of reference tree:

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