The AGM-X 0(N) Heegner Point Lifting Algorithm
and Elliptic Curve Point Counting 1st edition
by David Kohel ISBN 3540205920 9783540205920 pdf
download
https://ebookball.com/product/the-agm-x-0-n-heegner-point-
lifting-algorithm-and-elliptic-curve-point-counting-1st-edition-
by-david-kohel-isbn-3540205920-9783540205920-11308/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Tate Pairing Implementation for Hyperelliptic y 2 = x p – x + d 1st
edition by Iwan Duursma, Hyang Sook Lee ISBN 3540205920 978354020592
https://ebookball.com/product/tate-pairing-implementation-for-
hyperelliptic-y-2-x-p-aeur-x-d-1st-edition-by-iwan-duursma-hyang-
sook-lee-isbn-3540205920-9783540205920-8946/
Massively parallel elliptic curve factoring 1st edition by Dixon,
Lenstra ISBN 3540564133 9783540564133
https://ebookball.com/product/massively-parallel-elliptic-curve-
factoring-1st-edition-by-dixon-lenstra-
isbn-3540564133-9783540564133-11064/
Living and Nursing from the Highest Point of Your Consciousness 1st
edition by Rachel Hill 0763769967 9780763769963
https://ebookball.com/product/living-and-nursing-from-the-
highest-point-of-your-consciousness-1st-edition-by-rachel-
hill-0763769967-9780763769963-786/
On Diophantine Complexity and Statistical Zero Knowledge Arguments 1st
edition by ISBN Helger Lipmaa 3540205920 9783540205920
https://ebookball.com/product/on-diophantine-complexity-and-
statistical-zero-knowledge-arguments-1st-edition-by-isbn-helger-
lipmaa-3540205920-9783540205920-9426/
,Verifiable Homomorphic Oblivious Transfer and Private Equality Test
1st edition by Helger Lipmaa ISBN 3540205920 9783540205920
https://ebookball.com/product/verifiable-homomorphic-oblivious-
transfer-and-private-equality-test-1st-edition-by-helger-lipmaa-
isbn-3540205920-9783540205920-9424/
A Simple Public Key Cryptosystem with a Double Trapdoor Decryption
Mechanism and Its Applications 1st edition by Emmanuel Bresson, Dario
Catalano, David Pointcheval ISBN 3540205920 9783540205920
https://ebookball.com/product/a-simple-public-key-cryptosystem-
with-a-double-trapdoor-decryption-mechanism-and-its-
applications-1st-edition-by-emmanuel-bresson-dario-catalano-
david-pointcheval-isbn-3540205920-9783540205920-10706/
Efficient Group Signatures without Trapdoors 1st edition by Giuseppe
Ateniese, Breno de Medeiros ISBN 3540205920 9783540205920
https://ebookball.com/product/efficient-group-signatures-without-
trapdoors-1st-edition-by-giuseppe-ateniese-breno-de-medeiros-
isbn-3540205920-9783540205920-9868/
On the Geometric Dilation of Finite Point Sets 1st edition by Annette
Ebbers Baumann, Ansgar Grune, Rolf Klein ISBN 3540206958
9783540206958
https://ebookball.com/product/on-the-geometric-dilation-of-
finite-point-sets-1st-edition-by-annette-ebbers-baumann-ansgar-
grune-rolf-klein-isbn-3540206958-9783540206958-13670/
The Ultimate Guide to Point Of Care Ultrasound Guided Procedures 1st
edition by Srikar Adhikari, Michael Blaivas ISBN 3030282651
978-3030282653
https://ebookball.com/product/the-ultimate-guide-to-point-of-
care-ultrasound-guided-procedures-1st-edition-by-srikar-adhikari-
michael-blaivas-isbn-3030282651-978-3030282653-6246/
, The AGM-X0(N ) Heegner Point Lifting
Algorithm and Elliptic Curve Point Counting
David R. Kohel
School of Mathematics and Statistics
University of Sydney, NSW 2006, Australia
Abstract. We describe an algorithm, AGM-X0 (N ), for point counting
on elliptic curves of small characteristic p using p-adic lifts of their in-
variants associated to modular curves X0 (N ). The algorithm generalizes
the contruction of Satoh [10], SST [11], and Mestre [9]. We describe this
method and give details of its implementation for characteristics 2, 3, 5,
7, and 13.
Keywords: Elliptic curve cryptography, modular curves, point counting
1 Introduction
Elliptic curve cryptosystems can be designed using the reduction of precom-
puted CM curves or using randomly selected curves over a finite field. In the
former case, the curve can be assumed to be drawn from a prespecified list of
curves having many endomorphisms, on which an adversary can perform pre-
computations or exploit the existence of endomorphisms of small degree. On the
general randomly selected curve, the only endomorphisms of small degree are
scalar multiplication by a small integer. Such curves are believed to have higher
security, but to implement an elliptic curve cryptosystem using randomly gen-
erated curves, it is imperative to have an efficient algorithm to determine the
number of points on arbitrary elliptic curves.
The first theoretically polynomial time algorithm for point counting was
due to Schoof [13]. Atkin and Elkies (see [3]) introduced the use of modular
parametrizations of the torsion subgroups of elliptic curves to turn Schoof’s
algorithm into a practical one. Couveignes introduced an extension of this al-
gorithm to curves over finite fields of small characteristic, and independently
Lercier designed an efficient algorithm specific to characteristic 2.
In 1999, Satoh [10] introduced a novel idea of p-adically lifting the j-invariants
of the cycle of curves which are related by the Frobenius isogeny (x, y) →
(xp , y p ) over a finite field Fq = Fpm of small characteristic p. The j-invariants
j0 , j1 , . . . , jm = j0 can be lifted efficiently to a degree m extension of the p-adic
field Qp even though to lift the j-invariants to an extension of Q would in gen-
√
eral require an extension of degree O( q). The classical modular polynomial
Φp (X, Y ) provides the algebraic lifting condition. The unique p-adic lifts ̃i are
those for which the equations Φp (̃i , ̃i+1 ) = 0 continue to hold. This was followed
C.S. Laih (Ed.): ASIACRYPT 2003, LNCS 2894, pp. 124–136, 2003.
c International Association for Cryptologic Research 2003
and Elliptic Curve Point Counting 1st edition
by David Kohel ISBN 3540205920 9783540205920 pdf
download
https://ebookball.com/product/the-agm-x-0-n-heegner-point-
lifting-algorithm-and-elliptic-curve-point-counting-1st-edition-
by-david-kohel-isbn-3540205920-9783540205920-11308/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Tate Pairing Implementation for Hyperelliptic y 2 = x p – x + d 1st
edition by Iwan Duursma, Hyang Sook Lee ISBN 3540205920 978354020592
https://ebookball.com/product/tate-pairing-implementation-for-
hyperelliptic-y-2-x-p-aeur-x-d-1st-edition-by-iwan-duursma-hyang-
sook-lee-isbn-3540205920-9783540205920-8946/
Massively parallel elliptic curve factoring 1st edition by Dixon,
Lenstra ISBN 3540564133 9783540564133
https://ebookball.com/product/massively-parallel-elliptic-curve-
factoring-1st-edition-by-dixon-lenstra-
isbn-3540564133-9783540564133-11064/
Living and Nursing from the Highest Point of Your Consciousness 1st
edition by Rachel Hill 0763769967 9780763769963
https://ebookball.com/product/living-and-nursing-from-the-
highest-point-of-your-consciousness-1st-edition-by-rachel-
hill-0763769967-9780763769963-786/
On Diophantine Complexity and Statistical Zero Knowledge Arguments 1st
edition by ISBN Helger Lipmaa 3540205920 9783540205920
https://ebookball.com/product/on-diophantine-complexity-and-
statistical-zero-knowledge-arguments-1st-edition-by-isbn-helger-
lipmaa-3540205920-9783540205920-9426/
,Verifiable Homomorphic Oblivious Transfer and Private Equality Test
1st edition by Helger Lipmaa ISBN 3540205920 9783540205920
https://ebookball.com/product/verifiable-homomorphic-oblivious-
transfer-and-private-equality-test-1st-edition-by-helger-lipmaa-
isbn-3540205920-9783540205920-9424/
A Simple Public Key Cryptosystem with a Double Trapdoor Decryption
Mechanism and Its Applications 1st edition by Emmanuel Bresson, Dario
Catalano, David Pointcheval ISBN 3540205920 9783540205920
https://ebookball.com/product/a-simple-public-key-cryptosystem-
with-a-double-trapdoor-decryption-mechanism-and-its-
applications-1st-edition-by-emmanuel-bresson-dario-catalano-
david-pointcheval-isbn-3540205920-9783540205920-10706/
Efficient Group Signatures without Trapdoors 1st edition by Giuseppe
Ateniese, Breno de Medeiros ISBN 3540205920 9783540205920
https://ebookball.com/product/efficient-group-signatures-without-
trapdoors-1st-edition-by-giuseppe-ateniese-breno-de-medeiros-
isbn-3540205920-9783540205920-9868/
On the Geometric Dilation of Finite Point Sets 1st edition by Annette
Ebbers Baumann, Ansgar Grune, Rolf Klein ISBN 3540206958
9783540206958
https://ebookball.com/product/on-the-geometric-dilation-of-
finite-point-sets-1st-edition-by-annette-ebbers-baumann-ansgar-
grune-rolf-klein-isbn-3540206958-9783540206958-13670/
The Ultimate Guide to Point Of Care Ultrasound Guided Procedures 1st
edition by Srikar Adhikari, Michael Blaivas ISBN 3030282651
978-3030282653
https://ebookball.com/product/the-ultimate-guide-to-point-of-
care-ultrasound-guided-procedures-1st-edition-by-srikar-adhikari-
michael-blaivas-isbn-3030282651-978-3030282653-6246/
, The AGM-X0(N ) Heegner Point Lifting
Algorithm and Elliptic Curve Point Counting
David R. Kohel
School of Mathematics and Statistics
University of Sydney, NSW 2006, Australia
Abstract. We describe an algorithm, AGM-X0 (N ), for point counting
on elliptic curves of small characteristic p using p-adic lifts of their in-
variants associated to modular curves X0 (N ). The algorithm generalizes
the contruction of Satoh [10], SST [11], and Mestre [9]. We describe this
method and give details of its implementation for characteristics 2, 3, 5,
7, and 13.
Keywords: Elliptic curve cryptography, modular curves, point counting
1 Introduction
Elliptic curve cryptosystems can be designed using the reduction of precom-
puted CM curves or using randomly selected curves over a finite field. In the
former case, the curve can be assumed to be drawn from a prespecified list of
curves having many endomorphisms, on which an adversary can perform pre-
computations or exploit the existence of endomorphisms of small degree. On the
general randomly selected curve, the only endomorphisms of small degree are
scalar multiplication by a small integer. Such curves are believed to have higher
security, but to implement an elliptic curve cryptosystem using randomly gen-
erated curves, it is imperative to have an efficient algorithm to determine the
number of points on arbitrary elliptic curves.
The first theoretically polynomial time algorithm for point counting was
due to Schoof [13]. Atkin and Elkies (see [3]) introduced the use of modular
parametrizations of the torsion subgroups of elliptic curves to turn Schoof’s
algorithm into a practical one. Couveignes introduced an extension of this al-
gorithm to curves over finite fields of small characteristic, and independently
Lercier designed an efficient algorithm specific to characteristic 2.
In 1999, Satoh [10] introduced a novel idea of p-adically lifting the j-invariants
of the cycle of curves which are related by the Frobenius isogeny (x, y) →
(xp , y p ) over a finite field Fq = Fpm of small characteristic p. The j-invariants
j0 , j1 , . . . , jm = j0 can be lifted efficiently to a degree m extension of the p-adic
field Qp even though to lift the j-invariants to an extension of Q would in gen-
√
eral require an extension of degree O( q). The classical modular polynomial
Φp (X, Y ) provides the algebraic lifting condition. The unique p-adic lifts ̃i are
those for which the equations Φp (̃i , ̃i+1 ) = 0 continue to hold. This was followed
C.S. Laih (Ed.): ASIACRYPT 2003, LNCS 2894, pp. 124–136, 2003.
c International Association for Cryptologic Research 2003
