What does 3-PRP means exactly ? (in pfgw primality test)

Question

When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP.

1: What does 3-PRP means exactly?
2: What is the error ratio?
3: When the test return Composite, does it mean "probably composite"?

Answer 1

1. It means it is a base 3 pseudoprime, i.e. it passes a Fermat test for base 3: $3^{n-1} = 1\pmod n$.

   I agree this finding the test type is not obvious. I looked in gw_prp.cpp to see the test, as the documentation doesn't seem really explicit. It is also noted on the Wikipedia page for Fermat primality test. I just verified it with some base-3 PSPs that are not base-3 SPSPs.

2. There is typically trial factoring done before, which greatly reduces the error rate. E.g. 1000067795191 with only report 3-PRP if "-f 0" is used to turn off trial factoring. But 100000185552877 will report as 3-PRP using the default trial factoring.

   For the probability of the test itself, I will defer to Kim and Pomerance (1989). For general purpose use, we would normally want something much stronger (e.g. BPSW), but PFGW typically is using this test for quite large numbers where the probabilities are vastly smaller. Given the speed of the underlying gwnum library and the PFGW implementation, it makes an excellent pre-test for multi-thousand digit numbers.

3. Like most useful compositeness tests (often called probable prime tests), the possible answers are:

   • Composite. Barring implementation bugs, this is 100% correct.
   • Definitely prime. If this is returned, it is 100% correct.
   • Probably prime. It passes this test, which may be more or less stringent.
   • Error. This test may be inappropriate for the input, or we can't understand the input, or our algorithm has failed somehow. In these cases this is a far better return value than any of the above.

   While it is possible to construct tests that give "probably composite" as a possible result, that is generally not useful. I can't think of any examples in common use.