THE PROBABILITY THAT THE NUMBER OF POINTS ON AN ELLIPTIC CURVE OVER A FINITE FIELD IS PRIME

STEVEN D. GALBRAITH; JAMES McKEE

doi:10.1112/S0024610700001502

Abstract

The paper gives a formula for the probability that a randomly chosen elliptic curve over a finite field has a prime number of points. Two heuristic arguments in support of the formula are given as well as experimental evidence. The paper also gives a formula for the probability that a randomly chosen elliptic curve over a finite field has kq points where k is a small number and q is a prime.

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Miri, S. Ali and Murty, V. Kumar 2001. Progress in Cryptology — INDOCRYPT 2001. Vol. 2247, Issue. , p. 91.

Lange, Tanja and Shparlinski, Igor 2005. Collisions in Fast Generation of Ideal Classes and Points on Hyperelliptic and Elliptic Curves. Applicable Algebra in Engineering, Communication and Computing, Vol. 15, Issue. 5, p. 329.

Konstantinou, Elisavet Kontogeorgis, Aristides Stamatiou, Yannis C. and Zaroliagis, Christos 2005. Information Security and Cryptology – ICISC 2004. Vol. 3506, Issue. , p. 261.

Murty, Ram and Shparlinski, Igor 2006. Topics in Geometry, Coding Theory and Cryptography. Vol. 6, Issue. , p. 167.

Bernstein, Daniel J. Birkner, Peter Joye, Marc Lange, Tanja and Peters, Christiane 2008. Progress in Cryptology – AFRICACRYPT 2008. Vol. 5023, Issue. , p. 389.

Konstantinou, Elisavet Kontogeorgis, Aristides Stamatiou, Yannis C and Zaroliagis, Christos 2010. On the Efficient Generation of Prime-Order Elliptic Curves. Journal of Cryptology, Vol. 23, Issue. 3, p. 477.

Bakhtiari, Saeid Ibrahim, Subariah Salleh, Mazleena and Bakhtiari, Majid 2013. Prime order elliptic curve generation methods: A review. p. 109.

Castryck, Wouter and Hubrechts, Hendrik 2013. The distribution of the number of points modulo an integer on elliptic curves over finite fields. The Ramanujan Journal, Vol. 30, Issue. 2, p. 223.

Shparlinski, Igor E. 2013. Advances in Applied Mathematics, Modeling, and Computational Science. Vol. 66, Issue. , p. 65.

Shparlinski, Igor E. and Sutantyo, Daniel 2014. Distribution of elliptic twin primes in isogeny and isomorphism classes. Journal of Number Theory, Vol. 137, Issue. , p. 1.

Bernstein, Daniel J. Chou, Tung Chuengsatiansup, Chitchanok Hülsing, Andreas Lambooij, Eran Lange, Tanja Niederhagen, Ruben and van Vredendaal, Christine 2015. Security Standardisation Research. Vol. 9497, Issue. , p. 109.

Auerbach, Benedikt Bellare, Mihir and Kiltz, Eike 2018. Public-Key Cryptography – PKC 2018. Vol. 10769, Issue. , p. 348.

Meneghetti, Alessio Sala, Massimiliano and Taufer, Daniele 2020. A New ECDLP-Based PoW Model. Mathematics, Vol. 8, Issue. 8, p. 1344.

Swati and Gupta, Ramjee Prasad 2022. Artificial Intelligence and Sustainable Computing. p. 201.

Werapun, Warodom Karode, Tanakorn Suaboot, Jakapan Arpornthip, Tanwa and Sangiamkul, Esther 2023. NativeVRF: A Simplified Decentralized Random Number Generator on EVM Blockchains. Systems, Vol. 11, Issue. 7, p. 326.

Kane, Ben and Pujahari, Sudhir 2023. Distribution of moments of Hurwitz class numbers in arithmetic progressions and holomorphic projection. Transactions of the American Mathematical Society, Vol. 376, Issue. 8, p. 5503.

Article contents

THE PROBABILITY THAT THE NUMBER OF POINTS ON AN ELLIPTIC CURVE OVER A FINITE FIELD IS PRIME

Abstract

Access options

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Article contents

THE PROBABILITY THAT THE NUMBER OF POINTS ON AN ELLIPTIC CURVE OVER A FINITE FIELD IS PRIME

Abstract

Access options

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests