Finding strong pseudoprimes to several bases

Abstract

Define <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi Subscript m"> <mml:semantics> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\psi _m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to be the smallest strong pseudoprime to all the first <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> prime bases. If we know the exact value of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi Subscript m"> <mml:semantics> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\psi _m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , we will have, for integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than psi Subscript m"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">n&gt;\psi _m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi Subscript m"> <mml:semantics> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mi>m</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\psi _m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are known for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 less-than-or-equal-to m less-than-or-equal-to 8"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo> ≤ </mml:mo> <mml:mi>m</mml:mi> <mml:mo> ≤ </mml:mo> <mml:mn>8</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">1 \leq m \leq 8</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Upper bounds for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="psi 9 comma psi 10 and psi 11"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mn>9</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>10</mml:mn> </mml:mrow> </mml:msub> <mml:mtext> and </mml:mtext> <mml:msub> <mml:mi> ψ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>11</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">\psi _9,\psi _{10} \text { and } \psi _{11}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp’s) <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than 10 Superscript 24"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&gt;</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>24</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">n&gt;10^{24}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to the first ten prime bases <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 comma 3 comma midline-horizontal-ellipsis comma 29 comma"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mo> ⋯ </mml:mo> <mml:mo>,</mml:mo> <mml:mn>29</mml:mn> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">2, 3, \cdots , 29,</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which have the form <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n equals p q"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mspace width="thinmathspace"/> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n=p\,q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p comma q"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>q</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p, q</mml:annotation> </mml:semantics> </mml:math>