Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Published electronically: July 1, 2003
MathSciNet review: 2047101
Full-text PDF Free Access

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?)


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: http://dx.doi.org/10.1090/S0025-5718-03-01575-8
PII: S 0025-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