1975/01/01 by John Brillhart, D. H. Lehmer, J. L. Selfridge · 104 citations
Computer Science · Physics and Astronomy · Mathematics · #Coding theory and cryptography #Polynomial and algebraic computation #Advanced Mathematical Theories and Applications #Algorithm #Type (biology) #Annotation #Computer science #Mathematics #Artificial intelligence #Database
paper · pdf · doi:10.1090/s0025-5718-1975-0384673-1
published in Mathematics of Computation 29(130), 620-647 (American Mathematical Society)
openalex publication_date 1975/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
A collection of theorems is developed for testing a given integer <italic>N</italic> for primality. The first type of theorem considered is based on the converse of Fermat’s theorem and uses factors of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N minus 1"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">N - 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The second type is based on divisibility properties of Lucas sequences and uses factors of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N plus 1"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">N + 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The third type uses factors of both <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N minus 1"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">N - 1</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 N plus 1"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">N + 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and provides a more effective, yet more complicated, primality test. The search bound for factors of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo> ± </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">N ± 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and properties of the hyperbola <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals x squared minus y squared"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <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:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>y</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">N = x2 - y2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are utilized in the theory for the first time. A collection of 133 new complete factorizations of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript m Baseline plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>m</mml:mi> </mml:msup> </mml:mrow> <mml:mo> ± </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">2m ± 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and associated numbers is included, along with two status lists: one for the complete factorizations of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript m Baseline plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>m</mml:mi> </mml:msup> </mml:mrow> <mml:mo> ± </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">2m ± 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ; the other for the original Mersenne numbers.