# Constructing a number strong probable prime to several bases

See here https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test for the definition of a strong probable prime, where it is also mentioned that Arnault constructed a number being strong probable prime to many bases (A version of maple declared the number to be prime!)

Is there an easy way to construct such numbers, for example a number strong probable prime to the bases $2-1000$ ? It would already be nice to see Arnaults number (I did not find it online), but I would like to construct my own numbers.

A promising approach are the numbers of the form $N=(4k-1)(8k-3)$, where both $4k-1$ and $8k-3$ are prime. It can be shown that such numbers have the minimum number of witnesses (exactly $75$% of the numbers coprime to $N$), but it is difficult to make the smallest witness large.

Can anyone help ?

Additional question : If $p$ is a prime, is there a known estimate for the smallest number which is strong probable prime to every base $q$ with $q$ prime and $q\le p$ (I do not demand the number to be strong-probable prime to every base $\le p$) ?

• Near the end of: github.com/danaj/Math-Prime-Util-GMP/blob/master/t/… you can find a number of examples, including a couple of Arnault's examples. Bleichenbacher's paper is also useful, and there are some relatively simple ways of finding examples to not too many bases (e.g. all bases under 100). It gets harder as the number of desired bases increases. – DanaJ Oct 29 '15 at 1:09
• Just pointing out that the file referenced above has an example composite which is a strong probable prime to all bases 2-1008. That trips up a lot of software using the obsolete "first n prime bases" method including libtommath. – DanaJ Oct 29 '15 at 1:13

Arnault's paper is here. He gives a method for constructing numbers that are strong pseudoprime (PSP) to a given set of bases. However, he doesn't find all such strong PSPs; he only finds those that are a product of two distinct primes of a certain form.

You may also be interested in a paper by Jaeschke. He tried to find the smallest such strong PSP to a given set of bases.

One note of caution: his construction is for square-free examples only. In order to conclude that the smallest square-free strong pseudoprime is the smallest one period, one needs to exclude pseudoprimes with a square divisor. But if a square divides a pseudoprime to some base, that divisor is a Wieferich prime to that base. Jaeschke noted that the next smallest base-2 Wieferich prime larger than 3511 was larger than $10^9$ (at the time he wrote the paper). That squared is $10^{18}$, and his searches for strong pseudoprimes to 8 or fewer bases were below that. For 9, 10, and 11 bases, the smallest he found was larger than that so he only concludes these are upper bounds. Since computer searches have pushed that limit on the next-smallest Wierferich prime to over $10^{17}$ (and thus the square to $10^{34}$), the candidates that Jaeschke found are indeed the smallest strong PSPs.