Strong primality tests that are not sufficient

Abstract

A detailed investigation is given of the possible use of cubic recurrences in primality tests. No attempt is made in this abstract to cover all of the many topics examined in the paper. Define a doubly infinite set of sequences<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis n right-parenthesis"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">A(n)</mml:annotation></mml:semantics></mml:math></inline-formula>by<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis n plus 3 right-parenthesis equals r upper A left-parenthesis n plus 2 right-parenthesis minus s upper A left-parenthesis n plus 1 right-parenthesis plus upper A left-parenthesis n right-parenthesis"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>3</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>r</mml:mi><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>−</mml:mo><mml:mi>s</mml:mi><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">A(n + 3) = rA(n + 2) - sA(n + 1) + A(n)</mml:annotation></mml:semantics></mml:math>\]</disp-formula>with<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis negative 1 right-parenthesis equals s"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>s</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">A( - 1) = s</mml:annotation></mml:semantics></mml:math></inline-formula>,<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis 0 right-parenthesis equals 3"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>0</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mn>3</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">A(0) = 3</mml:annotation></mml:semantics></mml:math></inline-formula>, and<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis 1 right-parenthesis equals r"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>r</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">A(1) = r</mml:annotation></mml:semantics></mml:math></inline-formula>. If<italic>n</italic>is prime,<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis n right-parenthesis identical-to upper A left-parenthesis 1 right-parenthesis left-parenthesis mod n right-parenthesis"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>≡</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mspace width="thickmathspace"/><mml:mspace width="0.667em"/><mml:mo stretchy="false">(</mml:mo><mml:mi>mod</mml:mi><mml:mspace width="0.333em"/><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">A(n) \equiv A(1)\;\pmod n</mml:annotation></mml:semantics></mml:math></inline-formula>. Perrin asked if any composite satisfies this congruence if<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r equals 0"><mml:semantics><mml:mrow><mml:mi>r</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">r = 0</mml:annotation></mml:semantics></mml:math></inline-formula>,<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s equals negative 1"><mml:semantics><mml:mrow><mml:mi>s</mml:mi><mml:mo>=</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">s = - 1</mml:annotation></mml:semantics></mml:math></inline-formula>. The answer is yes, and our first example leads us to strengthen the condition by introducing the "signature" of<italic>n</italic>:<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis negative n minus 1 right-parenthesis comma upper A left-parenthesis negative n right-parenthesis comma upper A left-parenthesis negative n plus 1 right-parenthesis comma upper A left-parenthesis n minus 1 right-parenthesis comma upper A left-parenthesis n right-parenthesis comma upper A left-parenthesis n plus 1 right-parenthesis"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo>−</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>,</mml:mo><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">A( - n - 1),A( - n),A( - n + 1),A(n - 1),A(n),A(n + 1)</mml:annotation></mml:semantics></mml:math>\]</disp-formula><inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mod n"><mml:semantics><mml:mrow><mml:mo lspace="thickmathspace" rspace="thickmathspace">mod</mml:mo><mml:mi>n</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">\bmod n</mml:annotation></mml:semantics></mml:math></inline-formula>. Primes have three types of signatures depending on how they split in the cubic field generated by<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x cubed minus r x squared plus s x minus 1 equals 0"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mi>x</mml:mi><mml:mn>3</mml:mn></mml:msup></mml:mrow><mml:mo>−</mml:mo><mml:mi>r</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:msup><mml:mi>x</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow><mml:mo>+</mml:mo><mml:mi>s</mml:mi><mml:mi>x</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>=</mml:mo><mml:mn>0</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">{x^3} - r{x^2} + sx - 1 = 0</mml:annotation></mml:semantics></mml:math></inline-formula>. Composites with "acceptable" signatures do exist but are very rare. The<italic>S</italic>-type signature, which corresponds to the completely split primes, has a very special role, and it may even be that<italic>I</italic>and<italic>Q</italic>type composites do not occur in Perrin’s sequence even though the<italic>I</italic>and<italic>Q</italic>primes comprise<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="5 slash 6"><mml:semantics><mml:mrow><mml:mn>5</mml:mn><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>6</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">5/6</mml:annotation></mml:semantics></mml:math></inline-formula>ths of all primes.<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis n right-parenthesis left-parenthesis mod n right-parenthesis"><mml:semantics><mml:mrow><mml:mi>A</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mspace width="thickmathspace"/><mml:mspace width="0.667em"/><mml:mo stretchy="false">(</mml:mo><mml:mi>mod</mml:mi><mml:mspace width="0.333em"/><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">A(n)\;\pmod n</mml:annotation></mml:semantics></mml:math></inline-formula>is easily computable in<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis log n right-parenthesis"><mml:semantics><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">O(\log n)</mml:annotation></mml:semantics></mml:math></inline-formula>operations. The paper closes with a<italic>p</italic>-adic analysis. This powerful tool sets the stage for our [12] which will be Part II of the paper.