An Efficient Approach to Point-Counting on Elliptic Curves from a Prominent Family over the Prime Field F p

Yuri Borissov and Miroslav Markov
Additional contact information
Yuri Borissov: Department of Mathematical Foundations of Informatics, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 1113 Sofia, Bulgaria
Miroslav Markov: Department of Mathematical Foundations of Informatics, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 1113 Sofia, Bulgaria

Mathematics, 2021, vol. 9, issue 12, 1-9

Abstract: Here, we elaborate an approach for determining the number of points on elliptic curves from the family E p = { E a : y 2 = x 3 + a ( mod p ) , a ? 0 } , where p is a prime number >3. The essence of this approach consists in combining the well-known Hasse bound with an explicit formula for the quantities of interest-reduced modulo p . It allows to advance an efficient technique to compute the six cardinalities associated with the family E p , for p ? 1 ( mod 3 ) , whose complexity is O ˜ ( log 2 p ) , thus improving the best-known algorithmic solution with almost an order of magnitude.

Keywords: elliptic curve over \({\mathbb{F}_{p}}\); Hasse bound; high-order residue modulo prime (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/12/1431/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/12/1431/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:12:p:1431-:d:577924

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().