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).