Kummer Surface Arithmetic for Primality Testing
Abstract
We use the arithmetic of the Kummer surface associated to the Jacobian of a hyperelliptic curve to study the primality of integers of the form λm,n := 4m^2*5^n − 1. We provide an algorithm capable of proving the primality or compositeness of most of the integers in these families and discuss in detail the necessary steps to implement this algorithm in a computer. The algorithm depends on an initial choice of a pair of integers. If λm,n is prime there is always a pair that works. We prove that the proportion of pairs that do not work to show compositeness for this algorithm is very small and decreases exponentially with n.
Downloads
References
[1] A. Abatzoglou, A. Silverberg, A. Sutherland, and A. Wong. Deterministic elliptic curve primality proving for a special sequence of numbers. The Open Book Series, 1(1):1–20, 2013. a
[2] A. Abatzoglou, A. Silverberg, A. Sutherland, and A. Wong. A framework for deterministic primality proving using elliptic curves with complex multiplication. Math. Comp., 85(299):1461–1483, 2016. a
[3] M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Ann. of Math., 160(2):781–793, 2004. a
[4] S. Bosch, W. L¨utkebohmert, and M. Raynaud. N´eron models, volume 21 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1990. 1
[5] W. Bosma. Primality testing using elliptic curves. University of Amsterdam, Department of Mathematics, 1985. a
[6] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(34):235–265, 1997. Computational algebra and number theory (London, 1993). 2.2
[7] J. W. S. Cassels and E. V. Flynn. Prolegomena to a middlebrow arithmetic of curves of genus 2, volume 230 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1996. 1, 2.1
[8] C. Costello and K. Lauter. Group law computations on Jacobians of hyperelliptic curves. In A. Miri and S. Vaudenay, editors, Selected Areas in Cryptography, pages 92–117, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. 2.1
[9] R. Denomme and G. Savin. Elliptic curve primality tests for Fermat and related primes. J. Number Theory, 128(8):23982412, 2008. a
[10] E. R. Duarte and M. P. Noordman. Example primality test using kummer surface. https://github.com/toorandom/
kummerendomorphisms/blob/master/primetestkummerexample.py, 2020. 2.5
[11] E. R. Duarte and M. P. Noordman. Kummer endomorphism calculation for genus 2.https://github.com/toorandom/kummerendomorphisms/blob/master/kumendoformulas.magma, 2020. 2.2, 2.5
[12] E. R. Duarte and M. P. Noordman. Kummer explicit endomorphisms for different curves. https://github.com/toorandom/kummerendomorphisms/blob/master/kumsqrt5endomorphisms.py, 2020. 2.2, 2.5
[13] E. R. Duarte and M. P. Noordman. Kummer initial points code and endomorphism calculation. https://github.com/toorandom/kummerendomorphisms/blob/master/, 2020. 2
[14] E. R. Duarte and M. P. Noordman. Magma code to generate starting kummer points for primality on different m. https://github.com/toorandom/kummerendomorphisms/blob/master/kumstartvectors.magma, 2020. 2.5
[15] E. R. Duarte and M. P. Noordman. Starting kummer points for primality on different m. https://github.com/toorandom/kummerendomorphisms/blob/master/kumstartvectors.py, 2020. 2.3, 2.5
[16] E. R. Duarte and M. P. Noordman. Starting vectors in csv for various m and h. https://github.com/toorandom/kummerendomorphisms/tree/master/startvectors, 2020. 2.5
[17] R. R. Farashahi. Extractors for Jacobian of hyperelliptic curves of genus 2 in odd characteristic. In S. D. Galbraith, editor, Cryptography and Coding, pages 313–335, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. 2.1
[18] E. V. Flynn. The Jacobian and formal group of a curve of genus 2 over an arbitrary ground field. Math. Proc. Cambridge Philos. Soc., 107(3):425–441, 1990. 2.1
[19] E. V. Flynn. The group law on the Jacobian of a curve of genus 2. J. Reine Angew. Math, 439:45–69, 1993. 2.1
[20] D. Grant. Formal groups in genus two. J. Reine Angew. Math, 411:96––121, 1990. 2.1
[21] B. H. Gross. An elliptic curve test for Mersenne primes. J. Number Theory, 110(1):114–119, 2005. a
[22] A. Gurevich and B. Kunyavski˘ı. Primality testing through algebraic groups. Arch. Math. (Basel), 93(6):555–564, 2009. a
[23] S. Hambleton. Generalized Lucas-Lehmer tests using Pell conics. Proc. Amer. Math. Soc., 140(8):2653–2661, 2012. a
[24] D. H. Lehmer. On Lucas’ test for the primality of Mersenne’s numbers. Journal of the London Mathematical Society, 10:162–165, 1935. a
[25] H. W. Lenstra Jr. and C. Pomerance. Primality testing with Gaussian periods. 2005. a
[26] T. P´epin. Sur la formule 22n + 1. Comptes Rendus des S´eances de l’Acad´emie des Sciences. Paris., (85):329–331, 1877. a
[27] C. Pomerance. Very short primality proofs. Math. Comp., 48(177):315–322, 1987. a
[28] J. T. Tate and I. R. Shafarevich. The rank of elliptic curves. Dokl. Akad. Nauk SSSR, 175(4):770–773, 1967. 1
[29] C. Xing. On supersingular abelian varieties of dimension two over finite fields. Finite Fields Appl., 2(4):407–421, 1996.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Eduardo Ruiz Duarte, Marc Paul
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
