On the Distribution of Atkin and Elkies Primes
Given an elliptic curve E over a finite field F[subscript q] of q elements, we say that an odd prime ℓ∤q is an Elkies prime for E if t[superscript 2][subscript E]−4q is a square modulo ℓ, where t[subscript E]=q+1−#E(F[subscript q]) and #E(F[subscript q]) is the number of F[subscript q]-rationa...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2016
|
| Online Access: | http://hdl.handle.net/1721.1/104899 |
| _version_ | 1826204395577016320 |
|---|---|
| author | Shparlinski, Igor E. Sutherland II, Andrew Victor |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Shparlinski, Igor E. Sutherland II, Andrew Victor |
| author_sort | Shparlinski, Igor E. |
| collection | MIT |
| description | Given an elliptic curve E over a finite field F[subscript q] of q elements, we say that an odd prime ℓ∤q is an Elkies prime for E if t[superscript 2][subscript E]−4q is a square modulo ℓ, where t[subscript E]=q+1−#E(F[subscript q]) and #E(F[subscript q]) is the number of F[subscript q]-rational points on E; otherwise, ℓ is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ℓ<L on average over all curves E over F[subscript q], provided that L≥(log q)[superscript ε] for any fixed ε>0 and a sufficiently large q. We use this result to design and analyze a fast algorithm to generate random elliptic curves with #E(F[subscript p]) prime, where p varies uniformly over primes in a given interval [x,2x]. |
| first_indexed | 2024-09-23T12:54:24Z |
| format | Article |
| id | mit-1721.1/104899 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:54:24Z |
| publishDate | 2016 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1048992024-06-26T15:16:09Z On the Distribution of Atkin and Elkies Primes Shparlinski, Igor E. Sutherland II, Andrew Victor Massachusetts Institute of Technology. Department of Mathematics Sutherland II, Andrew Victor Given an elliptic curve E over a finite field F[subscript q] of q elements, we say that an odd prime ℓ∤q is an Elkies prime for E if t[superscript 2][subscript E]−4q is a square modulo ℓ, where t[subscript E]=q+1−#E(F[subscript q]) and #E(F[subscript q]) is the number of F[subscript q]-rational points on E; otherwise, ℓ is called an Atkin prime. We show that there are asymptotically the same number of Atkin and Elkies primes ℓ<L on average over all curves E over F[subscript q], provided that L≥(log q)[superscript ε] for any fixed ε>0 and a sufficiently large q. We use this result to design and analyze a fast algorithm to generate random elliptic curves with #E(F[subscript p]) prime, where p varies uniformly over primes in a given interval [x,2x]. 2016-10-20T20:30:02Z 2016-10-20T20:30:02Z 2014-02 2013-07 2016-08-18T15:41:25Z Article http://purl.org/eprint/type/JournalArticle 1615-3375 1615-3383 http://hdl.handle.net/1721.1/104899 Shparlinski, Igor E., and Andrew V. Sutherland. “On the Distribution of Atkin and Elkies Primes.” Foundations of Computational Mathematics 14.2 (2014): 285–297. © SFoCM 2014 en http://dx.doi.org/10.1007/s10208-013-9181-9 Foundations of Computational Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. SFoCM application/pdf Springer US Springer US |
| spellingShingle | Shparlinski, Igor E. Sutherland II, Andrew Victor On the Distribution of Atkin and Elkies Primes |
| title | On the Distribution of Atkin and Elkies Primes |
| title_full | On the Distribution of Atkin and Elkies Primes |
| title_fullStr | On the Distribution of Atkin and Elkies Primes |
| title_full_unstemmed | On the Distribution of Atkin and Elkies Primes |
| title_short | On the Distribution of Atkin and Elkies Primes |
| title_sort | on the distribution of atkin and elkies primes |
| url | http://hdl.handle.net/1721.1/104899 |
| work_keys_str_mv | AT shparlinskiigore onthedistributionofatkinandelkiesprimes AT sutherlandiiandrewvictor onthedistributionofatkinandelkiesprimes |