1

Given an odd integer n ≥ 5, and a base 2 ≤ a ≤ n-2, $a^{n-1} = 1 \mod n$ whenever n is a prime, and whenever the result is not 1, n is composite. Plus composite numbers where the result is 1 are rare. A composite number passing this test is a "pseudo-prime" or "Fermat pseudo-prime". There are slightly more clever tests producing "Euler pseudo-primes" or "Miller-Rabin pseudo-primes".

I have always been told that one should take a prime number a as the basis in these tests, not a composite number. And it is easy to show that taking a square $a^2$ gives weaker results. However, I tried to find sets of three bases where the smallest number that is a pseudo-prime to all three bases is as large as possible, and composite numbers seem to give good results, for example there is no $n < 2^{32}$ that is a Rabin-Miller pseudo-prime to bases 13, 18 and 35.

Question: Is there a reason to avoid composite numbers as bases when testing whether numbers are pseudo-primes to multiple bases or is that just folklore? Should we avoid bases with common divisors?

BTW. 25,326,001 is a Miller-Rabin pseudoprime to bases 2, 3 and 5, so that's at least 180 times worse than 13, 18 and 35.

gnasher729
  • 10,113
  • You only have to worry about avoiding perfect power bases. In particular, if the base $a$ is composite, then pseudoprimality works in the exact same way: avoiding common divisors is something one must do for prime bases $a$ as well, just confirm $\gcd(a,n)=1$ before doing the pseudoprimality test. Perfect power bases lessen the efficacy of the test. – Tejas Rao Feb 27 '23 at 16:42
  • Did you mean $n$ where you typed $p$ in the first line? – J. W. Tanner Feb 27 '23 at 16:56
  • 1
    @J.W.Tanner Fixed. – gnasher729 Feb 27 '23 at 22:30
  • @TejasRao Running the test blindly when gcd(a, n) > 1 will always report n as "composite". That is useless, but only wrong if n is a prime. So I just check whether n <= a and n divides a. If only primes are used for the base a, then you only need to check whether a = n. – gnasher729 Feb 27 '23 at 22:44
  • @gnasher729 there is a fast gcd algorithm that allows one to compute $gcd(a,n)$ without knowing the factors of $n$ in about as long as it takes for one step of multiplication. – Tejas Rao Mar 01 '23 at 15:55

1 Answers1

0

There is no need to choose primes as bases. Some composites are even better than primes: there are 19322 strong pseudoprimes with bases 2 and 3 below $10^{15}$ but only 14623 with bases 2 and 15. The results are similiar with several multiples of 15, e. g. 1215 and 735.

15283202437 is the lowest strong pseudoprime with bases 2, 453 and 735; $453 = 3 \cdot 151,\ 735 = 3 \cdot 5 \cdot 7^2$.

Strong pseudoprimes base $a$ are composite numbers that pass the Miller-Rabin test base $a$.

Eberhard
  • 158