Pseudoprime vs probable prime

[Bill Hart]

Hi all,

I'm getting really confused by nomenclature.

Numerous people, including the Pari devs, use the word pseudoprime to
refer to a number which is either prime or which acts like a prime in
a "primality" test. For example if I use the Fermat test that a^(n-1)
must be 1 mod n for a prime n, then any number n which passes the
test, whether prime or not, would be called a pseudoprime.

Other people reserve the word pseudoprime for a *composite* number
which passes a primality test. Primes are just, well, prime.

There is also the word probable prime. For some people, this appears
to refer to a number passing a very specific primality test, and
strong probable prime to base m has a very specific meaning indeed.
However, some people seem to use probable prime to mean what I
described above for pseudoprime, i.e. something which is probably
prime according to some test, but which may occasionally (presumably
rarely) be composite.

I had just gotten through changing all my function names in FLINT from
pseudoprime to probable prime, thinking I have them wrong. But now I
am unsure.

Is there a standard nomenclature?

Bill.

[Bill Hart]

Another possibility is that probable prime does not refer to the
number probably being prime but to the style of test used, i.e. one
which relies on random values, such as Miller-Rabin. Pseudoprime may
then be used for ...., eh, I don't know.

And strong probable prime is something else, as it definitely does not
depend on random values.

Confused.

Bill.