Possible error in PRP calculation or server display

[alpertron]

From the information given in Primenet for M3416453, it shows that the PRP residue of M3416453/39603523177 is equal to the PRP residue of M3416453/39603523177/27070715752699810127.

Is this an error on Prime95 or in Primenet? There is a very low probability that all 64 bits of the residue match.

[GP2]

Originally Posted by alpertron

Is this an error on Prime95 or in Primenet? There is a very low probability that all 64 bits of the residue match.

This is a property of Type 5 residues. The numerical value of the residue remains unchanged, so older results with fewer factors can act as a double-check for the newer result.

[alpertron]

Where can I find information on how these type 5 PRP residues are calculated?

[Prime95]

From the C code:

// There are (at least) 5 PRP residue types for testing N=(k*b^n+c)/d:
#define	PRIMNET_PRP_TYPE_FERMAT		1	// Fermat PRP.  Calculate a^(N-1) mod N.  PRP if result = 1
#define	PRIMNET_PRP_TYPE_SPRP		2	// SPRP variant.  Calculate a^((N-1)/2) mod N.  PRP if result = +/-1
#define	PRIMNET_PRP_TYPE_FERMAT_VAR	3	// Type 1 variant,b=2,d=1. Calculate a^(N-c) mod N.  PRP if result = a^-(c-1)
#define	PRIMNET_PRP_TYPE_SPRP_VAR	4	// Type 2 variant,b=2,d=1. Calculate a^((N-c)/2) mod N.  PRP if result = +/-a^-((c-1)/2)
#define	PRIMNET_PRP_TYPE_COFACTOR	5	// Cofactor variant.  Calculate a^(N*d-1) mod N*d.  PRP if result = a^(d-1) mod N.  (d is product of known factors)

[alpertron]

OK. I understand it now the type 5 PRP. Very clever.