# Generating DataSet of Strong PseudoPrimes?

Is there a C/C++ library for Number Theory that helps generate a Strong PseudoPrimes w.r.t. an Input base.

I intend to test a Primality Testing Algorithm's performace stastically but I am struggling with a dataset of Strong PseudoPrimes and was unable to find one of Random Strong PseudoPrimes large enough.

Finally, note that the website factordb.com maintains a list of numbers that pass a surprisingly large number of iterations of the Miller-Rabin test before failing one. This list might be useful to you, and Arnault (in "Constructing Carmichael Numbers Which are Strong Pseudoprimes to Several Bases") gave an example of a 397-digit composite number for which the smallest strong liar is is $307$.
• It is quite likely that there is a short cut. If you only want spsp's for one base $a$, you could look for composite factors of $\Phi_{n}(a)$ that are relatively prime to $n$ (where $n$ is odd and $\Phi_{n}(x)$ is the $n$th cyclotomic polynomial). For example, $N = 407613774637837876811$ is an spsp to base 3 because it is a composite factor of $\Phi_{65}(3)$. – Jeremy Rouse Sep 16 '16 at 17:26
• If you want multiple bases, you could search for $n = p(2p-1)$ where $p \equiv 3 \pmod{4}$ is prime and $2p-1$ is also prime. For such an $n$, one quarter of the bases $a$ will be strong liars, so your chances are good. – Jeremy Rouse Sep 16 '16 at 17:28