Frobenius pseudoprimes and a cubic primality test

Catherine A. Buell and Eric W. Kimball
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 20, 2014, Number 4, Pages 11–20
Full paper (PDF, 172 Kb)

Details

Authors and affiliations

Catherine A. Buell
Department of Mathematics, Fitchburg State University
160 Pearl Street, Fitchburg, MA, 01420, USA

Eric W. Kimball
Department of Mathematics, Bates College
3 Andrews Rd., Lewiston, ME, 04240, USA

Abstract

An integer, n, is called a Frobenius probable prime with respect to a polynomial when it passes the Frobenius probable prime test. Composite integers that are Frobenius probable primes are called Frobenius pseudoprimes. Jon Grantham developed and analyzed a Frobenius probable prime test with quadratic polynomials. Using the Chinese Remainder Theorem and Frobenius automorphisms, we were able to extend Grantham’s results to some cubic polynomials. This case is computationally similar but more efficient than the quadratic case.

Keywords

• Frobenius
• Pseudoprimes
• Cubic
• Number fields
• Primality

AMS Classification

• 11Y11

References

1. Grantham, J. Frobenius Pseudoprimes, Mathematics of Computation, Vol. 234, 2000, 873–891.
2. Grantham, J. A Probable Prime Test With High Confidence, Journal of Number Theory, Vol. 72, 1998, 32–47.