Efficient method to find the strong pseudoprimes to base $2,3,5$ upto $10^9$

Question

A composite number $n$ is a Fermat-pseudoprime to base $a$, if

$$a^{n-1}\equiv\ 1\ (\ mod\ n)$$

If $n-1=2^s\times t$ , $t$ odd , $n$ is a strong a-PRP, if either $2^t\equiv 1\ (\ mod\ n)$ or there is a number $u$ with $0\le u<s$ and $\large 2^{2^u\times t}\equiv -1\ (\ mod\ n\ )$

I want to find the composite numbers, which are strong PRP to the bases $2,3,5$ upto , lets say , $10^9$ in an efficient way (faster than just check all the composite numbers).

Is this possible ? If yes, how ?

Answer 1

Indeed, there are much faster methods than exhaustive search. Here are two references:

Zhenxiang Zhang, Finding strong pseudoprimes to several bases, in Math. Comp. 70 (2001)

Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases II, in Math. Comp. 72 (2003).

Answer 2

Follow the links in fgrieu’s answer.

The obvious method would be to check all odd composite numbers from 9 to 999,999,999. You’d use a sieve to find all the non-primes. This is not the fastest method, but doesn’t take very long.

Zhang’s paper shows how to find a much smaller number of composite numbers that might be strong pseudoprimes. He picks numbers k > 1, then picks primes q such that q is larger than the largest prime factor of k, and kq < 10^9. He also cites other papers that show the first strong pseudo prime that isn’t square free must be very large. Basically, such a pseudo-prime must be greater than the square of a Wieferich prime, but the first two Wieferich primes don’t produce a Pseudoprime that isn’t square free, and the third Wieferich prime is greater than 2^64. We don’t know what it is, so there might be numbers > 2^128 that are not square free.

So he vastly reduces the search space, but has to use brute force within that search space. The more conditions you have (like being Pseudoprime to 12 bases), the more you can reduce the search space using his paper. For pseudoprimes to three bases up to 10^9 you don’t need it. For a larger range you need that paper.

Answer 3

Here's a decently fast implementation: Try it online!

It takes less than 1 minute to find the terms: 25326001, 161304001, 960946321.