Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Biquadratic reciprocity and a Lucasian primality test


Authors: Pedro Berrizbeitia and T. G. Berry
Journal: Math. Comp. 73 (2004), 1559-1564
MSC (2000): Primary 11A51, 11Y11
DOI: https://doi.org/10.1090/S0025-5718-03-01575-8
Published electronically: July 1, 2003
MathSciNet review: 2047101
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\{s_k,k\geq 0\}$ be the sequence defined from a given initial value, the seed, $s_0$, by the recurrence $s_{k+1}=s_k^2-2,k\geq 0$. Then, for a suitable seed $s_0$, the number $M_{h,n}=h\cdot2^n-1$ (where $h<2^n$ is odd) is prime iff $s_{n-2} \equiv 0 \bmod M_{h,n}$. In general $s_0$ depends both on $h$ and on $n$. We describe a slight modification of this test which determines primality of numbers $h\cdot2^n\pm 1$ with a seed which depends only on $h$, provided $h \not \equiv 0 \bmod 5$. In particular, when $h=4^m-1$, $m$ odd, we have a test with a single seed depending only on $h$, in contrast with the unmodified test, which, as proved by W. Bosma in Explicit primality criteria for $h\cdot 2^k\pm 1$, Math. Comp. 61 (1993), 97-109, needs infinitely many seeds. The proof of validity uses biquadratic reciprocity.


References [Enhancements On Off] (What's this?)

  • 1. Wieb Bosma.
    Explicit primality criteria for $h\cdot 2\sp k\pm 1$.
    Math. Comp., 61(203):97-109, S7-S9, 1993. MR 94c:11005
  • 2. K. Ireland and M. Rosen.
    A classical introduction to modern number theory.
    Springer Verlag, 1990. MR 92e:11001
  • 3. Hans Riesel.
    Lucasian criteria for the primality of ${N}=h\cdot 2\sp{n} -1$.
    Math. Comp., 23:869-875, 1969. MR 41:6773
  • 4. Hugh C. Williams.
    Édouard Lucas and Primality Testing, volume 22 of Canadian Math. Society Series of Advanced Texts.
    John Wiley and Sons, 1998. MR 2000b:11139

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11A51, 11Y11

Retrieve articles in all journals with MSC (2000): 11A51, 11Y11


Additional Information

Pedro Berrizbeitia
Affiliation: Departamento de Matemáticas Puras y Aplicadas, Universidad Simón Bolívar, Caracas, Venezuela
Email: pedrob@usb.ve

T. G. Berry
Affiliation: Departamento de Matemáticas Puras y Aplicadas, Universidad Simón Bolívar, Caracas, Venezuela
Email: berry@usb.ve

DOI: https://doi.org/10.1090/S0025-5718-03-01575-8
Received by editor(s): May 3, 2002
Received by editor(s) in revised form: January 10, 2003
Published electronically: July 1, 2003
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society