refs.bib

% Encoding: UTF-8

@book{Lam,
    AUTHOR = {Lam, T. Y.},
     TITLE = {Introduction to quadratic forms over fields},
    SERIES = {Graduate Studies in Mathematics},
    VOLUME = {67},
 PUBLISHER = {American Mathematical Society, Providence, RI},
      YEAR = {2005},
     PAGES = {xxii+550},
      ISBN = {0-8218-1095-2},
   MRCLASS = {11Exx},
  MRNUMBER = {2104929},
MRREVIEWER = {K. Szymiczek},
}

@Book{silverman:advanced,
  title                = {Advanced Topics in the Arithmetic of Elliptic Curves},
  publisher            = {Springer},
  year                 = {1994},
  author               = {Silverman, Joseph H.},
  volume               = {151},
  series               = {Graduate Texts in Mathematics},
  month                = jan,
  isbn                 = {0387943285},
  abstract             = {{This book continues the treatment of the arithmetic theory of elliptic curves begun in the first volume. The book begins with the theory of elliptic and modular functions for the full modular group r(1), including a discussion of Hekcke operators and the L-series associated to cusp forms. This is followed by a detailed study of elliptic curves with complex multiplication, their associated Gr\"{o}ssencharacters and L-series, and applications to the construction of abelian extensions of quadratic imaginary fields. Next comes a treatment of elliptic curves over function fields and elliptic surfaces, including specialization theorems for heights and sections. This material serves as a prelude to the theory of minimal models and N\'{e}ron models of elliptic curves, with a discussion of special fibers, conductors, and Ogg's formula. Next comes a brief description of q-models for elliptic curves over C and R, followed by Tate's theory of q-models for elliptic curves with non-integral j-invariant over p-adic fields. The book concludes with the construction of canonical local height functions on elliptic curves, including explicit formulas for both archimedean and non-archimedean fields.}},
  citeulike-article-id = {789887},
  citeulike-linkout-0  = {http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path=ASIN/0387943285},
  citeulike-linkout-1  = {http://www.amazon.de/exec/obidos/redirect?tag=citeulike01-21&path=ASIN/0387943285},
  citeulike-linkout-2  = {http://www.amazon.fr/exec/obidos/redirect?tag=citeulike06-21&path=ASIN/0387943285},
  citeulike-linkout-3  = {http://www.amazon.co.uk/exec/obidos/ASIN/0387943285/citeulike00-21},
  citeulike-linkout-4  = {http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/0387943285},
  citeulike-linkout-5  = {http://www.worldcat.org/isbn/0387943285},
  citeulike-linkout-6  = {http://books.google.com/books?vid=ISBN0387943285},
  citeulike-linkout-7  = {http://www.amazon.com/gp/search?keywords=0387943285&index=books&linkCode=qs},
  citeulike-linkout-8  = {http://www.librarything.com/isbn/0387943285},
  day                  = {01},
  groups               = {Isogenies},
  howpublished         = {Paperback},
  keywords             = {elliptic\_curve},
  posted-at            = {2010-06-20 19:57:19},
  url                  = {http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/0387943285},
}

@Book{silverman:elliptic,
  title                = {The arithmetic of elliptic curves},
  publisher            = {Springer-Verlag},
  year                 = {1992},
  author               = {Silverman, Joseph H.},
  volume               = {106},
  series               = {Graduate Texts in Mathematics},
  address              = {New York},
  citeulike-article-id = {10862495},
  comment              = {Corrected reprint of the 1986 original},
  groups               = {Isogenies},
  mrnumber             = {MR1329092 (95m:11054)},
  posted-at            = {2012-07-06 21:19:47},
}

@Book{langANT,
  title     = {Algebraic number theory},
  publisher = {Springer-Verlag},
  year      = {1994},
  author    = {Lang, Serge},
  volume    = {110},
  series    = {Graduate Texts in Mathematics},
  isbn      = {978-0-387-94225-4},
  doi       = {10.1007/978-1-4612-0853-2},
  location  = {New York},
  pagetotal = {XIII, 357},
}

@Book{lang1987elliptic,
  title     = {Elliptic Functions},
  publisher = {Springer},
  year      = {1987},
  author    = {Lang, Serge},
  volume    = {112},
  series    = {Graduate texts in mathematics},
  isbn      = {9780387965086},
  groups    = {Isogenies},
  lccn      = {87004514},
}

@Book{neukirch2013algebraic,
  title     = {Algebraic number theory},
  publisher = {Springer Verlag},
  year      = {1999},
  author    = {Neukirch, J{\"u}rgen},
  volume    = {322},
  isbn      = {978-3-642-08473-7},
  doi       = {10.1007/978-3-662-03983-0},
  location  = {Berlin Heidelberg},
}

@InProceedings{10.1007/3-540-44448-3_18,
  author    = {Hamdy, Safuat and M{\"o}ller, Bodo},
  title     = {Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders},
  booktitle = {Advances in Cryptology --- ASIACRYPT 2000},
  year      = {2000},
  editor    = {Okamoto, Tatsuaki},
  pages     = {234--247},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {In this work we investigate the dificulty of the
                   discrete logarithm problem in class groups of
                   imaginary quadratic orders.In particular, we discuss
                   several strategies to compute discrete logarithms in
                   those class groups.Based on heuristic reasoning, we
                   give advice for selecting the cryptographic
                   parameter, i.e. the discriminant, such that
                   cryptosystems based on class groups of imaginary
                   quadratic orders would offer a similar security as
                   commonly used cryptosystems.},
  isbn      = {978-3-540-44448-0},
}

@InProceedings{10.1007/3-540-44598-6_10,
  author    = {Ko, Ki Hyoung and Lee, Sang Jin and Cheon, Jung Hee and Han, Jae Woo and Kang, Ju-sung and Park, Choonsik},
  title     = {New Public-Key Cryptosystem Using Braid Groups},
  booktitle = {Advances in Cryptology --- CRYPTO 2000},
  year      = {2000},
  editor    = {Bellare, Mihir},
  pages     = {166--183},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {The braid groups are infinite non-commutative groups
                   naturally arising from geometric braids. The aim of
                   this article is twofold. One is to show that the
                   braid groups can serve as a good source to enrich
                   cryptography. The feature that makes the braid groups
                   useful to cryptography includes the followings: (i)
                   The word problem is solved via a fast algorithm which
                   computes the canonical form which can be efficiently
                   manipulated by computers. (ii) The group operations
                   can be performed efficiently. (iii) The braid groups
                   have many mathematically hard problems that can be
                   utilized to design cryptographic primitives. The
                   other is to propose and implement a new key agreement
                   scheme and public key cryptosystem based on these
                   primitives in the braid groups. The efficiency of our
                   systems is demonstrated by their speed and
                   information rate. The security of our systems is
                   based on topological, combinatorial and
                   group-theoretical problems that are intractible
                   according to our current mathematical knowledge. The
                   foundation of our systems is quite different from
                   widely used cryptosystems based on number theory, but
                   there are some similarities in design.},
  isbn      = {978-3-540-44598-2},
}

@InProceedings{10.1007/3-540-44598-6_8,
  author    = {Biehl, Ingrid and Meyer, Bernd and M{\"u}ller, Volker},
  title     = {Differential Fault Attacks on Elliptic Curve Cryptosystems},
  booktitle = {Advances in Cryptology --- CRYPTO 2000},
  year      = {2000},
  editor    = {Bellare, Mihir},
  pages     = {131--146},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  isbn      = {978-3-540-44598-2},
}

@InProceedings{10.1007/3-540-45353-9_12,
  author    = {Abdalla, Michel and Bellare, Mihir and Rogaway, Phillip},
  title     = {The Oracle {D}iffie--{H}ellman Assumptions and an Analysis of {DHIES}},
  booktitle = {Topics in Cryptology --- CT-RSA 2001},
  year      = {2001},
  editor    = {Naccache, David},
  pages     = {143--158},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {This paper provides security analysis for the
                   public-key encryption scheme DHIES (formerly named
                   DHES and DHAES), which was proposed in [7] and is now
                   in several draft standards. DHIES is a Diffie-Hellman
                   based scheme that combines a symmetric encryption
                   method, a message authentication code, and a hash
                   function, in addition to number-theoretic operations,
                   in a way which is intended to provide security
                   against chosen-ciphertext attacks. In this paper we
                   find natural assumptions under which DHIES achieves
                   security under chosen-ciphertext attack. The
                   assumptions we make about the Diffie-Hellman problem
                   are interesting variants of the customary ones, and
                   we investigate relationships among them, and provide
                   security lower bounds. Our proofs are in the standard
                   model; no random-oracle assumption is required.},
  isbn      = {978-3-540-45353-6},
}

@InProceedings{10.1007/3-540-48405-1_34,
  author    = {Fujisaki, Eiichiro and Okamoto, Tatsuaki},
  title     = {Secure Integration of Asymmetric and Symmetric Encryption Schemes},
  booktitle = {Advances in Cryptology --- CRYPTO' 99},
  year      = {1999},
  editor    = {Wiener, Michael},
  pages     = {537--554},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {This paper shows a generic and simple conversion from
                   weak asymmetric and symmetric encryption schemes into
                   an asymmetric encryption scheme which is secure in a
                   very strong sense --- indistinguishability against
                   adaptive chosen-ciphertext attacks in the random
                   oracle model. In particular, this conversion can be
                   applied efficiently to an asymmetric encryption
                   scheme that provides a large enough coin space and,
                   for every message, many enough variants of the
                   encryption, like the ElGamal encryption scheme.},
  isbn      = {978-3-540-48405-9},
}

@InProceedings{10.1007/978-3-319-70500-2_12,
  author    = {Hofheinz, Dennis and H{\"o}velmanns, Kathrin and Kiltz, Eike},
  title     = {A Modular Analysis of the {Fujisaki-Okamoto} Transformation},
  booktitle = {Theory of Cryptography},
  year      = {2017},
  editor    = {Kalai, Yael and Reyzin, Leonid},
  pages     = {341--371},
  publisher = {Springer International Publishing},
  isbn      = {978-3-319-70500-2},
}

@InProceedings{10.1007/978-3-642-14081-5_15,
  author    = {Biasse, Jean-Fran{\c{c}}ois and Jacobson, Michael J. and Silvester, Alan K.},
  title     = {Security Estimates for Quadratic Field Based Cryptosystems},
  booktitle = {Information Security and Privacy},
  year      = {2010},
  editor    = {Steinfeld, Ron and Hawkes, Philip},
  pages     = {233--247},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {We describe implementations for solving the discrete
                   logarithm problem in the class group of an imaginary
                   quadratic field and in the infrastructure of a real
                   quadratic field. The algorithms used incorporate
                   improvements over previously-used algorithms, and
                   extensive numerical results are presented
                   demonstrating their efficiency. This data is used as
                   the basis for extrapolations, used to provide
                   recommendations for parameter sizes providing
                   approximately the same level of security as block
                   ciphers with 80, 112, 128, 192, and 256-bit symmetric
                   keys.},
  isbn      = {978-3-642-14081-5},
}

@InProceedings{10.1007/978-3-642-60539-0_27,
  author    = {Gao, Shuhong and Panario, Daniel},
  title     = {Tests and Constructions of Irreducible Polynomials over Finite Fields},
  booktitle = {Foundations of Computational Mathematics},
  year      = {1997},
  editor    = {Cucker, Felipe and Shub, Michael},
  pages     = {346--361},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {In this paper we focus on tests and constructions of
                   irreducible polynomials over finite fields. We
                   revisit Rabin's (1980) algorithm providing a variant
                   of it that improves Rabin's cost estimate by a log n
                   factor. We give a precise analysis of the probability
                   that a random polynomial of degree n contains no
                   irreducible factors of degree less than O(log n).
                   This probability is naturally related to Ben-Or's
                   (1981) algorithm for testing irreducibility of
                   polynomials over finite fields. We also compute the
                   probability of a polynomial being irreducible when it
                   has no irreducible factors of low degree. This
                   probability is useful in the analysis of various
                   algorithms for factoring polynomials over finite
                   fields. We present an experimental comparison of
                   these irreducibility methods when testing random
                   polynomials.},
  isbn      = {978-3-642-60539-0},
}

@InProceedings{10.1007/BFb0052240,
  author    = {Lim, Chae Hoon and Lee, Pil Joong},
  title     = {A key recovery attack on discrete log-based schemes using a prime order subgroup},
  booktitle = {Advances in Cryptology --- CRYPTO '97},
  year      = {1997},
  editor    = {Kaliski, Burton S.},
  pages     = {249--263},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  abstract  = {Consider the well-known oracle attack: somehow one
                   gets a certain computation result as a function of a
                   secret key from the secret key owner and tries to
                   extract some information on the secret key. This
                   attacking scenario is well understood in the
                   cryptographic community. However, there are many
                   protocols based on the discrete logarithm problem
                   that turn out to leak many of the secret key bits
                   from this oracle attack, unless suitable checkings
                   are carried out. In this paper we present a key
                   recovery attack on various discrete log-based schemes
                   working in a prime order subgroup. Our attack may
                   reveal part of, or the whole secret key in most
                   Diffie-Hellman-type key exchange protocols and some
                   applications of ElGamal encryption and signature
                   schemes.},
  isbn      = {978-3-540-69528-8},
}

@InProceedings{10.1007/BFb0099440,
  author    = {Cohen, Henri and Lenstra, Hendrik W.},
  title     = {Heuristics on class groups of number fields},
  booktitle = {Number Theory Noordwijkerhout 1983},
  year      = {1984},
  editor    = {Jager, Hendrik},
  pages     = {33--62},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin Heidelberg},
  isbn      = {978-3-540-38906-4},
}

@Article{10.2307/24522768,
  author    = {David Harvey},
  title     = {Counting points on hyperelliptic curves in average polynomial time},
  journal   = {Annals of Mathematics},
  year      = {2014},
  volume    = {179},
  number    = {2},
  pages     = {783--803},
  issn      = {0003486X},
  abstract  = {Let g ≥ 1, and let Q ∈ Z[x] be a monic,
                   squarefree polynomial of degree 2g + 1. For an odd
                   prime p not dividing the discriminant of Q, let Zp(T)
                   denote the zeta function of the hyperelliptic curve
                   of genus g over the finite field Fp obtained by
                   reducing the coefficients of the equation y2 = Q(x)
                   modulo p. We present an explicit deterministic
                   algorithm that given as input Q and a positive
                   integer N, computes Zp(T) simultaneously for all such
                   primes p < N, whose average complexity per prime is
                   polynomial in g, log N, and the number of bits
                   required to represent Q.},
  publisher = {Annals of Mathematics},
  url       = {http://www.jstor.org/stable/24522768},
}

@InProceedings{Adleman-Lenstra,
  author    = {Adleman, Leonard M. and Lenstra, Hendrik W.},
  title     = {Finding Irreducible Polynomials over Finite Fields},
  booktitle = {Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing},
  year      = {1986},
  series    = {STOC '86},
  pages     = {350--355},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/12130.12166},
  isbn      = {0-89791-193-8},
}

@Article{Allombert02,
  author  = {Bill Allombert},
  title   = {Explicit Computation of Isomorphisms between Finite Fields},
  journal = {Finite Fields and Their Applications},
  year    = {2002},
  volume  = {8},
  number  = {3},
  pages   = {332--342},
  doi     = {10.1006/ffta.2001.0344},
}

@Electronic{Allombert02-rev,
  author = {Bill Allombert},
  year   = {2002},
  title  = {Explicit Computation of Isomorphisms between Finite Fields},
  note   = {Revised version},
  url    = {https://www.math.u-bordeaux.fr/~ballombe/fpisom.ps},
  number = {3},
  pages  = {332--342},
  volume = {8},
}

@InProceedings{antipa+brown+gallant+lambert+struik+vanstone06,
  author    = {Antipa, Adrian and Brown, Daniel and Gallant, Robert and Lambert, Rob and Struik, Ren\'{e} and Vanstone, Scott},
  title     = {Accelerated Verification of {ECDSA} Signatures},
  booktitle = {Selected Areas in Cryptography 2005},
  year      = {2006},
  volume    = {3897},
  series    = {Lecture Notes in Computer Science},
  pages     = {307--318},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin / Heidelberg},
  abstract  = {{Verification of ECDSA signatures is considerably
                   slower than generation of ECDSA signatures. This
                   paper describes a method that can be used to
                   accelerate verification of ECDSA signatures by more
                   than 40\% with virtually no added implementation
                   complexity. The method can also be used to accelerate
                   verification for other ElGamal-like signature
                   algorithms, including DSA.}},
  chapter   = {21},
  doi       = {10.1007/11693383_21},
  isbn      = {978-3-540-33108-7},
}

@Electronic{atkin91,
  author       = {Atkin, Arthur O. L.},
  year         = {1991},
  title        = {The number of points on an elliptic curve modulo a prime},
  howpublished = {Manuscript, Chicago IL},
  url          = {http://www.lix.polytechnique.fr/Labo/Francois.Morain/AtkinEmails/19910614.txt},
}

@Electronic{atkin92,
  author       = {Atkin, Arthur O. L.},
  year         = {1992},
  title        = {The number of points on an elliptic curve modulo a prime (II)},
  howpublished = {\url{http://www.lix.polytechnique.fr/Labo/Francois.Morain/AtkinEmails/19910614.txt}},
  url          = {http://www.lix.polytechnique.fr/Labo/Francois.Morain/AtkinEmails/19920319.txt},
}

@Article{AtkinMorain93,
  author  = {Atkin, Arthur O. L. and Morain, François},
  title   = {Elliptic curves and primality proving},
  journal = {Mathematics of Computation},
  year    = {1993},
  volume  = {61},
  number  = {203},
  pages   = {29--68},
  issn    = {0025-5718},
  doi     = {10.2307/2152935},
}

@Article{Aubry:1999:TTS:2947511.2947551,
  author    = {Aubry, Philippe and Lazard, Daniel and Moreno Maza, Marc},
  title     = {On the Theories of Triangular Sets},
  journal   = {Journal of Symbolic Computation},
  year      = {1999},
  volume    = {28},
  number    = {1},
  pages     = {105--124},
  month     = jul,
  issn      = {0747-7171},
  address   = {Duluth, MN, USA},
  doi       = {10.1006/jsco.1999.0269},
  publisher = {Academic Press, Inc.},
}

@PhdThesis{belding08-thesis,
  author   = {Belding, Juliana V.},
  title    = {Number Theoretic Algorithms for Elliptic Curves},
  school   = {University of Maryland},
  year     = {2008},
  abstract = {We present new algorithms related to both theoretical
                   and practical questions in the area of elliptic
                   curves and class field theory. The dissertation has
                   two main parts, as described below. Let O be an
                   imaginary quadratic order of discriminant D < 0, and
                   let K = √ Q( D). The class polynomial HD of O is
                   the polynomial whose roots are precisely the
                   j-invariants of elliptic curves with complex
                   multiplication by O. Computing this polynomial is
                   useful in constructing elliptic curves suitable for
                   cryptography, as well as in the context of explicit
                   class field theory. In the first part of the
                   dissertation, we present an algorithm to compute HD
                   p-adically where p is a prime inert in K and not
                   dividing D. ̃ This involves computing the canonical
                   lift E of a pair (E, f ) where E is a supersingular
                   elliptic curve and f is an embedding of O into the
                   endomorphism ring of E. We also present an algorithm
                   to compute HD modulo p for p inert which is used in
                   the Chinese remainder theorem algorithm to compute HD
                   . For an elliptic curve E over any field K, the Weil
                   pairing en is a bilinear map on the points of order n
                   of E. The Weil pairing is a useful tool in both the
                   theory of elliptic curves and the application of
                   elliptic curves to cryptography. However, for K of
                   characteristic p, the classical Weil pairing on the
                   points of order p is trivial. In the second part of
                   the dissertation, we consider E over the dual numbers
                   K[ ] and define a non-degenerate ” Weil pairing on
                   p-torsion.” We show that this pairing satisfies
                   many of the same properties of the classical pairing.
                   Moreover, we show that it directly relates to recent
                   attacks on the discrete logarithm problem on the
                   p-torsion subgroup of an elliptic curve over the
                   finite field Fq . We also present a new attack on the
                   discrete logarithm problem on anomalous curves using
                   a lift of E over Fp [ ].},
}

@InProceedings{Ben-Or1981,
  author    = {Ben-Or, Michael},
  title     = {Probabilistic algorithms in finite fields},
  booktitle = {22nd Annual Symposium on Foundations of Computer Science ({SFCS} 1981)},
  year      = {1981},
  pages     = {394--398},
  month     = oct,
  doi       = {10.1109/SFCS.1981.37},
  issn      = {0272-5428},
}

@Article{berlekamp1970factoring,
  author  = {Berlekamp, Elwyn R.},
  title   = {Factoring polynomials over large finite fields},
  journal = {Mathematics of computation},
  year    = {1970},
  volume  = {24},
  number  = {111},
  pages   = {713--735},
  doi     = {10.1090/S0025-5718-1970-0276200-X},
}

@Article{Berlekamp82,
  author  = {Berlekamp, Elwyn R.},
  title   = {Bit-serial {R}eed--{S}olomon encoders},
  journal = {IEEE Transactions on Information Theory},
  year    = {1982},
  volume  = {28},
  number  = {6},
  pages   = {869--874},
}

@InProceedings{BGPS05,
  author    = {Bostan, Alin and Gonz{\'a}lez-Vega, Laureano and Perdry, Hervé and Schost, {\'E}ric},
  title     = {From {N}ewton sums to coefficients: complexity issues in characteristic $p$},
  booktitle = {MEGA'05},
  year      = {2005},
}

@Article{bisson+sutherland11,
  author   = {Bisson, Gaetan and Sutherland, Andrew V.},
  title    = {Computing the endomorphism ring of an ordinary elliptic curve over a finite field},
  journal  = {Journal of Number Theory},
  year     = {2011},
  volume   = {131},
  number   = {5},
  pages    = {815--831},
  month    = may,
  issn     = {0022314X},
  abstract = {We present two algorithms to compute the endomorphism
                   ring of an ordinary elliptic curve E defined over a
                   finite field . Under suitable heuristic assumptions,
                   both have subexponential complexity. We bound the
                   complexity of the first algorithm in terms of , while
                   our bound for the second algorithm depends primarily
                   on {log|DE}|, where {DE} is the discriminant of the
                   order isomorphic to {End(E}). As a byproduct, our
                   method yields a short certificate that may be used to
                   verify that the endomorphism ring is as claimed.},
  doi      = {10.1016/j.jnt.2009.11.003},
}

@Book{blake+seroussi+smart,
  title     = {Elliptic curves in cryptography},
  publisher = {Cambridge University Press},
  year      = {1999},
  author    = {Blake, Ian F. and Seroussi, Gadiel and Smart, Nigel P.},
  address   = {New York, NY, USA},
  isbn      = {0-521-65374-6},
}

@Article{BoFlSaSc06,
  author   = {Alin Bostan and Philippe Flajolet and Bruno Salvy and Éric Schost},
  title    = {Fast computation of special resultants},
  journal  = {Journal of Symbolic Computation},
  year     = {2006},
  volume   = {41},
  number   = {1},
  pages    = {1--29},
  issn     = {0747-7171},
  abstract = {We propose fast algorithms for computing composed
                   products and composed sums, as well as diamond
                   products of univariate polynomials. These operations
                   correspond to special multivariate resultants, that
                   we compute using power sums of roots of polynomials,
                   by means of their generating series.},
  doi      = {10.1016/j.jsc.2005.07.001},
}

@Article{bosma+cannon+steel97,
  author    = {Bosma, Wieb and Cannon, John and Steel, Allan},
  title     = {Lattices of compatibly embedded finite fields},
  journal   = {Journal of Symbolic Computation},
  year      = {1997},
  volume    = {24},
  number    = {3-4},
  pages     = {351--369},
  issn      = {0747-7171},
  address   = {Duluth, MN, USA},
  doi       = {10.1006/jsco.1997.0138},
  publisher = {Academic Press, Inc.},
}

@InProceedings{bostan+lecerf+schost:tellegen,
  author    = {Bostan, Alin and Lecerf, Gr{\'e}goire and Schost, \'{E}ric},
  title     = {{T}ellegen's principle into practice},
  booktitle = {ISSAC'03},
  year      = {2003},
  pages     = {37--44},
  publisher = {ACM},
  abstract  = {The transposition principle, also called Tellegen's
                   principle, is a set of transformation rules for
                   linear programs. Yet, though well known, it is not
                   used systematically, and few practical
                   implementations rely on it. In this article, we
                   propose explicit transposed versions of polynomial
                   multiplication and division but also new faster
                   algorithms for multipoint evaluation, interpolation
                   and their transposes. We report on their
                   implementation in Shoup's {NTL} C++ library.},
  doi       = {10.1145/860854.860870},
  isbn      = {1-58113-641-2},
}

@Article{bostan+morain+salvy+schost08,
  author   = {Bostan, Alin and Morain, Fran\c{c}ois and Salvy, Bruno and Schost, {\'{E}}ric},
  title    = {Fast algorithms for computing isogenies between elliptic curves},
  journal  = {Mathematics of Computation},
  year     = {2008},
  volume   = {77},
  number   = {263},
  pages    = {1755--1778},
  month    = sep,
  issn     = {0025-5718},
  abstract = {We survey algorithms for computing isogenies between
                   elliptic curvesdefined over a field of characteristic
                   either 0 or a large prime. Weintroduce a new
                   algorithm that computes an isogeny of degree ell (
                   elldifferent from the characteristic) in time
                   quasi-linear with respect to ell E This is based in
                   particular on fast algorithms for power
                   seriesexpansion of the Weierstrass wp -function and
                   related functions.},
  doi      = {10.1090/S0025-5718-08-02066-8},
}

@Article{bostan+salvy+schost03,
  author   = {Bostan, Alin and Salvy, Bruno and Schost, \'{E}ric},
  title    = {Fast Algorithms for Zero-Dimensional Polynomial Systems using Duality},
  journal  = {Applicable Algebra in Engineering, Communication and Computing},
  year     = {2003},
  volume   = {14},
  number   = {4},
  pages    = {239--272},
  month    = nov,
  issn     = {0938-1279},
  abstract = {Many questions concerning a zero-dimensional
                   polynomial system can be reduced to linear algebra
                   operations in the quotient algebra A= k[ X 1,…, X
                   n]/I, where I is the ideal generated by the input
                   system. Assuming that the multiplicative structure of
                   the algebra A is (partly) known, we address the
                   question of speeding up the linear algebra phase for
                   the computation of minimal polynomials and rational
                   parametrizations in A. We present new formul{\ae} for
                   the rational parametrizations, extending those of
                   Rouillier, and algorithms extending ideas introduced
                   by Shoup in the univariate case. Our approach is
                   based on the A-module structure of the dual space
                   \$\widehat{A}\$ . An important feature of our
                   algorithms is that we do not require \$\widehat{A}\$
                   to be free and of rank 1. The complexity of our
                   algorithms for computing the minimal polynomial and
                   the rational parametrizations are O(2 nD 5/2) and O(
                   n2 nD 5/2) respectively, where D is the dimension of
                   A. For fixed n, this is better than algorithms based
                   on linear algebra except when the complexity of the
                   available matrix product has exponent less than 5/2.},
  doi      = {10.1007/s00200-003-0133-5},
}

@Book{Bostan10,
  title  = {Algorithmes rapides pour les polyn\^omes, s\'eries formelles et matrices},
  year   = {2010},
  author = {Alin Bostan},
  volume = {1},
  number = {2},
  series = {Les cours du CIRM},
  url    = {https://hal.inria.fr/hal-00780433/},
}

@Book{BourbakiAlgCom9,
  title     = {\'{E}l\'ements de math\'ematique},
  publisher = {Springer},
  year      = {2007},
  author    = {Bourbaki, Nicolas},
  note      = {Alg{\`e}bre. Chapitre 9},
}

@Article{BrCa87,
  author   = {Joel V. Brawley and Leonard Carlitz},
  title    = {Irreducibles and the composed product for polynomials over a finite field},
  journal  = {Discrete Mathematics},
  year     = {1987},
  volume   = {65},
  number   = {2},
  pages    = {115--139},
  issn     = {0012-365X},
  abstract = {Let GF(q) denote the finite field of q elements and
                   let GF[q,x] denote the integral domain of polynomials
                   in an indeterminate x over GF(q). Further, let Γ =
                   Γ(q) denote the algebraic closure of GF(q) so that
                   every polynomial in GF[q,x] on which there is defined
                   a binary considers certain sets of monic polynomials
                   from GF[q,x] on which there is defined a binary
                   operation called the composed product. Here, if f and
                   g are monics in GF[q,x] with deg f = m and deg g=n,
                   then the composed product, denoted by f♦g and
                   defined in terms of the roots of f and g, is also in
                   GF[q,x] and has degree mn. In the present paper, the
                   two most important composed products, denoted by the
                   special symbols Ō and ∗, are those induced by the
                   field multiplication and the field addition on Γ and
                   defined by: f∘g = Π Παβ (x − αβ), f∗g =
                   Π Παβ (x − (α+β)), where the products
                   indicated by П are the usual products in Γ[x] and
                   are taken over all the roots α of f and β of g,
                   (including multiplicities). These two composed
                   products are called composed multiplication and
                   composed addition, respectively. After introducing
                   and developing some theory concerning a more general
                   notion of composed product, this paper moves to the
                   special composed products above and asks whether the
                   irreducibles over GF(q) can be factored uniquely into
                   indecomposables with respect to each of these
                   products. Here, the term “irreducible” is used in
                   the usual sense of the word while the term
                   “indecomposable” is used in reference to composed
                   products. This question is shown to have an
                   affirmative answer in both situations, and thus yield
                   unique factorization theorems (multiplicative and
                   additive) for Γ. These theorems are then used to
                   prove corresponding unique factorization theorems for
                   all subfields of Γ. Next, it is shown that there are
                   no irreducibles f in GF[q,x] which can be decomposed
                   as f=f1Ōg1=f2∗g2 (except for trivial
                   decompositions). A special inversion formula is then
                   derived and using this inversion formula, the authors
                   determine the numbers of irreducibles of degree n
                   which are indecomposable with respect to (i) composed
                   multiplication Ō, (ii) composed addition ∗, and
                   (iii) both the composed products Ō and ∗
                   simultaneously. These numbers are given in terms of
                   the well-known number of irreducibles of degree n
                   over GF(q). A final section contains some discussion
                   and several observations about the more general
                   composed product.},
  doi      = {10.1016/0012-365X(87)90135-X},
}

@Article{brent+kung,
  author    = {Brent, Richard P. and Kung, Hsiang Te},
  title     = {Fast Algorithms for Manipulating Formal Power Series},
  journal   = {Journal of the ACM},
  year      = {1978},
  volume    = {25},
  number    = {4},
  pages     = {581--595},
  issn      = {0004-5411},
  abstract  = {Note: {OCR} errors may be found in this Reference
                   List extracted from the full text article. {ACM} has
                   opted to expose the complete List rather than only
                   correct and linked references.},
  address   = {New York, NY, USA},
  doi       = {10.1145/322092.322099},
  publisher = {ACM},
}

@Article{brieulle2018computing,
  author  = {Brieulle, Ludovic and De Feo, Luca and Doliskani, Javad and Flori, Jean-Pierre and Schost, {\'E}ric},
  title   = {Computing isomorphisms and embeddings of finite fields},
  journal = {Mathematics of Computation},
  year    = {2019},
  number  = {88},
  pages   = {1391--1426},
  doi     = {10.1090/mcom/3363},
}

@Article{Broeker2009,
  author    = {Bröker, Reinier and Lauter, Kristin},
  title     = {Modular Polynomials for Genus 2},
  journal   = {LMS Journal of Computation and Mathematics},
  year      = {2009},
  volume    = {12},
  pages     = {326--339},
  doi       = {10.1112/S1461157000001546},
  publisher = {Cambridge University Press},
}

@Article{broker-ss,
  author  = {Br{\"o}ker, Reinier},
  title   = {Constructing supersingular elliptic curves},
  journal = {Journal of Combinatorics and Number Theory},
  year    = {2009},
  volume  = {1},
  number  = {3},
  pages   = {269--273},
  issn    = {1942-5600},
}

@Article{Brooks2017,
  author   = {Brooks, Ernest Hunter and Jetchev, Dimitar and Wesolowski, Benjamin},
  title    = {Isogeny graphs of ordinary abelian varieties},
  journal  = {Research in Number Theory},
  year     = {2017},
  volume   = {3},
  number   = {1},
  pages    = {28},
  month    = nov,
  issn     = {2363-9555},
  abstract = {Fix a prime number {\$}{\$}{\backslash}ell {\$}{\$}
                   ℓ . Graphs of isogenies of degree a power of
                   {\$}{\$}{\backslash}ell {\$}{\$} ℓ are
                   well-understood for elliptic curves, but not for
                   higher-dimensional abelian varieties. We study the
                   case of absolutely simple ordinary abelian varieties
                   over a finite field. We analyse graphs of so-called
                   {\$}{\$}{\backslash}mathfrak l{\$}{\$} l -isogenies,
                   resolving that, in arbitrary dimension, their
                   structure is similar, but not identical, to the
                   ``volcanoes'' occurring as graphs of isogenies of
                   elliptic curves. Specializing to the case of
                   principally polarizable abelian surfaces, we then
                   exploit this structure to describe graphs of a
                   particular class of isogenies known as
                   {\$}{\$}({\backslash}ell , {\backslash}ell ){\$}{\$}
                   ( ℓ , ℓ ) -isogenies: those whose kernels are
                   maximal isotropic subgroups of the
                   {\$}{\$}{\backslash}ell {\$}{\$} ℓ -torsion for the
                   Weil pairing. We use these two results to write an
                   algorithm giving a path of computable isogenies from
                   an arbitrary absolutely simple ordinary abelian
                   surface towards one with maximal endomorphism ring,
                   which has immediate consequences for the CM-method in
                   genus 2, for computing explicit isogenies, and for
                   the random self-reducibility of the discrete
                   logarithm problem in genus 2 cryptography.},
  doi      = {10.1007/s40993-017-0087-5},
}

@Article{BruinierOS16,
  author  = {Jan Hendrik Bruinier and Ken Ono and Andrew V. Sutherland},
  title   = {Class polynomials for nonholomorphic modular functions},
  journal = {Journal of Number Theory},
  year    = {2016},
  volume  = {161},
  pages   = {204--229},
  issn    = {0022-314X},
  doi     = {10.1016/j.jnt.2015.07.002},
}

@Article{Buchmann1988,
  author   = {Buchmann, Johannes and Williams, Hugh C.},
  title    = {A key-exchange system based on imaginary quadratic fields},
  journal  = {Journal of Cryptology},
  year     = {1988},
  volume   = {1},
  number   = {2},
  pages    = {107--118},
  month    = jun,
  issn     = {1432-1378},
  abstract = {We describe another key-exchange system which, while
                   based on the general idea of the well-known scheme of
                   Diffie and Hellman, seems to be more secure than that
                   technique. The new system is based on the arithmetic
                   of an imaginary quadratic field, and makes use,
                   specifically, of the properties of the class group of
                   such a field.},
  doi      = {10.1007/BF02351719},
}

@Book{burgisser+clausen-shokrollahi,
  title        = {Algebraic Complexity Theory},
  publisher    = {Springer},
  year         = {1997},
  author       = {B\"{u}rgisser, Peter and Clausen, Michael and Shokrollahi, M. Amin},
  month        = feb,
  isbn         = {3540605827},
  abstract     = {This is the first book to present an up-to-date and
                   self-contained account of Algebraic Complexity Theory
                   that is both comprehensive and unified. Requiring of
                   the reader only some basic algebra and offering over
                   350 exercises, it is well-suited as a textbook for
                   beginners at graduate level. With its extensive
                   bibliography covering about 500 research papers, this
                   text is also an ideal reference book for the
                   professional researcher. The subdivision of the
                   contents into 21 more or less independent chapters
                   enables readers to familiarize themselves quickly
                   with a specific topic, and facilitates the use of
                   this book as a basis for complementary courses in
                   other areas such as computer algebra.},
  howpublished = {Hardcover},
}

@InProceedings{canetti,
  author    = {Canetti, Ran and Krawczyk, Hugo},
  title     = {Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels},
  booktitle = {EUROCRYPT},
  year      = {2001},
  editor    = {Birgit Pfitzmann},
  volume    = {2045},
  series    = {Lecture Notes in Computer Science},
  pages     = {453--474},
  publisher = {Springer},
  isbn      = {3-540-42070-3},
}

@InProceedings{canny+kaltofen+yagati89,
  author    = {Canny, John F. and Kaltofen, Eric and Yagati, Lakshman N.},
  title     = {Solving systems of nonlinear polynomial equations faster},
  booktitle = {ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation},
  year      = {1989},
  pages     = {121--128},
  address   = {New York, NY, USA},
  publisher = {ACM},
  abstract  = {Note: {OCR} errors may be found in this Reference
                   List extracted from the full text article. {ACM} has
                   opted to expose the complete List rather than only
                   correct and linked references.},
  doi       = {10.1145/74540.74556},
  isbn      = {0-89791-325-6},
}

@Article{cantor+kaltofen91,
  author    = {Cantor, David G. and Kaltofen, Erich},
  title     = {On fast multiplication of polynomials over arbitrary algebras},
  journal   = {Acta Informatica},
  year      = {1991},
  volume    = {28},
  number    = {7},
  pages     = {693--701},
  month     = jul,
  issn      = {0001-5903},
  doi       = {10.1007/BF01178683},
  publisher = {Springer},
}

@Article{cantor1981,
  author    = {Cantor, David G and Zassenhaus, Hans},
  title     = {A {N}ew {A}lgorithm for {F}actoring {P}olynomials over {F}inite {F}ields},
  journal   = {Mathematics of Computation},
  year      = {1981},
  pages     = {587--592},
  publisher = {JSTOR},
}

@Article{cantor89,
  author    = {Cantor, David G.},
  title     = {On arithmetical algorithms over finite fields},
  journal   = {Journal of Combinatiorial Theory},
  year      = {1989},
  volume    = {50},
  number    = {2},
  pages     = {285--300},
  issn      = {0097-3165},
  address   = {Orlando, FL, USA},
  doi       = {10.1016/0097-3165(89)90020-4},
  publisher = {Academic Press, Inc.},
  series    = {Series A},
}

@Article{castryck+hubrechts13,
  author    = {Castryck, Wouter and Hubrechts, Hendrik},
  title     = {The distribution of the number of points modulo an integer on elliptic curves over finite fields},
  journal   = {The Ramanujan Journal},
  year      = {2013},
  volume    = {30},
  number    = {2},
  pages     = {223--242},
  publisher = {Springer},
}

@Misc{cervino04,
  author   = {Cervi\~{n}o, Juan M.},
  title    = {On the Correspondence between Supersingular Elliptic Curves and maximal quaternionic Orders},
  month    = apr,
  year     = {2004},
  abstract = {We present a deterministic and explicit algorithm to
                   compute the endomorphism rings of supersingular
                   elliptic curves. As an example we compute the
                   endomorphism rings of all supersingular elliptic
                   curves defined over characteristic p=29,...,97.},
  url      = {http://arxiv.org/abs/math/0404538},
}

@Misc{charlap1991enumeration,
  author    = {Charlap, Leonard S and Coley, Raymond and Robbins, David P},
  title     = {Enumeration of rational points on elliptic curves over finite fields},
  year      = {1991},
  note      = {Preprint},
  publisher = {Draft},
}

@Article{chung1989diameters,
  author  = {Chung, Fan R.K.},
  title   = {Diameters and eigenvalues},
  journal = {Journal of the American Mathematical Society},
  year    = {1989},
  volume  = {2},
  number  = {2},
  pages   = {187--196},
}

@Article{Ciet2005,
  author  = {Ciet, Mathieu and Joye, Marc},
  title   = {Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Faults},
  journal = {Designs, Codes and Cryptography},
  year    = {2005},
  volume  = {36},
  number  = {1},
  pages   = {33--43},
  month   = jul,
  issn    = {1573-7586},
  doi     = {10.1007/s10623-003-1160-8},
}

@Article{CL08,
  author  = {Couveignes, Jean-Marc and Lercier, Reynald},
  title   = {Galois invariant smoothness basis},
  journal = {Series on Number Theory and Its Applications},
  year    = {2008},
  volume  = {5},
  pages   = {142--167},
  month   = may,
  note    = {World Scientific},
}

@Book{Cohen1993,
  title     = {A Course in Computational Algebraic Number Theory},
  publisher = {Springer-Verlag New York, Inc.},
  year      = {1993},
  author    = {Cohen, Henri},
  address   = {New York, NY, USA},
  isbn      = {0-387-55640-0},
}

@Book{Conway:ONAG2000,
  title        = {On Numbers and Games},
  publisher    = {AK Peters, Ltd.},
  year         = {2000},
  author       = {Conway, John H.},
  edition      = {2nd edition},
  month        = dec,
  isbn         = {1568811276},
  abstract     = {{ONAG, as the book is known, is one of those rare
                   publications that sprang to life in a moment of
                   creative energy and has remained influential for over
                   a quarter of a century. Still in high demand, it is
                   being republished with some adjustments and
                   corrections. The original motivation for writing the
                   book was an attempt to understand the relation
                   between the theories of transfinite numbers and
                   mathematical games. By defining numbers as the
                   strengths of positions in certain games, the author
                   arrives at a new class, the surreal numbers (so named
                   by Donald Knuth) that includes at the same time the
                   real numbers and the ordinal numbers. <P>This new
                   edition ends with an epilogue that sets the stage for
                   further research on surreal numbers. The book is a
                   must-have for all readers with a serious interest in
                   the mathematical foundations of game strategies.}},
  howpublished = {Hardcover},
}

@Article{coppersmith+winograd,
  author    = {Coppersmith, Don and Winograd, Shmuel},
  title     = {Matrix multiplication via arithmetic progressions},
  journal   = {Journal of Symbolic Computation},
  year      = {1990},
  volume    = {9},
  number    = {3},
  pages     = {251--280},
  issn      = {07477171},
  abstract  = {We present a new method for accelerating matrix
                   multiplication asymptotically. Thiswork builds on
                   recent ideas of Volker Strassen, by using a basic
                   trilinear form which is not a matrix product. We make
                   novel use of the {Salem-Spencer} Theorem, which gives
                   a fairly dense set of integers with no three-term
                   arithmetic progression. Our resulting matrix exponent
                   is 2.376.},
  address   = {Duluth, MN, USA},
  doi       = {10.1016/S0747-7171(08)80013-2},
  publisher = {Academic Press, Inc.},
}

@Article{cosset2015computing,
  author  = {Cosset, Romain and Robert, Damien},
  title   = {Computing $(\ell, \ell)$-isogenies in polynomial time on Jacobians of genus 2 curves},
  journal = {Mathematics of Computation},
  year    = {2015},
  volume  = {84},
  number  = {294},
  pages   = {1953--1975},
}

@Article{CostelloSmith2017,
  author    = {Costello, Craig and Smith, Benjamin},
  title     = {Montgomery curves and their arithmetic},
  journal   = {Journal of Cryptographic Engineering},
  year      = {2017},
  doi       = {10.1007/s13389-017-0157-6},
  publisher = {Springer},
  series    = {Special issue on Montgomery arithmetic},
  url       = {https://hal.inria.fr/hal-01483768},
}

@Article{couveignes+lercier11,
  author    = {Couveignes, Jean-Marc and Lercier, Reynald},
  title     = {Fast construction of irreducible polynomials over finite fields},
  journal   = {Israel Journal of Mathematics},
  year      = {2013},
  volume    = {194},
  number    = {1},
  pages     = {77--105},
  publisher = {Springer},
}

@InProceedings{couveignes+morain94,
  author    = {Couveignes, Jean-Marc and Morain, François},
  title     = {Schoof's algorithm and isogeny cycles},
  booktitle = {ANTS-I: Proceedings of the First International Symposium on Algorithmic Number Theory},
  year      = {1994},
  volume    = {877},
  series    = {Lecture Notes in Computer Science},
  pages     = {43--58},
  address   = {London, UK},
  publisher = {Springer},
  isbn      = {3-540-58691-1},
}

@Article{couveignes00,
  author    = {Couveignes, Jean-Marc},
  title     = {Isomorphisms between {A}rtin-{S}chreier towers},
  journal   = {Mathematics of Computation},
  year      = {2000},
  volume    = {69},
  number    = {232},
  pages     = {1625--1631},
  issn      = {0025-5718},
  address   = {Boston, MA, USA},
  doi       = {10.1090/S0025-5718-00-01193-5},
  publisher = {American Mathematical Society},
}

@PhdThesis{couveignes94,
  author = {Couveignes, Jean-Marc},
  title  = {{Quelques calculs en th{\'{e}}orie des nombres}},
  school = {Universit\'{e} de Bordeaux},
  year   = {1994},
}

@InProceedings{couveignes96,
  author    = {Couveignes, Jean-Marc},
  title     = {Computing $\ell$-isogenies using the $p$-Torsion},
  booktitle = {ANTS-II: Proceedings of the Second International Symposium on Algorithmic Number Theory},
  year      = {1996},
  pages     = {59--65},
  address   = {London, UK},
  publisher = {Springer-Verlag},
  isbn      = {3-540-61581-4},
}

@Book{Cox-Little-OShea:UAG2005,
  title        = {Using Algebraic Geometry},
  publisher    = {Springer-Verlag},
  year         = {2005},
  author       = {Cox, David A. and Little, John and O'Shea, Donal},
  isbn         = {0387207066},
  abstract     = {In recent years, the discovery of new algorithms for
                   dealing with polynomial equations, coupled with their
                   implementation on fast inexpensive computers, has
                   sparked a minor revolution in the study and practice
                   of algebraic geometry. These algorithmic methods have
                   also given rise to some exciting new applications of
                   algebraic geometry. This book illustrates the many
                   uses of algebraic geometry, highlighting some of the
                   more recent applications of Gr\"{o}bner bases and
                   resultants. In order to do this, the authors provide
                   an introduction to some algebraic objects and
                   techniques which are more advanced than one typically
                   encounters in a first course, but nonetheless of
                   great utility. The book is written for nonspecialists
                   and for readers with a diverse range of backgrounds.
                   It assumes knowledge of the material covered in a
                   standard undergraduate course in abstract algebra,
                   and it would help to have some previous exposure to
                   Gr\"{o}bner bases. The book does not assume the
                   reader is familiar with more advanced concepts such
                   as modules. For this new edition the authors added
                   two new sections and a new chapter, updated the
                   references and made numerous minor improvements
                   throughout the text.},
  howpublished = {Hardcover},
}

@Misc{cryptoeprint:1999:007,
  author       = {Abdalla, Michel and Bellare, Mihir and Rogaway, Phillip},
  title        = {{DHAES}: An Encryption Scheme Based on the {D}iffie--{H}ellman Problem},
  howpublished = {Cryptology ePrint Archive, Report 1999/007},
  year         = {1999},
  url          = {https://eprint.iacr.org/1999/007},
}

@Proceedings{DBLP:conf/ants/2006,
  title     = {Algorithmic Number Theory, 7th International Symposium, ANTS-VII, Berlin, Germany, July 23-28, 2006, Proceedings},
  year      = {2006},
  editor    = {Florian Hess and Sebastian Pauli and Michael E. Pohst},
  volume    = {4076},
  series    = {Lecture Notes in Computer Science},
  publisher = {Springer},
  isbn      = {3-540-36075-1},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ants/2006},
}

@Proceedings{DBLP:conf/eurocrypt/2001,
  title     = {Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding},
  year      = {2001},
  editor    = {Birgit Pfitzmann},
  volume    = {2045},
  series    = {Lecture Notes in Computer Science},
  publisher = {Springer},
  isbn      = {3-540-42070-3},
  booktitle = {EUROCRYPT},
}

@Proceedings{DBLP:conf/pkc/2000,
  title     = {Public Key Cryptography, Third International Workshop on Practice and Theory in Public Key Cryptography, {PKC} 2000, Melbourne, Victoria, Australia, January 18-20, 2000, Proceedings},
  year      = {2000},
  editor    = {Hideki Imai and Yuliang Zheng},
  volume    = {1751},
  series    = {Lecture Notes in Computer Science},
  publisher = {Springer},
  isbn      = {3-540-66967-1},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/pkc/2000},
}

@Proceedings{DBLP:conf/pqcrypto/2011,
  title     = {Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 - December 2, 2011. Proceedings},
  year      = {2011},
  editor    = {Bo-Yin Yang},
  volume    = {7071},
  series    = {Lecture Notes in Computer Science},
  publisher = {Springer},
  isbn      = {978-3-642-25404-8},
  booktitle = {PQCrypto},
}

@InProceedings{DeDoSc13,
  author    = {De Feo, Luca and Doliskani, Javad and Schost, \'{E}ric},
  title     = {Fast Algorithms for $\ell$-adic Towers over Finite Fields},
  booktitle = {Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation},
  year      = {2013},
  series    = {ISSAC '13},
  pages     = {165--172},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/2465506.2465956},
  isbn      = {978-1-4503-2059-7},
}

@InProceedings{DeDoSc2014,
  author    = {De Feo, Luca and Doliskani, Javad and Schost, \'{E}ric},
  title     = {Fast Arithmetic for the Algebraic Closure of Finite Fields},
  booktitle = {Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation},
  year      = {2014},
  series    = {ISSAC '14},
  pages     = {122--129},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/2608628.2608672},
  isbn      = {978-1-4503-2501-1},
}

@Article{defeo2016explicit,
  author    = {De Feo, Luca and Hugounenq, Cyril and Pl{\^u}t, J{\'e}r{\^o}me and Schost, {\'E}ric},
  title     = {Explicit isogenies in quadratic time in any characteristic},
  journal   = {LMS Journal of Computation and Mathematics},
  year      = {2016},
  volume    = {19},
  number    = {A},
  pages     = {267--282},
  doi       = {10.1112/S146115701600036X},
  publisher = {London Mathematical Society},
}

@Article{deuring41,
  author    = {Deuring, Max},
  title     = {Die {T}ypen der {M}ultiplikatorenringe elliptischer {F}unktionenk\"{o}rper},
  journal   = {Abhandlungen aus dem Mathematischen Seminar der Universit\"{a}t Hamburg},
  year      = {1941},
  volume    = {14},
  number    = {1},
  pages     = {197--272},
  month     = dec,
  issn      = {0025-5858},
  doi       = {10.1007/BF02940746},
  publisher = {Springer Berlin / Heidelberg},
}

@InProceedings{df+schost09,
  author    = {De Feo, Luca and Schost, \'{E}ric},
  title     = {Fast arithmetics in {A}rtin-{S}chreier towers over finite fields},
  booktitle = {ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation},
  year      = {2009},
  pages     = {127--134},
  address   = {New York, NY, USA},
  publisher = {ACM},
  abstract  = {An {Artin-Schreier} tower over the finite field F p
                   is a tower of field extensions generated by
                   polynomials of the form X p - X -α. Following Cantor
                   and Couveignes, we give algorithms with quasi-linear
                   time complexity for arithmetic operations in such
                   towers. As an application, we present an
                   implementation of Couveignes' algorithm for computing
                   isogenies between elliptic curves using the p
                   -torsion.},
  doi       = {10.1145/1576702.1576722},
  isbn      = {978-1-60558-609-0},
}

@Article{df+schost12,
  author   = {De Feo, Luca and Schost, {\'E}ric},
  title    = {Fast arithmetics in {A}rtin-{S}chreier towers over finite fields},
  journal  = {Journal of Symbolic Computation},
  year     = {2012},
  volume   = {47},
  number   = {7},
  pages    = {771--792},
  issn     = {07477171},
  abstract = {An {Artin-Schreier} tower over the finite field Fp is
                   a tower of field extensions generated by polynomials
                   of the form {Xp−X}−α. Following Cantor and
                   Couveignes, we give algorithms with quasi-linear time
                   complexity for arithmetic operations in such towers.
                   As an application, we present an implementation of
                   Couveignes' algorithm for computing isogenies between
                   elliptic curves using the p-torsion.},
  doi      = {10.1016/j.jsc.2011.12.008},
}

@PhdThesis{df+thesis,
  author   = {De Feo, Luca},
  title    = {{A}lgorithmes {R}apides pour les {T}ours de {C}orps {F}inis et les {I}sog{\'{e}}nies},
  school   = {Ecole Polytechnique X},
  year     = {2010},
  month    = dec,
  abstract = {{D}ans cette th{\`{e}}se nous appliquons des
                   techniques provenant du calcul formel et de la
                   th{\'{e}}orie des langages afin d'am{\'{e}}liorer
                   les op{\'{e}}rations {\'{e}}l{\'{e}}mentaires dans
                   certaines tours de corps finis. {N}ous appliquons
                   notre construction au probl{\`{e}}me du calcul
                   d'isog{\'{e}}nies entre courbes elliptiques et
                   obtenons une variante plus rapide ({\`{a}} la fois en
                   th{\'{e}}orie et en pratique) de l'algorithme de
                   {C}ouveignes. {L}e document est divis{\'{e}} en
                   quatre parties. {D}ans la partie {I} nous faisons des
                   rappels d'alg{\`{e}}bre et de th{\'{e}}orie de la
                   complexit{\'{e}}. {L}a partie {II} traite du principe
                   de transposition : nous g{\'{e}}n{\'{e}}ralisons des
                   id{\'{e}}es de {B}ostan, {S}chost et {L}ecerf et nous
                   montrons qu'il est possible de transposer
                   automatiquement des programmes sans pertes en
                   complexit{\'{e}}-temps et avec une petite perte en
                   complexit{\'{e}}-espace. {L}a partie {III} combine
                   les r{\'{e}}sultats sur le principe de transposition
                   avec des techniques classiques en th{\'{e}}orie de
                   l'{\'{e}}limination ; nous appliquons ces id{\'{e}}es
                   pour obtenir des algorithmes asymptotiquement
                   optimaux pour l'arithm{\'{e}}tique des tours
                   d'{A}rtin-{S}chreier de corps finis. {N}ous
                   d{\'{e}}crivons aussi une implantation de ces
                   algorithmes. {E}nfin, dans la partie {IV} nous
                   utilisons les r{\'{e}}sultats pr{\'{e}}c{\'{e}}dents
                   afin d'acc{\'{e}}l{\'{e}}rer l'algorithme de
                   {C}ouveignes et de comparer le r{\'{e}}sultat avec
                   les autres algorithmes pour le calcul
                   d'isog{\'{e}}nies qui font l'{\'{e}}tat de l'art.
                   {N}ous pr{\'{e}}sentons aussi une nouvelle
                   g{\'{e}}n{\'{e}}ralisation de l'algorithme de
                   {C}ouveignes qui calcule des isog{\'{e}}nies de
                   degr{\'{e}} inconnu.},
  url      = {http://tel.archives-ouvertes.fr/tel-00547034/en/},
}

@Article{df10,
  author   = {De Feo, Luca},
  title    = {Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic},
  journal  = {Journal of Number Theory},
  year     = {2011},
  volume   = {131},
  number   = {5},
  pages    = {873--893},
  month    = may,
  issn     = {0022-314X},
  abstract = {The problem of computing an explicit isogeny between
                   two given elliptic curves over , originally motivated
                   by point counting, has recently awaken new interest
                   in the cryptology community thanks to the works of
                   Teske and Rostovtsev \& Stolbunov. While the large
                   characteristic case is well understood, only
                   suboptimal algorithms are known in small
                   characteristic; they are due to Couveignes, Lercier,
                   Lercier \& Joux and Lercier \& Sirvent. In this paper
                   we discuss the differences between them and run some
                   comparative experiments. We also present the first
                   complete implementation of Couveignes' second
                   algorithm and present improvements that make it the
                   algorithm having the best asymptotic complexity in
                   the degree of the isogeny.},
  doi      = {10.1016/j.jnt.2010.07.003},
}

@Article{doi:10.1137/S0097539702403773,
  author  = {Ronald Cramer and Victor Shoup},
  title   = {Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack},
  journal = {SIAM Journal on Computing},
  year    = {2003},
  volume  = {33},
  number  = {1},
  pages   = {167--226},
  doi     = {10.1137/S0097539702403773},
}

@Article{doliskanischost2011,
  author  = {Doliskani, Javad and Schost, {\'E}ric},
  title   = {Taking roots over high extensions of finite fields},
  journal = {Mathematics of Computation},
  year    = {2014},
  volume  = {83},
  number  = {285},
  pages   = {435--446},
}

@Article{DoSc12,
  author  = {Doliskani, Javad and Schost, \'Eric},
  title   = {Computing in degree $2^k$-extensions of finite fields of odd characteristic},
  journal = {Designs, Codes and Cryptography},
  year    = {2015},
  volume  = {74},
  number  = {3},
  pages   = {559--569},
}

@Book{DSV,
  title     = {Elementary number theory, group theory, and {R}amanujan graphs},
  publisher = {Cambridge University Press},
  year      = {2003},
  author    = {Davidoff, Giuliana and Sarnak, Peter and Valette, Alain},
  volume    = {55},
  series    = {London Mathematical Society Student Texts},
  address   = {Cambridge},
  doi       = {10.1017/CBO9780511615825},
}

@PhdThesis{dupont2006moyenne,
  author      = {Dupont, R{\'e}gis},
  title       = {Moyenne arithm{\'e}tico-g{\'e}om{\'e}trique, suites de {B}orchardt et applications},
  year        = {2006},
  institution = {École Polytechnique},
  journal     = {{\'E}cole polytechnique, Palaiseau},
}

@Electronic{Echidna,
  author = {David R. Kohel},
  year   = {2018},
  title  = {Echidna databases},
  url    = {http://iml.univ-mrs.fr/~kohel/dbs/},
}

@InProceedings{ECM20,
  author    = {Paul Zimmermann and Bruce Dodson},
  title     = {20 Years of {ECM}},
  booktitle = {Algorithmic Number Theory, 7th International Symposium, ANTS-VII, Berlin, Germany, July 23-28, 2006, Proceedings},
  year      = {2006},
  editor    = {Florian Hess and Sebastian Pauli and Michael E. Pohst},
  volume    = {4076},
  series    = {Lecture Notes in Computer Science},
  pages     = {525--542},
  publisher = {Springer},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ants/ZimmermannD06},
  doi       = {10.1007/11792086\_37},
  isbn      = {3-540-36075-1},
}

@Misc{efd,
  author = {Bernstein, Daniel J. and Lange, Tanja},
  title  = {{Explicit-Formulas Database}},
  year   = {2007},
  url    = {http://www.hyperelliptic.org/EFD/index.html},
}

@Article{elgamal,
  author    = {ElGamal, Taher},
  title     = {A public key cryptosystem and a signature scheme based on discrete logarithms},
  journal   = {IEEE transactions on information theory},
  year      = {1985},
  volume    = {31},
  number    = {4},
  pages     = {469--472},
  publisher = {Institute of Electrical and Electronics Engineers},
}

@Unpublished{elkies92,
  author       = {Elkies, Noam D.},
  title        = {Explicit isogenies},
  year         = {1992},
  howpublished = {Manuscript, Boston MA},
}

@InProceedings{elkies98,
  author    = {Elkies, Noam D.},
  title     = {Elliptic and modular curves over finite fields and related computational issues},
  booktitle = {Computational perspectives on number theory (Chicago, IL, 1995)},
  year      = {1998},
  volume    = {7},
  series    = {Studies in Advanced Mathematics},
  pages     = {21--76},
  address   = {Providence, RI},
  publisher = {AMS International Press},
  url       = {http://www.ams.org/mathscinet-getitem?mr=1486831},
}

@InProceedings{enge+morain03,
  author    = {Enge, Andreas and Morain, Fran\c{c}ois},
  title     = {Fast decomposition of polynomials with known Galois group},
  booktitle = {AAECC'03: Proceedings of the 15th international conference on Applied algebra, algebraic algorithms and error-correcting codes},
  year      = {2003},
  pages     = {254--264},
  address   = {Berlin, Heidelberg},
  publisher = {Springer-Verlag},
  abstract  = {Let {f(X}) be a separable polynomial with
                   coefficients in a field K , generating a field
                   extension {M/K} . If this extension is Galois with a
                   solvable automorphism group, then the equation {f(X})
                   = 0 can be solved by radicals. The first step of the
                   solution consists of splitting the extension {M/K}
                   into intermediate fields. Such computations are
                   classical, and we explain how fast polynomial
                   arithmetic can be used to speed up the process.
                   Moreover, we extend the algorithms to a more general
                   case of extensions that are no longer Galois.
                   Numerical examples are provided, including results
                   obtained with our implementation for Hilbert class
                   fields of imaginary quadratic fields.},
  isbn      = {3-540-40111-3},
}

@Article{enge09,
  author  = {Enge, Andreas},
  title   = {Computing modular polynomials in quasi-linear time},
  journal = {Mathematics of Computation},
  year    = {2009},
  volume  = {78},
  number  = {267},
  pages   = {1809--1824},
}

@Article{feige+fiat+shamir88,
  author    = {Feige, Uriel and Fiat, Amos and Shamir, Adi},
  title     = {Zero-knowledge proofs of identity},
  journal   = {Journal of Cryptology},
  year      = {1988},
  volume    = {1},
  number    = {2},
  pages     = {77--94},
  month     = jun,
  issn      = {0933-2790},
  abstract  = {In this paper we extend the notion of interactive
                   proofs of assertions to interactive proofs of
                   knowledge. This leads to the definition of
                   unrestricted input zero-knowledge proofs of knowledge
                   in which the prover demonstrates possession of
                   knowledge without revealing any computational
                   information whatsoever (not even the one bit revealed
                   in zero-knowledge proofs of assertions). We show the
                   relevance of these notions to identification schemes,
                   in which parties prove their identity by
                   demonstrating their knowledge rather than by proving
                   the validity of assertions. We describe a novel
                   scheme which is provably secure if factoring is
                   difficult and whose practical implementations are
                   about two orders of magnitude faster than RSA-based
                   identification schemes. The advantages of thinking in
                   terms of proofs of knowledge rather than proofs of
                   assertions are demonstrated in two efficient variants
                   of the scheme: unrestricted input zero-knowledge
                   proofs of knowledge are used in the construction of a
                   scheme which needs no directory; a version of the
                   scheme based on parallel interactive proofs (which
                   are not known to be zero knowledge) is proved secure
                   by observing that the identification protocols are
                   proofs of knowledge.},
  doi       = {10.1007/BF02351717},
  publisher = {Springer New York},
}

@Article{feisel1999normal,
  author    = {Feisel, Sandra and von zur Gathen, Joachim and Shokrollahi, M. Amin},
  title     = {Normal bases via general Gauss periods},
  journal   = {Mathematics of Computation},
  year      = {1999},
  volume    = {68},
  number    = {225},
  pages     = {271--290},
  publisher = {American Mathematical Society},
}

@Article{ffisom-long,
  author  = {Brieulle, Ludovic and De Feo, Luca and Doliskani, Javad and Flori, Jean-Pierre and Schost, {\'E}ric},
  title   = {Computing isomorphisms and embeddings of finite fields (extended version)},
  journal = {arXiv preprint arXiv:1705.01221},
  year    = {2017},
  url     = {https://arxiv.org/abs/1705.01221},
}

@InProceedings{Fieker:2017:NCA:3087604.3087611,
  author    = {Fieker, Claus and Hart, William and Hofmann, Tommy and Johansson, Fredrik},
  title     = {{Nemo/Hecke}: Computer Algebra and Number Theory Packages for the {Julia} Programming Language},
  booktitle = {Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation},
  year      = {2017},
  series    = {ISSAC '17},
  pages     = {157--164},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/3087604.3087611},
  isbn      = {978-1-4503-5064-8},
  url       = {http://nemocas.org/},
}

@Manual{flint,
  title     = {{FLINT}: {F}ast {L}ibrary for {N}umber {T}heory},
  author    = {Hart, William and Johansson, Fredrik and Pancratz, Sebastian},
  year      = {2013},
  note      = {Version 2.4.0},
  shorthand = {Flint},
  url       = {http://flintlib.org},
}

@InProceedings{fouquet+morain02,
  author    = {Fouquet, Mireille and Morain, Fran\c{c}ois},
  title     = {Isogeny Volcanoes and the {SEA} Algorithm},
  booktitle = {Algorithmic Number Theory Symposium},
  year      = {2002},
  editor    = {Fieker, Claus and Kohel, David R.},
  volume    = {2369},
  series    = {Lecture Notes in Computer Science},
  pages     = {47--62},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin / Heidelberg},
  abstract  = {Recently, Kohel gave algorithms to compute the
                   conductor of the endomorphism ring of an ordinary
                   elliptic curve, given the cardinality of the curve.
                   Using his work, we give a complete description of the
                   structure of curves related via rational ℓ-degree
                   isogenies, a structure we call a volcano. We explain
                   how we can travel through this structure using
                   modular polynomials. The computation of the structure
                   is possible without knowing the cardinality of the
                   curve, and that as a result, we deduce information on
                   the cardinality.},
  chapter   = {23},
  doi       = {10.1007/3-540-45455-1_23},
  isbn      = {978-3-540-43863-2},
}

@Book{galbraith2012mathematics,
  title     = {Mathematics of public key cryptography},
  publisher = {Cambridge University Press},
  year      = {2012},
  author    = {Galbraith, Steven D.},
  note      = {\url{https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html}},
}

@InProceedings{gallant+lambert+vanstone01,
  author    = {Gallant, Robert P. and Lambert, Robert J. and Vanstone, Scott A.},
  title     = {Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms},
  booktitle = {CRYPTO '01: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology},
  year      = {2001},
  pages     = {190--200},
  address   = {London, UK},
  publisher = {Springer-Verlag},
  abstract  = {The fundamental operation in elliptic curve
                   cryptographic schemes is that of point multiplication
                   of an elliptic curve point by an integer. This paper
                   describes a new method for accelerating this
                   operation on classes of elliptic curves that have
                   efficiently-computable endomorphisms. One advantage
                   of the new method is that it is applicable to a
                   larger class of curves than previous such methods.},
  isbn      = {3-540-42456-3},
  url       = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.2004},
}

@Manual{GAP4,
  title        = {{GAP -- Groups, Algorithms, and Programming, Version 4.9.2}},
  organization = {The GAP~Group},
  year         = {2018},
  key          = {GAP},
  shorthand    = {GAP},
  url          = {https://www.gap-system.org},
}

@PhdThesis{gaudry2000algorithmique,
  author      = {Gaudry, Pierrick},
  title       = {Algorithmique des courbes hyperelliptiques et applications {\`a} la cryptologie},
  school      = {Ecole Polytechnique},
  year        = {2000},
  institution = {École Polytechnique},
  url         = {https://hal-polytechnique.archives-ouvertes.fr/tel-00514848/},
}

@Book{gauss1986disquisitiones,
  title     = {Disquisitiones Arithmeticae},
  publisher = {Springer-Verlag},
  year      = {1986},
  author    = {Gauss, Carl Friedrich},
  editor    = {Waterhouse, William C.},
  isbn      = {9783540962540},
  url       = {https://books.google.fr/books?id=Y-49PgAACAAJ},
}

@Article{giusti+lecerf+salvy01,
  author    = {Giusti, Marc and Lecerf, Gr\'{e}goire and Salvy, Bruno},
  title     = {A {G}r\"{o}bner free alternative for polynomial system solving},
  journal   = {Journal of Complexity},
  year      = {2001},
  volume    = {17},
  number    = {1},
  pages     = {154--211},
  month     = mar,
  issn      = {0885-064X},
  abstract  = {Given a system of polynomial equations and
                   inequations with coefficients in the field of
                   rational numbers, we show how to compute a geometric
                   resolution of the set of common roots of the system
                   over the field of complex numbers. A geometric
                   resolution consists of a primitive element of the
                   algebraic extension defined by the set of roots, its
                   minimal polynomial, and the parametrizations of the
                   coordinates. Such a representation of the solutions
                   has a long history which goes back to Leopold
                   Kronecker and has been revisited many times in
                   computer algebra. We introduce a new generation of
                   probabilistic algorithms where all the computations
                   use only univariate or bivariate polynomials. We give
                   a new codification of the set of solutions of a
                   positive dimensional algebraic variety relying on a
                   new global version of Newton's iterator. Roughly
                   speaking the complexity of our algorithm is
                   polynomial in some kind of degree of the system, in
                   its height, and linear in the complexity of
                   evaluation of the system. We present our
                   implementation in the Magma system which is called
                   Kronecker in homage to his method for solving systems
                   of polynomial equations. We show that the theoretical
                   complexity of our algorithm is well reflected in
                   practice and we exhibit some cases for which our
                   program is more efficient than the other available
                   software.},
  address   = {Orlando, FL, USA},
  doi       = {10.1006/jcom.2000.0571},
  publisher = {Academic Press, Inc.},
}

@Manual{givaro,
  title        = {Givaro -- {C++} library for arithmetic and algebraic computations},
  organization = {{The LinBox Team}},
  key          = {Givaro},
  shorthand    = {Giv},
  url          = {https://github.com/linbox-team/givaro},
}

@Misc{GMP-ECM,
  author = {Paul Zimmermann and others},
  title  = {{GMP-ECM} software},
  year   = {2018},
  url    = {http://ecm.gforge.inria.fr/},
}

@Article{goldreich+micali+widgerson91,
  author    = {Goldreich, Oded and Micali, Silvio and Wigderson, Avi},
  title     = {Proofs that yield nothing but their validity or all languages in {NP} have zero-knowledge proof systems},
  journal   = {Journal of the Association for Computing Machinery},
  year      = {1991},
  volume    = {38},
  number    = {3},
  pages     = {690--728},
  month     = jul,
  issn      = {0004-5411},
  abstract  = {An abstract is not available.},
  address   = {New York, NY, USA},
  doi       = {10.1145/116825.116852},
  publisher = {ACM},
}

@InBook{Goldreich2011,
  pages     = {451--464},
  title     = {Basic Facts about Expander Graphs},
  publisher = {Springer Berlin Heidelberg},
  year      = {2011},
  author    = {Goldreich, Oded},
  editor    = {Goldreich, Oded},
  address   = {Berlin, Heidelberg},
  isbn      = {978-3-642-22670-0},
  abstract  = {In this survey we review basic facts regarding
                   expander graphs that are most relevant to the theory
                   of computation.},
  booktitle = {Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman},
  doi       = {10.1007/978-3-642-22670-0_30},
}

@Article{hanrot+quercia+zimmermann,
  author   = {Hanrot, Guillaume and Quercia, Michel and Zimmermann, Paul},
  title    = {The Middle Product Algorithm {I}},
  journal  = {Applicable Algebra in Engineering, Communication and Computing},
  year     = {2004},
  volume   = {14},
  number   = {6},
  pages    = {415--438},
  issn     = {0938-1279},
  abstract = {We present new algorithms for the inverse, division,
                   and square root of power series. The key trick is a
                   new algorithm – {MiddleProduct} or, for short, {MP}
                   – computing the n middle coefficients of a (2
                   n-1)× n full product in the same number of
                   multiplications as a full n× n product. This
                   improves previous work of Brent, Mulders, Karp and
                   Markstein, Burnikel and Ziegler. These results apply
                   both to series and polynomials.},
  doi      = {10.1007/s00200-003-0144-2},
}

@InProceedings{Hart2010,
  author    = {William B. Hart},
  title     = {Fast Library for Number Theory: An Introduction},
  booktitle = {Proceedings of the Third International Congress on Mathematical Software},
  year      = {2010},
  series    = {ICMS'10},
  pages     = {88--91},
  address   = {Berlin, Heidelberg},
  publisher = {Springer-Verlag},
  location  = {Kobe, Japan},
  numpages  = {4},
  url       = {http://flintlib.org/},
}

@Article{harvey09,
  author   = {Harvey, David},
  title    = {Faster polynomial multiplication via multipoint {K}ronecker substitution},
  journal  = {Journal of Symbolic Computation},
  year     = {2009},
  volume   = {44},
  number   = {10},
  pages    = {1502--1510},
  month    = oct,
  issn     = {07477171},
  abstract = {We present several new algorithms for dense
                   polynomial multiplication in {inlMMLBox} based on the
                   Kronecker substitution method. Instead of reducing to
                   a single integer multiplication, we reduce to several
                   smaller multiplications. We describe an
                   implementation of multiplication in {inlMMLBox} for a
                   word-sized modulus n based on these methods, and
                   compare its performance to that of {NTL} and Magma.},
  doi      = {10.1016/j.jsc.2009.05.004},
}

@InProceedings{heath+loehr99,
  author    = {Heath, Lenwood S. and Loehr, Nicholas A.},
  title     = {New algorithms for generating {C}onway polynomials over finite fields},
  booktitle = {Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms},
  year      = {1999},
  series    = {SODA '99},
  pages     = {429--437},
  address   = {Philadelphia, PA, USA},
  publisher = {Society for Industrial and Applied Mathematics},
  abstract  = {An abstract is not available.},
  isbn      = {0-89871-434-6},
}

@InProceedings{heath1992zero,
  author    = {Heath-Brown, David R.},
  title     = {Zero-free regions for {Dirichlet} {L-functions}, and the least prime in an arithmetic progression},
  booktitle = {Proceedings of the London Mathematical Society},
  year      = {1992},
  volume    = {64},
  number    = {2},
  pages     = {265--338},
}

@PhdThesis{hugounenq:tel-01635463,
  author = {Hugounenq, Cyril},
  title  = {Volcanoes and isogeny computing},
  school = {{Universit{\'e} Paris-Saclay}},
  year   = {2017},
  month  = sep,
  number = {2017SACLV050},
  url    = {https://tel.archives-ouvertes.fr/tel-01635463},
}

@Article{ionica+joux13,
  author  = {Ionica, Sorina and Joux, Antoine},
  title   = {Pairing the volcano},
  journal = {Mathematics of Computation},
  year    = {2013},
  volume  = {82},
  number  = {281},
  pages   = {581--603},
}

@Article{ionica2014isogeny,
  author  = {Ionica, Sorina and Thom{\'e}, Emmanuel},
  title   = {Isogeny graphs with maximal real multiplication},
  journal = {arXiv preprint arXiv:1407.6672},
  year    = {2014},
}

@Inprocedings{joux,
  author    = {Joux, Antoine},
  title     = {The {W}eil and {T}ate pairings as building blocks for public key cryptosystems},
  year      = {2002},
  address   = {Berlin},
  booktitle = {Algorithmic number theory},
  doi       = {10.1007/3-540-45455-1_3},
  pages     = {20--32},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2369},
}

@InProceedings{kaltofen+shoup97,
  author    = {Kaltofen, Erich and Shoup, Victor},
  title     = {Fast polynomial factorization over high algebraic extensions of finite fields},
  booktitle = {ISSAC '97: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation},
  year      = {1997},
  pages     = {184--188},
  address   = {New York, NY, USA},
  publisher = {ACM},
  abstract  = {Note: {OCR} errors may be found in this Reference
                   List extracted from the full text article. {ACM} has
                   opted to expose the complete List rather than only
                   correct and linked references.},
  doi       = {10.1145/258726.258777},
  isbn      = {0-89791-875-4},
}

@Article{kaltofen+shoup98,
  author    = {Kaltofen, Erich and Shoup, Victor},
  title     = {Subquadratic-time factoring of polynomials over finite fields},
  journal   = {Mathematics of Computation},
  year      = {1998},
  volume    = {67},
  number    = {223},
  pages     = {1179--1197},
  issn      = {0025-5718},
  address   = {Boston, MA, USA},
  doi       = {10.1090/S0025-5718-98-00944-2},
  publisher = {American Mathematical Society},
}

@Article{kaltofen87,
  author    = {Kaltofen, Erich},
  title     = {Computer algebra algorithms},
  journal   = {Annual Review in Computer Science},
  year      = {1987},
  volume    = {2},
  pages     = {91--118},
  address   = {Palo Alto, California},
  publisher = {Annual Reviews Inc.},
  url       = {http://www.math.ncsu.edu/~kaltofen/bibliography/87/Ka87_annrev.pdf},
}

@Article{kedlaya01,
  author   = {Kedlaya, Kiran S.},
  title    = {Counting points on hyperelliptic curves using {M}onsky-{W}ashnitzer cohomology},
  journal  = {Journal of the Ramanujan Mathematical Society},
  year     = {2001},
  volume   = {16},
  number   = {4},
  pages    = {323--338},
  abstract = {In this paper an algorithm for counting points on
                   hyperelliptic curvesover finite fields of odd
                   characteristic is developed.<P> The approach is to
                   compute in the Monsky-Washnitzer cohomology,described
                   in sections 2 and 3, of an affine curve endowed with
                   anaction of Frobenius which can be \$p\$-adically
                   approximated efficientlyusing certain power series.
                   The running time of the algorithm is onthe order of
                   \$g^{4+\epsilon}n^{3+\epsilon}\$, where \$n\$ is the
                   degreeof the finite field and \$g\$ is the genus of
                   the curve (assuming thatthe curve has a rational
                   Weierstrass point).},
}

@InCollection{kedlaya04,
  author    = {Kedlaya, Kiran S.},
  title     = {Computing zeta functions via \(p\)-adic cohomology},
  booktitle = {Algorithmic number theory},
  publisher = {Springer},
  year      = {2004},
  volume    = {3076},
  series    = {Lecture Notes in Comput. Sci.},
  pages     = {1--17},
  address   = {Berlin},
}

@Article{KeUm11,
  author    = {Kedlaya, Kiran S and Umans, Christopher},
  title     = {Fast polynomial factorization and modular composition},
  journal   = {SIAM Journal on Computing},
  year      = {2011},
  volume    = {40},
  number    = {6},
  pages     = {1767--1802},
  publisher = {SIAM},
}

@Article{kitaev1995hsp,
  author  = {Kitaev, Alexey Yuri},
  title   = {Quantum measurements and the Abelian stabilizer problem},
  journal = {arXiv preprint quant-ph/9511026},
  year    = {1995},
  url     = {https://arxiv.org/abs/quant-ph/9511026},
}

@InProceedings{kocher+jaffe+jun99,
  author    = {Kocher, Paul and Jaffe, Joshua and Jun, Benjamin},
  title     = {{Differential Power Analysis}},
  booktitle = {Advances in Cryptology --- CRYPTO' 99},
  year      = {1999},
  volume    = {1666},
  series    = {Lecture Notes in Computer Science},
  pages     = {388--397},
  address   = {Berlin, Heidelberg},
  month     = dec,
  publisher = {Springer Berlin Heidelberg},
  abstract  = {{Cryptosystem designers frequently assume that
                   secrets will be manipulated in closed, reliable
                   computing environments. Unfortunately, actual
                   computers and microchips leak information about the
                   operations they process. This paper examines specific
                   methods for analyzing power consumption measurements
                   to find secret keys from tamper resistant devices. We
                   also discuss approaches for building cryptosystems
                   that can operate securely in existing hardware that
                   leaks information.}},
  chapter   = {25},
  doi       = {10.1007/3-540-48405-1_25},
  isbn      = {978-3-540-66347-8},
  issn      = {0302-9743},
}

@Article{Kummer1846,
  author   = {Kummer, Ernst Eduard},
  title    = {{\"Uber die Divisoren gewisser Formen der Zahlen, welche aus der Theorie der Kreistheilung entstehen}},
  journal  = {Journal f\"ur die reine und angewandte Mathematik},
  year     = {1846},
  volume   = {30},
  pages    = {107--116},
  language = {German},
  url      = {http://eudml.org/doc/147278},
}

@Article{Kummer1847a,
  author   = {Kummer, Ernst Eduard},
  title    = {{\"Uber die Zerlegung der aus Wurzeln der Einheit gebildeten complexen Zahlen in ihre Primfactoren}},
  journal  = {Journal f\"ur die reine und angewandte Mathematik},
  year     = {1847},
  volume   = {35},
  pages    = {327--367},
  language = {German},
  url      = {http://eudml.org/doc/147394},
}

@Article{Kummer1847b,
  author   = {Kummer, Ernst Eduard},
  title    = {Sur les nombres complexes qui sont form\'es avec les nombres entiers r\'eels et les racines de l'unit\'e},
  journal  = {Journal de Math\'ematiques Pures et Appliqu\'ees},
  year     = {1847},
  pages    = {185--212},
  language = {French},
  url      = {http://eudml.org/doc/235075},
}

@Article{Kummer1847c,
  author   = {Kummer, Ernst Eduard},
  title    = {{Zur Theorie der complexen Zahlen}},
  journal  = {Journal f\"ur die reine und angewandte Mathematik},
  year     = {1847},
  volume   = {35},
  pages    = {319--326},
  language = {German},
  url      = {http://eudml.org/doc/147393},
}

@Article{Kummer1851,
  author   = {Kummer, Ernst Eduard},
  title    = {M\'emoire sur la th\'eorie des nombres complexes compos\'es de racines de l'unit\'e et de nombres entiers},
  journal  = {Journal de Math\'ematiques Pures et Appliqu\'ees},
  year     = {1851},
  pages    = {377--498},
  language = {French},
  url      = {http://eudml.org/doc/235621},
}

@Article{Kummer1855,
  author   = {Kummer, Ernst Eduard},
  title    = {{\"Uber eine besondere Art, aus complexen Einheiten gebildeter Ausdr\"ucke}},
  journal  = {Journal f\"ur die reine und angewandte Mathematik},
  year     = {1855},
  volume   = {50},
  pages    = {212--232},
  language = {German},
  url      = {http://eudml.org/doc/147605},
}

@Article{Kummer1857,
  author   = {Kummer, Ernst Eduard},
  title    = {{\"Uber die den Gau\ss{}schen Perioden der Kreistheilung entsprechenden Congruenzwurzeln}},
  journal  = {Journal f\"ur die reine und angewandte Mathematik},
  year     = {1857},
  volume   = {53},
  pages    = {142--148},
  language = {German},
  url      = {http://eudml.org/doc/147659},
}

@Book{Kunz86,
  title     = {K\"ahler differentials},
  publisher = {Friedrich Vieweg \& Sohn},
  year      = {1986},
  author    = {Kunz, Ernst},
}

@InProceedings{lairez-vaccon,
  author    = {Lairez, Pierre and Vaccon, Tristan},
  title     = {On $p$-adic Differential Equations with Separation of Variables},
  booktitle = {Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation},
  year      = {2016},
  series    = {ISSAC '16},
  pages     = {319--323},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/2930889.2930912},
  isbn      = {978-1-4503-4380-0},
}

@Book{lang,
  title        = {Algebra},
  publisher    = {Springer},
  year         = {2002},
  author       = {Lang, Serge},
  edition      = {3rd edition},
  month        = jan,
  isbn         = {038795385X},
  abstract     = {{"Lang's Algebra changed the way graduate algebra is
                   taught, retaining classical topics but introducing
                   language and ways of thinking from category theory
                   and homological algebra. It has affected all
                   subsequent graduate-level algebra books."
                   \&nbsp;NOTICES OF THE AMS "The author has an
                   impressive knack for presenting the important and
                   interesting ideas of algebra in just the right way,
                   and he never gets bogged down in the dry formalism
                   which pervades some parts of
                   algebra."\&nbsp;MATHEMATICAL REVIEWS This book is
                   intended as a basic text for a one-year course in
                   algebra at the graduate level, or as a useful
                   reference for mathematicians and professionals who
                   use higher-level algebra. It successfully addresses
                   the basic concepts of algebra. \&nbsp;For the revised
                   third edition, the author has added exercises and
                   made numerous corrections to the text.}},
  howpublished = {Hardcover},
}

@Article{lauder04,
  author   = {Lauder, Alan G. B.},
  title    = {Computing zeta functions of {A}rtin-{S}chreier curves over finite fields {II}},
  journal  = {Journal of Complexity},
  year     = {2004},
  volume   = {20},
  number   = {2-3},
  pages    = {331--349},
  month    = jun,
  issn     = {0885064X},
  abstract = {We describe a method which may be used to compute the
                   zeta function of an arbitrary {Artin-Schreier} cover
                   of the projective line over a finite field.
                   Specifically, for covers defined by equations of the
                   form Z p − Z = f ( X ) we present, and give the
                   complexity analysis of, an algorithm for the case in
                   which f ( X ) is a rational function whose poles all
                   have order 1. However, we only prove the correctness
                   of this algorithm when the field characteristic is at
                   least 5. The algorithm is based upon a cohomological
                   formula for the L -function of an additive character
                   sum. One consequence is a practical method of finding
                   the order of the group of rational points on the
                   Jacobian of a hyperelliptic curve in characteristic
                   2.},
  doi      = {10.1016/j.jco.2003.08.009},
}

@Article{LEBRETON2015230,
  author   = {Romain Lebreton},
  title    = {Relaxed {H}ensel lifting of triangular sets},
  journal  = {Journal of Symbolic Computation},
  year     = {2015},
  volume   = {68},
  pages    = {230--258},
  issn     = {0747-7171},
  note     = {Effective Methods in Algebraic Geometry},
  abstract = {In this paper, we present a new lifting algorithm for
                   triangular sets over general p-adic rings. Our
                   contribution is to give, for any p-adic triangular
                   set, a shifted algorithm of which the triangular set
                   is a fixed point. Then we can apply the relaxed
                   recursive p-adic framework and deduce a relaxed
                   lifting algorithm for this triangular set. We compare
                   our algorithm to the existing technique and report on
                   implementations inside the C++ library Geomsolvex of
                   Mathemagix (van der Hoeven et al., 2002). Our new
                   relaxed algorithm is competitive and compare
                   favorably on some examples.},
  doi      = {10.1016/j.jsc.2014.09.012},
}

@InProceedings{LeGall14,
  author    = {Le Gall, Fran\c{c}ois},
  title     = {Powers of Tensors and Fast Matrix Multiplication},
  booktitle = {ISSAC'14},
  year      = {2014},
  pages     = {296--303},
  publisher = {ACM},
}

@InProceedings{LeMeSc13,
  author    = {Lebreton, Romain and Mehrabi, Esmaeil and Schost, \'Eric},
  title     = {On the Complexity of Solving Bivariate Systems: The Case of Non-singular Solutions},
  booktitle = {ISSAC'13},
  year      = {2013},
  pages     = {251--258},
  publisher = {ACM},
}

@Electronic{lenstra+desmit08-stdmodels,
  author = {Lenstra, Hendrik W. and de Smit, Bart},
  year   = {2008},
  title  = {Standard models for finite fields: the definition},
  url    = {http://www.math.leidenuniv.nl/~desmit/papers/standard_models.pdf},
  pages  = {1--4},
}

@Article{LENSTRA1977389,
  author  = {Lenstra, Hendrik W.},
  title   = {On the algebraic closure of two},
  journal = {Indagationes Mathematicae (Proceedings)},
  year    = {1977},
  volume  = {80},
  number  = {5},
  pages   = {389--396},
  issn    = {1385-7258},
  doi     = {10.1016/1385-7258(77)90053-1},
}

@Article{lenstra87,
  author  = {Lenstra, Hendrik W.},
  title   = {Factoring integers with elliptic curves},
  journal = {Annals of Mathematics},
  year    = {1987},
  volume  = {126},
  pages   = {649--673},
}

@Article{LenstraJr91,
  author  = {Lenstra, Hendrik W.},
  title   = {Finding isomorphisms between finite fields},
  journal = {Mathematics of Computation},
  year    = {1991},
  volume  = {56},
  number  = {193},
  pages   = {329--347},
}

@Article{lercier+sirvent08,
  author  = {Lercier, Reynald and Sirvent, Thomas},
  title   = {On {E}lkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field},
  journal = {Journal de th\'{e}orie des nombres de Bordeaux},
  year    = {2008},
  volume  = {20},
  number  = {3},
  pages   = {783--797},
  url     = {http://perso.univ-rennes1.fr/reynald.lercier/file/LS08.pdf},
}

@InProceedings{lercier96,
  author    = {Lercier, Reynald},
  title     = {Computing Isogenies in {GF(2,n)}},
  booktitle = {ANTS-II: Proceedings of the Second International Symposium on Algorithmic Number Theory},
  year      = {1996},
  pages     = {197--212},
  address   = {London, UK},
  publisher = {Springer-Verlag},
  isbn      = {3-540-61581-4},
}

@InProceedings{li+moreno+schost07,
  author    = {Li, Xin and Moreno Maza, Marc and Schost, \'{E}ric},
  title     = {Fast Arithmetic for Triangular Sets: From Theory to Practice},
  booktitle = {Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation},
  year      = {2007},
  series    = {ISSAC '07},
  pages     = {269--276},
  address   = {New York, NY, USA},
  publisher = {ACM},
  abstract  = {We study arithmetic operations for triangular
                   families of polynomials, concentrating on
                   multiplication in dimension zero. By a suitable
                   extension of fast univariate Euclidean division, we
                   obtain theoretical and practical improvements over a
                   direct recursive approach; for a family of special
                   cases, we reach quasi-linear complexity. The main
                   outcome we have in mind is the acceleration of
                   higher-level algorithms, by interfacing our low-level
                   implementation with languages such as {AXIOM} or
                   Maple We show the potential for huge speed-ups, by
                   comparing two {AXIOM} implementations of van Hoeij
                   and Monagan's modular {GCD} algorithm.},
  doi       = {10.1145/1277548.1277585},
  isbn      = {978-1-59593-743-8},
}

@Article{littlewood1928class,
  author    = {Littlewood, John E},
  title     = {On the Class-Number of the Corpus $P(\sqrt{k})$},
  journal   = {Proceedings of the London Mathematical Society},
  year      = {1928},
  volume    = {2},
  number    = {1},
  pages     = {358--372},
  publisher = {Wiley Online Library},
}

@InCollection{lo,
  author    = {Lagarias, Jeffrey C. and Odlyzko, Andrew M.},
  title     = {Effective versions of the {C}hebotarev density theorem},
  booktitle = {Algebraic number fields: {$L$}-functions and {G}alois properties},
  publisher = {Academic Press},
  year      = {1977},
  pages     = {409--464},
  address   = {London},
}

@Article{longa+sica14,
  author  = {Longa, Patrick and Sica, Francesco},
  title   = {Four-Dimensional {G}allant--{L}ambert--{V}anstone Scalar Multiplication},
  journal = {Journal of Cryptology},
  year    = {2014},
  volume  = {27},
  number  = {2},
  pages   = {248--283},
  issn    = {1432-1378},
  doi     = {10.1007/s00145-012-9144-3},
}

@Book{Lub,
  title     = {Discrete groups, expanding graphs and invariant measures},
  publisher = {Birkh\"{a}user Verlag},
  year      = {1994},
  author    = {Lubotzky, Alexander},
  volume    = {125},
  series    = {Progress in Mathematics},
  address   = {Basel},
  isbn      = {978-3-0346-0332-4},
  doi       = {10.1007/978-3-0346-0332-4},
}

@Article{lubicz_robert_2012,
  author    = {Lubicz, David and Robert, Damien},
  title     = {Computing isogenies between abelian varieties},
  journal   = {Compositio Mathematica},
  year      = {2012},
  volume    = {148},
  number    = {5},
  pages     = {1483--1515},
  doi       = {10.1112/S0010437X12000243},
  publisher = {London Mathematical Society},
}

@Article{lubicz_robert_2015,
  author    = {Lubicz, David and Robert, Damien},
  title     = {Computing separable isogenies in quasi-optimal time},
  journal   = {LMS Journal of Computation and Mathematics},
  year      = {2015},
  volume    = {18},
  number    = {1},
  pages     = {198--216},
  doi       = {10.1112/S146115701400045X},
  publisher = {London Mathematical Society},
}

@Article{LubPS,
  author  = {Lubotzky, Alexander and Phillips, Ralph and Sarnak, Peter},
  title   = {Ramanujan graphs},
  journal = {Combinatorica},
  year    = {1988},
  volume  = {8},
  number  = {3},
  doi     = {10.1007/BF02126799},
}

@Electronic{Luebeck,
  author = {Lübeck, Frank},
  year   = {2008},
  title  = {Conway polynomials for finite fields},
  url    = {http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/},
}

@Article{MAGMA,
  author    = {Bosma, Wieb and Cannon, John and Playoust, Catherine},
  title     = {The {MAGMA} algebra system {I}: the user language},
  journal   = {Journal of Symbolic Computation},
  year      = {1997},
  volume    = {24},
  number    = {3-4},
  pages     = {235--265},
  issn      = {0747-7171},
  address   = {Duluth, MN, USA},
  doi       = {10.1006/jsco.1996.0125},
  publisher = {Academic Press, Inc.},
}

@InProceedings{mauer+menezes+teske01,
  author    = {Maurer, Markus and Menezes, Alfred and Teske, Edlyn},
  title     = {Analysis of the {GHS} {W}eil Descent Attack on the {ECDLP} over Characteristic Two Finite Fields of Composite Degree},
  booktitle = {INDOCRYPT '01: Proceedings of the Second International Conference on Cryptology in India},
  year      = {2001},
  pages     = {195--213},
  address   = {Berlin},
  publisher = {Springer-Verlag},
  isbn      = {3-540-43010-5},
}

@MastersThesis{memoire,
  author = {Kieffer, Jean},
  title  = {\'Etude et accélération du protocole d'échange de clés de Couveignes--Rostovtsev--Stolbunov},
  school = {Inria Saclay \& Université Paris VI},
  year   = {2017},
}

@Article{Mihailescu2010825,
  author  = {Preda Mihailescu and Victor Vuletescu},
  title   = {Elliptic Gauss sums and applications to point counting},
  journal = {Journal of Symbolic Computation},
  year    = {2010},
  volume  = {45},
  number  = {8},
  pages   = {825--836},
  issn    = {0747-7171},
  doi     = {10.1016/j.jsc.2010.01.004},
}

@Article{milio_2015,
  author    = {Milio, Enea},
  title     = {A quasi-linear time algorithm for computing modular polynomials in dimension 2},
  journal   = {LMS Journal of Computation and Mathematics},
  year      = {2015},
  volume    = {18},
  number    = {1},
  pages     = {603--632},
  doi       = {10.1112/S1461157015000170},
  publisher = {London Mathematical Society},
}

@Unpublished{milio:hal-01520262,
  author = {Milio, Enea and Robert, Damien},
  title  = {Modular polynomials on {H}ilbert surfaces},
  note   = {Working paper or preprint},
  month  = sep,
  year   = {2017},
  url    = {https://hal.archives-ouvertes.fr/hal-01520262},
}

@Article{MIRET200867,
  author   = {Miret, Josep M. and Moreno, Ramiro and Sadornil, Daniel and Tena, Juan and Valls, Magda},
  title    = {Computing the height of volcanoes of ℓ-isogenies of elliptic curves over finite fields},
  journal  = {Applied Mathematics and Computation},
  year     = {2008},
  volume   = {196},
  number   = {1},
  pages    = {67--76},
  issn     = {0096-3003},
  abstract = {The structure of the volcano of ℓ-isogenies,
                   ℓ-prime, of elliptic curves over finite fields has
                   been extensively studied over recent years. Previous
                   works present some results and algorithms concerning
                   the height of such volcanoes in the case of isogenies
                   whose kernels are generated by a rational point. The
                   main goal of this paper is to extend such works to
                   the case of ℓ-isogenies whose kernels are defined
                   by a rational subgroup. In particular, the height of
                   such volcanoes is completely characterized and can be
                   computationally obtained.},
  doi      = {10.1016/j.amc.2007.05.037},
}

@Article{MiretMRV05,
  author  = {Josep M. Miret and Ramiro Moreno and Ana Rio and Magda Valls},
  title   = {Determining the 2-{S}ylow subgroup of an elliptic curve over a finite field},
  journal = {Mathematics of Computation},
  year    = {2005},
  volume  = {74},
  number  = {249},
  pages   = {411--427},
  doi     = {10.1090/S0025-5718-04-01640-0},
}

@Article{MiretMSTV06,
  author  = {Josep M. Miret and Ramiro Moreno and Daniel Sadornil and Juan Tena and Magda Valls},
  title   = {An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields},
  journal = {Applied Mathematics and Computation},
  year    = {2006},
  volume  = {176},
  number  = {2},
  pages   = {739--750},
  doi     = {10.1016/j.amc.2005.10.020},
}

@Article{moenck76,
  author    = {Moenck, Robert T.},
  title     = {Another polynomial homomorphism},
  journal   = {Acta Informatica},
  year      = {1976},
  volume    = {6},
  number    = {2},
  pages     = {153--169},
  month     = jun,
  issn      = {0001-5903},
  abstract  = {The current proposals for applying the so called fast
                   {O(N} {logaN}) algorithms to multivariate polynomials
                   is that the univariate methods be applied
                   recursively, much in the way more conventional
                   algorithms are used. Since the size of the problems
                   is rather large for which a fastrd algorithm is more
                   efficient than a classical one, the recursive
                   approach compounds this size completely out of any
                   practical range .},
  doi       = {10.1007/BF00268498},
  publisher = {Springer Berlin / Heidelberg},
}

@Article{monico2007,
  author  = {Maze, G\'erard and Monico, Chris and Rosenthal, Joachim},
  title   = {Public key cryptography based on semigroup actions},
  journal = {Advances in Mathematics of Communications},
  year    = {2007},
  volume  = {1},
  number  = {4},
  pages   = {489--507},
  issn    = {1930-5346},
  doi     = {10.3934/amc.2007.1.489},
}

@Article{montgomery,
  author    = {Montgomery, Peter L.},
  title     = {Speeding the Pollard and Elliptic Curve Methods of Factorization},
  journal   = {Mathematics of Computation},
  year      = {1987},
  volume    = {48},
  number    = {177},
  pages     = {243--264},
  issn      = {00255718},
  abstract  = {Since 1974, several algorithms have been developed
                   that attempt to factor a large number \$N\$ by doing
                   extensive computations modulo \$N\$ and occasionally
                   taking {GCDs} with \$N\$. These began with Pollard's
                   \$p - 1\$ and Monte Carlo methods. More recently,
                   Williams published a \$p + 1\$ method, and Lenstra
                   discovered an elliptic curve method ({ECM}). We
                   present ways to speed all of these. One improvement
                   uses two tables during the second phases of \$p \pm
                   1\$ and {ECM}, looking for a match. Polynomial
                   preconditioning lets us search a fixed table of size
                   \$n\$ with \$n/2 + o(n)\$ multiplications. A
                   parametrization of elliptic curves lets Step 1 of
                   {ECM} compute the \$x\$-coordinate of \${nP}\$ from
                   that of \$P\$ in about \$9.3 \log\_2 n\$
                   multiplications for arbitrary \$P\$.},
  doi       = {10.2307/2007888},
  publisher = {American Mathematical Society},
}

@Article{MOODY20125249,
  author   = {Moody, Dustin},
  title    = {Computing isogeny volcanoes of composite degree},
  journal  = {Applied Mathematics and Computation},
  year     = {2012},
  volume   = {218},
  number   = {9},
  pages    = {5249--5258},
  issn     = {0096-3003},
  abstract = {Isogeny volcanoes are an interesting structure that
                   have had several recent applications. An isogeny
                   volcano is a connected component of a larger graph
                   called a cordillera. In this paper, we further
                   explore properties of how to compute volcanoes given
                   that we have already computed one of a different
                   degree. This allows us to compute volcanoes of
                   composite degree more efficiently than a direct
                   construction using modular polynomials.},
  doi      = {10.1016/j.amc.2011.11.008},
}

@Article{morain95,
  author  = {Morain, Fran\c{c}ois},
  title   = {Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques},
  journal = {Journal de Th\'eorie des Nombres Bordeaux},
  year    = {1995},
  volume  = {7},
  number  = {1},
  pages   = {255--282},
  issn    = {1246-7405},
  note    = {Les Dix-huiti\`emes Journ\'ees Arithm\'etiques (Bordeaux, 1993)},
  url     = {http://jtnb.cedram.org/item?id=JTNB_1995__7_1_255_0},
}

@Book{mullen2013handbook,
  title     = {Handbook of finite fields},
  publisher = {CRC Press},
  year      = {2013},
  author    = {Mullen, Gary L. and Panario, Daniel},
}

@InProceedings{narayanan2016fast,
  author    = {Narayanan, Anand Kumar},
  title     = {Fast Computation of Isomorphisms Between Finite Fields Using Elliptic Curves},
  booktitle = {{International Workshop on the Arithmetic of Finite Fields, WAIFI 2018}},
  year      = {2018},
  series    = {Lecture Notes in Computer Science},
  publisher = {Springer Berlin / Heidelberg},
}

@Electronic{Nickel1988,
  author      = {Nickel, Werner},
  year        = {1988},
  title       = {{E}ndliche {K}örper in dem gruppentheoretischen {P}rogrammsystem {GAP}},
  url         = {https://www2.mathematik.tu-darmstadt.de/~nickel/},
  institution = {RWTH Aachen},
  type        = {mathesis},
}

@Electronic{NIST2016,
  author       = {{National Institute of Standards and Technology}},
  year         = {2016},
  title        = {Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms},
  organization = {National Institute of Standards and Technology},
  url          = {https://www.federalregister.gov/documents/2016/12/20/2016-30615/announcing-request-for-nominations-for-public-key-post-quantum-cryptographic-algorithms},
  editor       = {The Federal Register},
}

@Article{Noether1932,
  author  = {Noether, Emmy},
  title   = {{Normalbasis bei K\"orpern ohne h\"ohere Verzweigung}},
  journal = {Journal f\"ur die reine und angewandte Mathematik},
  year    = {1932},
  volume  = {167},
  pages   = {147--152},
  url     = {http://eudml.org/doc/149800},
}

@Misc{oeis,
  author       = {{OEIS Foundation Inc.}},
  title        = {The On-Line Encyclopedia of Integer Sequences},
  howpublished = {\url{http://oeis.org/A130715}},
  year         = {2012},
}

@InProceedings{OKS00,
  author    = {Katsuyuki Okeya and Hiroyuki Kurumatani and Kouichi Sakurai},
  title     = {Elliptic Curves with the {Montgomery}-Form and Their Cryptographic Applications},
  booktitle = {Public Key Cryptography --- {PKC} 2000},
  year      = {2000},
  editor    = {Hideki Imai and Yuliang Zheng},
  volume    = {1751},
  series    = {Lecture Notes in Computer Science},
  pages     = {238--257},
  publisher = {Springer},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/pkc/OkeyaS00},
  doi       = {10.1007/978-3-540-46588-1\_17},
  isbn      = {3-540-66967-1},
}

@Manual{Pari,
  title        = {{PARI/GP, version {\texttt{2.8.0}}}},
  organization = {{The PARI Group}},
  address      = {Bordeaux},
  year         = {2016},
  key          = {PARI},
  shorthand    = {PARI},
  url          = {https://pari.math.u-bordeaux.fr/},
}

@InProceedings{pascal+schost06,
  author    = {Pascal, Cyril and Schost, \'{E}ric},
  title     = {Change of order for bivariate triangular sets},
  booktitle = {ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation},
  year      = {2006},
  pages     = {277--284},
  address   = {New York, NY, USA},
  publisher = {ACM},
  abstract  = {Changing the order of variables in bivariate
                   triangular sets has applications in Trager's
                   factorization algorithm, or in rational function
                   integration. We discuss the complexity of this
                   question, using baby steps / giant steps techniques
                   and trace formulas, obtaining subquadratic
                   estimates.},
  doi       = {10.1145/1145768.1145814},
  isbn      = {1-59593-276-3},
}

@Article{paterson_stockmeyer,
  author  = {Michael S. Paterson and Larry J. Stockmeyer},
  title   = {On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials},
  journal = {SIAM Journal on Computing},
  year    = {1973},
  volume  = {2},
  number  = {1},
  pages   = {60--66},
  doi     = {10.1137/0202007},
}

@Article{pila90,
  author    = {Pila, Jonathan},
  title     = {Frobenius Maps of {A}belian Varieties and Finding Roots of Unity in Finite Fields},
  journal   = {Mathematics of Computation},
  year      = {1990},
  volume    = {55},
  number    = {192},
  pages     = {745--763},
  issn      = {00255718},
  abstract  = {We give a generalization to Abelian varieties over
                   finite fields of the algorithm of Schoof for elliptic
                   curves. Schoof showed that for an elliptic curve
                   \$E\$ over \$\mathbf{F}\_q\$, given by a Weierstrass
                   equation, one can compute the number of
                   \$\mathbf{F}\_q\$-rational points of \$E\$ in time
                   \$O((\log q)^9)\$. Our result is the following. Let
                   \$A\$ be an Abelian variety over \$\mathbf{F}\_q\$.
                   Then one can compute the characteristic polynomial of
                   the Frobenius endomorphism of \$A\$ in time \$O((\log
                   q)^\Delta)\$, where \$\Delta\$ and the implied
                   constant depend only on the dimension of the
                   embedding space of \$A\$, the number of equations
                   defining \$A\$ and the addition law, and their
                   degrees. The method, generalizing that of Schoof, is
                   to use the machinery developed by Weil to prove the
                   Riemann hypothesis for Abelian varieties. By means of
                   this theory, the calculation is reduced to
                   ideal-theoretic computations in a ring of polynomials
                   in several variables over \$\mathbf{F}\_q\$. As
                   applications we show how to count the rational points
                   on the reductions modulo primes \$p\$ of a fixed
                   curve over \$\mathbf {Q}\$ in time polynomial in
                   \$\log p\$; we show also that, for a fixed prime
                   \$l\$, we can compute the \$l\$th roots of unity
                   \$\operatorname{mod} p\$, when they exist, in
                   polynomial time in \$\log p\$. This generalizes
                   Schoof's application of his algorithm to find square
                   roots of a fixed integer \$x \operatorname{mod} p\$.},
  doi       = {10.2307/2008445},
  publisher = {American Mathematical Society},
}

@InProceedings{Pinch,
  author    = {Richard G. E. Pinch},
  title     = {Recognising Elements Of Finite Fields},
  booktitle = {Cryptography and Coding II},
  year      = {1992},
  pages     = {193--197},
  publisher = {Oxford University Press},
}

@InProceedings{pointcheval95-pp,
  author    = {Pointcheval, David},
  title     = {A New Identification Scheme Based on the Perceptrons Problem},
  booktitle = {Advances in Cryptology --- EUROCRYPT '95},
  year      = {1995},
  volume    = {921},
  series    = {Lecture Notes in Computer Science},
  pages     = {319--328},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin / Heidelberg},
  abstract  = {Identification is a useful cryptographic tool. Since
                   zero-know- ledge theory appeared [ 3 ], several
                   interactive identification schemes have been proposed
                   (in particular Fiat-Shamir [ 2 ] and its variants [ 8
                   , 5 , 4 ], Schnorr [ 9 ]). These identifications are
                   based on number theoretical prob- lems. More
                   recently, new schemes appeared with the peculiarity
                   that they are more efficient from the computational
                   point of view and that their security is based on NP
                   -complete problems: PKP (Permuted Ker- nels Problem)
                   [ 10 ], SD (Syndrome Decoding) [ 12 ] and CLE
                   (Constrained Linear Equations) [ 13 ]. We present a
                   new NP -complete linear problem which comes from
                   learn- ing machines: the Perceptrons Problem. We have
                   some constraints, m vectors X i of {−1, +1} n , and
                   we want to find a vector V of {−1, +1} n such that
                   X i · V ≥ 0 for all i . Next, we provide some
                   zero-knowledge interactive identification protocols
                   based on this problem, with an evaluation of their
                   security. Eventually, those protocols are well suited
                   for smart card applications.},
  chapter   = {26},
  doi       = {10.1007/3-540-49264-X\_26},
  isbn      = {978-3-540-59409-3},
  url       = {http://dx.doi.org/10.1007/3-540-49264-X\_26},
}

@Article{PoSc13a,
  author    = {Adrian Poteaux and \'Eric Schost},
  title     = {Modular Composition Modulo Triangular Sets and Applications},
  journal   = {Computational Complexity},
  year      = {2013},
  volume    = {22},
  number    = {3},
  pages     = {463--516},
  publisher = {Springer Basel},
}

@Article{PoSc13b,
  author  = {Adrien Poteaux and \'Eric Schost},
  title   = {On the complexity of computing with zero-dimensional triangular sets},
  journal = {Journal of Symbolic Computation},
  year    = {2013},
  volume  = {50},
  pages   = {110--138},
}

@InProceedings{quis,
  author    = {Petit, Christophe and Lauter, Kristin and Quisquater, Jean-Jacques},
  title     = {Full Cryptanalysis of {LPS} and {M}orgenstern Hash Functions},
  booktitle = {Proceedings of the 6th international conference on Security and Cryptography for Networks},
  year      = {2008},
  series    = {SCN '08},
  address   = {Berlin, Heidelberg},
  publisher = {Springer-Verlag},
  doi       = {10.1007/978-3-540-85855-3_18},
}

@Unpublished{rains2008,
  author = {Eric M. Rains},
  title  = {Efficient Computation of Isomorphisms Between Finite Fields},
  note   = {Personal communication},
  year   = {1996},
}

@Misc{Roe2013,
  author       = {Roe, David and Flori, Jean-Pierre and Bruin, Peter},
  title        = {Implement pseudo-{C}onway polynomials},
  howpublished = {Trac ticket \#14958},
  month        = oct,
  year         = {2013},
  url          = {https://trac.sagemath.org/ticket/14958},
}

@Article{rouiller99,
  author   = {Rouillier, Fabrice},
  title    = {Solving Zero-Dimensional Systems Through the Rational Univariate Representation},
  journal  = {Applicable Algebra in Engineering, Communication and Computing},
  year     = {1999},
  volume   = {9},
  number   = {5},
  pages    = {433--461},
  month    = may,
  issn     = {0938-1279},
  abstract = {Abstract.\&nbsp;\&nbsp; This paper is devoted to the
                   resolution of zero-dimensional systems in {K[X} 1,
                   …X n ], where K is a field of characteristic zero
                   (or strictly positive under some conditions). We
                   follow the definition used in {MMM95} and basically
                   due to Kronecker for solving zero-dimensional
                   systems: A system is solved if each root is
                   represented in such way as to allow the performance
                   of any arithmetical operations over the arithmetical
                   expressions of its coordinates. We propose new
                   definitions for solving zero-dimensional systems in
                   this sense by introducing the Univariate
                   Representation of their roots. We show by this way
                   that the solutions of any zero-dimensional system of
                   polynomials can be expressed through a special kind
                   of univariate representation (Rational Univariate
                   Representation): where (f,g,g 1, …,g n ) are
                   polynomials of {K[X} 1, …, X n ]. A special feature
                   of our Rational Univariate Representation is that we
                   dont loose geometrical information contained in the
                   initial system. Moreover we propose different
                   efficient algorithms for the computation of the
                   Rational Univariate Representation, and we make a
                   comparison with standard known tools.},
  doi      = {10.1007/s002000050114},
}

@Manual{Sage,
  title        = {{SageMath, the Sage Mathematics Software System (Version 8.0)}},
  organization = {{The Sage Developers}},
  year         = {2018},
  key          = {SageMath},
  shorthand    = {Sage},
  url          = {https://www.sagemath.org},
}

@Book{Sarnak,
  title     = {Some applications of modular forms},
  publisher = {Cambridge University Press},
  year      = {1990},
  author    = {Sarnak, Peter},
  volume    = {99},
  series    = {Cambridge Tracts in Mathematics},
  address   = {Cambridge},
}

@Article{satoh00,
  author    = {Satoh, Takakazu},
  title     = {The canonical lift of an ordinary elliptic curve over a finite field and its point counting},
  journal   = {Journal of the Ramanujan Mathematical Society},
  year      = {2000},
  volume    = {15},
  number    = {4},
  pages     = {247--270},
  publisher = {The Ramanujan Mathematical Society},
}

@Article{schoof85,
  author    = {Schoof, Ren\'{e}},
  title     = {Elliptic Curves Over Finite Fields and the Computation of Square Roots mod \(p\)},
  journal   = {Mathematics of Computation},
  year      = {1985},
  volume    = {44},
  number    = {170},
  pages     = {483--494},
  issn      = {00255718},
  abstract  = {In this paper we present a deterministic algorithm to
                   compute the number of \$\mathbf{F}\_q\$-points of an
                   elliptic curve that is defined over a finite field
                   \$\mathbf{F}\_q\$ and which is given by a Weierstrass
                   equation. The algorithm takes \$O(\log^9 q)\$
                   elementary operations. As an application we give an
                   algorithm to compute square roots
                   \$\operatorname{mod} p\$. For fixed \$x \in
                   \mathbf{Z}\$, it takes \$O(\log^9 p)\$ elementary
                   operations to compute \$\sqrt x \operatorname{mod}
                   p\$.},
  doi       = {10.2307/2007968},
  publisher = {American Mathematical Society},
}

@Article{schoof95,
  author   = {Schoof, Ren\'{e}},
  title    = {Counting points on elliptic curves over finite fields},
  journal  = {Journal de Th\'{e}orie des Nombres de Bordeaux},
  year     = {1995},
  volume   = {7},
  number   = {1},
  pages    = {219--254},
  abstract = {Les Dix-huiti\`{e}mes Journ\'{e}es Arithm\'{e}tiques
                   (Bordeaux, 1993)},
  url      = {http://www.ams.org/mathscinet-getitem?mr=1413578},
}

@Book{Serre.Arith,
  title     = {{Cours d'arithmétique}},
  publisher = {Presses Universitaires de France},
  year      = {1970},
  author    = {Serre, Jean-Pierre},
  address   = {Paris},
}

@InProceedings{shamir89-pkp,
  author    = {Shamir, Adi},
  title     = {An efficient identification scheme based on permuted kernels (extended abstract)},
  booktitle = {Proceedings on Advances in cryptology},
  year      = {1989},
  series    = {CRYPTO '89},
  pages     = {606--609},
  address   = {New York, NY, USA},
  publisher = {Springer-Verlag New York, Inc.},
  abstract  = {In 1985 Goldwasser Micali and Rackoff proposed a new
                   type of interactive proof system which reveals no
                   knowledge whatsoever about the assertion except its
                   validity. The practical significance of these proofs
                   was demonstrated in 1986 by Fiat and Shamir, who
                   showed how to use efficient zero knowledge proofs of
                   quadratic residuosity to establish user identities
                   and to digitally sign messages. In this paper we
                   propose a new zero knowledge identification scheme,
                   which is even faster than the Fiat-Shamir scheme,
                   using a small number of communicated bits, simple
                   8-bit arithmetic operations, and compact public and
                   private keys. The security of the new scheme depends
                   on an NP-complete algebraic problem rather than on
                   factoring, and thus it widens the basis of public key
                   cryptography, which has become dangerously dependent
                   on the difficulty of a single problem.},
  isbn      = {0-387-97317-6},
}

@Article{Shoup_1990,
  author    = {Victor Shoup},
  title     = {New algorithms for finding irreducible polynomials over finite fields},
  journal   = {Mathematics of Computation},
  year      = {1990},
  volume    = {54},
  number    = {189},
  pages     = {435--435},
  month     = jan,
  doi       = {10.1090/s0025-5718-1990-0993933-0},
  publisher = {American Mathematical Society ({AMS})},
}

@Manual{shoup2003ntl,
  title     = {{NTL}: A library for doing number theory},
  author    = {Shoup, Victor},
  shorthand = {NTL},
  url       = {http://www.shoup.net/ntl},
}

@InProceedings{shoup93,
  author    = {Shoup, Victor},
  title     = {Fast construction of irreducible polynomials over finite fields},
  booktitle = {SODA '93: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms},
  year      = {1993},
  pages     = {484--492},
  address   = {Philadelphia, PA, USA},
  publisher = {Society for Industrial and Applied Mathematics},
  abstract  = {Note: {OCR} errors may be found in this Reference
                   List extracted from the full text article. {ACM} has
                   opted to expose the complete List rather than only
                   correct and linked references.},
  isbn      = {0-89871-313-7},
}

@Article{shoup94,
  author    = {Shoup, Victor},
  title     = {Fast construction of irreducible polynomials over finite fields},
  journal   = {Journal of Symbolic Computation},
  year      = {1994},
  volume    = {17},
  number    = {5},
  pages     = {371--391},
  issn      = {0747-7171},
  address   = {Duluth, MN, USA},
  doi       = {10.1006/jsco.1994.1025},
  publisher = {Academic Press, Inc.},
}

@Article{shoup95,
  author    = {Shoup, Victor},
  title     = {A New Polynomial Factorization Algorithm and its Implementation},
  journal   = {Journal of Symbolic Computation},
  year      = {1995},
  volume    = {20},
  number    = {4},
  pages     = {363--397},
  issn      = {0747-7171},
  abstract  = {We consider the problem of factoring univariate
                   polynomials over a finite field. We demonstrate that
                   the new baby step/giant step factoring method,
                   recently developed by Kaltofen and Shoup, can be made
                   into a very practical algorithm. We describe an
                   implementation of this algorithm, and present the
                   results of empirical tests comparing this new
                   algorithm with others. When factoring polynomials
                   modulo large primes, the algorithm allows much larger
                   polynomials to be factored using a reasonable amount
                   of time and space than was previously possible. For
                   example, this new software has been used to factor a
                   generic polynomial of degree 2048 modulo a 2048-bit
                   prime in under 12 days on a Sun SPARC-station 10,
                   using 68 MB of main memory.},
  address   = {Duluth, MN, USA},
  doi       = {10.1006/jsco.1995.1055},
  publisher = {Academic Press, Inc.},
}

@InProceedings{shoup99,
  author    = {Shoup, Victor},
  title     = {Efficient Computation of Minimal Polynomials in Algebraic Extensions of Finite Fields},
  booktitle = {Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation},
  year      = {1999},
  series    = {ISSAC '99},
  pages     = {53--58},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/309831.309859},
  isbn      = {1-58113-073-2},
}

@Article{Shparlinski2014,
  author   = {Shparlinski, Igor E. and Sutherland, Andrew V.},
  title    = {On the Distribution of {A}tkin and {E}lkies Primes},
  journal  = {Foundations of Computational Mathematics},
  year     = {2014},
  volume   = {14},
  number   = {2},
  pages    = {285--297},
  month    = apr,
  issn     = {1615-3383},
  abstract = {Given an elliptic curve {\$}{\$}E{\$}{\$} E over a
                   finite field {\$}{\$}{\backslash}mathbb
                   {\{}F{\}}{\_}q{\$}{\$} F q of {\$}{\$}q{\$}{\$} q
                   elements, we say that an odd prime
                   {\$}{\$}{\backslash}ell {\backslash}not
                   {\backslash}mid q{\$}{\$} ℓ ∤ q is an Elkies
                   prime for {\$}{\$}E{\$}{\$} E if {\$}{\$}t{\_}E^2 -
                   4q{\$}{\$} t E 2 - 4 q is a square modulo 
                   {\$}{\$}{\backslash}ell {\$}{\$} ℓ , where
                   {\$}{\$}t{\_}E = q+1 -
                   {\backslash}{\#}E({\backslash}mathbb
                   {\{}F{\}}{\_}q){\$}{\$} t E = q + 1 - {\#} E ( F q )
                   and {\$}{\$}{\backslash}{\#}E({\backslash}mathbb
                   {\{}F{\}}{\_}q){\$}{\$} {\#} E ( F q ) is the number
                   of {\$}{\$}{\backslash}mathbb {\{}F{\}}{\_}q{\$}{\$}
                   F q -rational points on {\$}{\$}E{\$}{\$} E ;
                   otherwise, {\$}{\$}{\backslash}ell {\$}{\$} ℓ is
                   called an Atkin prime. We show that there are
                   asymptotically the same number of Atkin and Elkies
                   primes {\$}{\$}{\backslash}ell < L{\$}{\$} ℓ < L on
                   average over all curves {\$}{\$}E{\$}{\$} E over
                   {\$}{\$}{\backslash}mathbb {\{}F{\}}{\_}q{\$}{\$} F q
                   , provided that {\$}{\$}L {\backslash}ge
                   ({\backslash}log q)^{\backslash}varepsilon {\$}{\$} L
                   ≥ ( log q ) $\epsilon$ for any fixed
                   {\$}{\$}{\backslash}varepsilon >0{\$}{\$} $\epsilon$
                   > 0 and a sufficiently large {\$}{\$}q{\$}{\$} q . We
                   use this result to design and analyze a fast
                   algorithm to generate random elliptic curves with
                   {\$}{\$}{\backslash}{\#}E({\backslash}mathbb
                   {\{}F{\}}{\_}p){\$}{\$} {\#} E ( F p ) prime, where
                   {\$}{\$}p{\$}{\$} p varies uniformly over primes in a
                   given interval {\$}{\$}[x,2x]{\$}{\$} [ x , 2 x ] .},
  doi      = {10.1007/s10208-013-9181-9},
}

@Book{SL2,
  title     = {Arbres, amalgames, $SL_2$},
  publisher = {Société Mathématique de France},
  year      = {1977},
  author    = {Serre, Jean-Pierre},
  volume    = {46},
  series    = {Astérisque},
  address   = {Paris},
}

@TechReport{solinas01,
  author      = {Solinas, Jerome A.},
  title       = {Low-Weight Binary Representations for Pairs of Integers},
  institution = {National Security Agency, USA},
  year        = {2001},
}

@InProceedings{stern94-CLE,
  author    = {Stern, Jacques},
  title     = {Designing Identification Schemes with Keys of Short Size},
  booktitle = {Advances in Cryptology --- CRYPTO '94},
  year      = {1994},
  volume    = {839},
  series    = {Lecture Notes in Computer Science},
  pages     = {164--173},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin / Heidelberg},
  abstract  = {In the last few years, there have been several
                   attempts to build identification protocols that do
                   not rely on arithmetical operations with large
                   numbers but only use simple operations (see [ 10 , 8
                   ]). One was presented at the CRYPTO 89 rump session
                   ([ 8 ]) and depends on the so-called Permuted Kernel
                   problem (PKP). Another appeared in the CRYPTO 93
                   proceedings and is based on the syndrome decoding
                   problem (SD) form the theory of error correcting
                   codes ([ 11 ]). In this paper, we introduce a new
                   scheme of the same family with the distinctive
                   character that both the secret key and the public
                   identification key can be taken to be of short
                   length. By short, we basically mean the usual size of
                   conventional symmetric cryptosystems. As is known,
                   the possibility of using short keys has been a
                   challenge in public key cryptography and has
                   practical applications. Our scheme relies on a
                   combinatorial problem which we call Constrained
                   Linear Equations (CLE in short) and which consists of
                   solving a set of linear equations modulo some small
                   prime q , the unknowns being subject to belong to a
                   specific subset of the integers mod q . Thus, we
                   enlarge the set of tools that can be used in
                   cryptography.},
  chapter   = {18},
  doi       = {10.1007/3-540-48658-5\_18},
  isbn      = {978-3-540-58333-2},
  url       = {http://dx.doi.org/10.1007/3-540-48658-5\_18},
}

@InProceedings{stern94-SD,
  author    = {Stern, Jacques},
  title     = {A new identification scheme based on syndrome decoding},
  booktitle = {Advances in Cryptology --- CRYPTO' 93},
  year      = {1994},
  volume    = {773},
  series    = {Lecture Notes in Computer Science},
  pages     = {13--21},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin / Heidelberg},
  abstract  = {Zero-knowledge proofs were introduced in 1985, in a
                   paper by Goldwasser, Micali and Rackoff ([ 6 ]).
                   Their practical significance was soon demonstrated in
                   the work of Fiat and Shamir ([ 4 ]), who turned
                   zero-knowledge proofs of quadratic residuosity into
                   efficient means of establishing user identities.
                   Still, as is almost always the case in public-key
                   cryptography, the Fiat-Shamir scheme relied on
                   arithmetic operations on large numbers. In 1989,
                   there were two attempts to build identification
                   protocols that only use simple operations (see [ 11 ,
                   10 ]). One appeared in the EUROCRYPT proceedings and
                   relies on the intractability of some coding problems,
                   the other was presented at the CRYPTO rump session
                   and depends on the so-called Permuted Kernel problem
                   (PKP). Unfortunately, the first of the schemes was
                   not really practical. In the present paper, we
                   propose a new identification scheme, based on
                   error-correcting codes, which is zero-knowledge and
                   is of practical value. Furthermore, we describe
                   several variants, including one which has an identity
                   based character. The security of our scheme depends
                   on the hardness of decoding a word of given syndrome
                   w.r.t. some binary linear error-correcting code.},
  chapter   = {2},
  doi       = {10.1007/3-540-48329-2\_2},
  isbn      = {978-3-540-57766-9},
  url       = {http://dx.doi.org/10.1007/3-540-48329-2\_2},
}

@Article{sutherland10:modpol,
  author   = {Br{\"o}ker, Reinier and Lauter, Kristin and Sutherland, Andrew},
  title    = {Modular polynomials via isogeny volcanoes},
  journal  = {Mathematics of Computation},
  year     = {2012},
  volume   = {81},
  number   = {278},
  pages    = {1201--1231},
  abstract = {We present a new algorithm to compute the classical
                   modular polynomial Phi\_nin the rings {Z[X},Y] and
                   ({Z/mZ})[{X,Y}], for a prime n and any positive
                   integer {m.Our} approach uses the graph of
                   n-isogenies to efficiently compute Phi\_n mod pfor
                   many primes p of a suitable form, and then applies
                   the Chinese {RemainderTheorem} ({CRT}). Under the
                   Generalized Riemann Hypothesis ({GRH}), we achieve
                   anexpected running time of O(n^3 (log n)^3 log log
                   n), and compute Phi\_n mod musing O(n^2 (log n)^2 +
                   n^2 log m) space. We have used the new algorithm
                   tocompute Phi\_n with n over 5000, and Phi\_n mod m
                   with n over 20000. We alsoconsider several modular
                   functions g for which Phi\_n^g is smaller than
                   Phi\_n,allowing us to handle n over 60000.},
  doi      = {10.1090/S0025-5718-2011-02508-1},
}

@Article{Sutherland2012,
  author  = {Sutherland, Andrew V.},
  title   = {Accelerating the {CM} method},
  journal = {LMS Journal of Computational Mathematics},
  year    = {2012},
  volume  = {15},
  pages   = {172--204},
  issn    = {1461-1570},
  doi     = {10.1112/S1461157012001015},
}

@Article{sutherland2012constructing,
  author  = {Sutherland, Andrew V.},
  title   = {Constructing elliptic curves over finite fields with prescribed torsion},
  journal = {Mathematics of Computation},
  year    = {2012},
  volume  = {81},
  pages   = {1131--1147},
}

@Article{sutherland2013evaluation,
  author    = {Sutherland, Andrew},
  title     = {On the evaluation of modular polynomials},
  journal   = {The Open Book Series},
  year      = {2013},
  volume    = {1},
  number    = {1},
  pages     = {531--555},
  publisher = {Mathematical Sciences Publishers},
}

@InProceedings{sutherland2013isogeny,
  author    = {Sutherland, Andrew},
  title     = {Isogeny volcanoes},
  booktitle = {ANTS X: Proceedings of the Algorithmic Number Theory 10th International Symposium},
  year      = {2013},
  volume    = {1},
  pages     = {507--530},
  address   = {Berkeley},
  publisher = {Mathematical Sciences Publishers},
  journal   = {The Open Book Series},
}

@Misc{SutherlandDatabase,
  author = {Andrew V. Sutherland},
  title  = {Modular polynomials},
  year   = {2018},
  url    = {https://math.mit.edu/~drew/ClassicalModPolys.html},
}

@Electronic{tao2011expander,
  author = {Terence Tao},
  year   = {2011},
  title  = {Expansion in groups of {Lie} type -- Basic theory of expander graphs},
  url    = {https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/},
}

@Article{Tate,
  author  = {Tate, John},
  title   = {Endomorphisms of abelian varieties over finite fields},
  journal = {Inventiones mathematicae},
  year    = {1966},
  volume  = {2},
  number  = {2},
  pages   = {134--144},
  month   = apr,
  issn    = {1432-1297},
  doi     = {10.1007/BF01404549},
}

@Article{teske-ph,
  author  = {Teske, Edlyn},
  title   = {The {P}ohlig-{H}ellman Method Generalized for Group Structure Computation},
  journal = {Journal of Symbolic Computation},
  year    = {1999},
  volume  = {27},
  number  = {6},
  pages   = {521--534},
  issn    = {0747-7171},
  doi     = {10.1006/jsco.1999.0279},
}

@InProceedings{tillich2008collisions,
  author       = {Tillich, Jean-Pierre and Z{\'e}mor, Gilles},
  title        = {Collisions for the {LPS} expander graph hash function},
  booktitle    = {Annual International Conference on the Theory and Applications of Cryptographic Techniques},
  year         = {2008},
  pages        = {254--269},
  organization = {Springer},
}

@InProceedings{twisted-edwards,
  author    = {Bernstein, Daniel and Birkner, Peter and Joye, Marc and Lange, Tanja and Peters, Christiane},
  title     = {{Twisted Edwards Curves}},
  booktitle = {Progress in Cryptology --- AFRICACRYPT 2008},
  year      = {2008},
  pages     = {389--405},
  abstract  = {{This paper introduces ” twisted Edwards curves,”
                   a generalization of the recently introduced Edwards
                   curves; shows that twisted Edwards curves include
                   more curves over finite fields, and in particular
                   every elliptic curve in Montgomery form; shows how to
                   cover even more curves via isogenies; presents fast
                   explicit formulas for twisted Edwards curves in
                   projective and inverted coordinates; and shows that
                   twisted Edwards curves save time for many curves that
                   were already expressible as Edwards curves.}},
  doi       = {10.1007/978-3-540-68164-9_26},
}

@InProceedings{vanderHoeven:2004:TFT:1005285.1005327,
  author    = {van der Hoeven, Joris},
  title     = {The Truncated {F}ourier Transform and Applications},
  booktitle = {Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation},
  year      = {2004},
  series    = {ISSAC '04},
  pages     = {290--296},
  address   = {New York, NY, USA},
  publisher = {ACM},
  doi       = {10.1145/1005285.1005327},
  isbn      = {1-58113-827-X},
}

@Electronic{Voight2018,
  author = {Voight, John},
  year   = {2018},
  title  = {Quaternion Algebras},
  url    = {https://math.dartmouth.edu/~jvoight/quat-book.pdf},
}

@InProceedings{vzgathen+shoup92,
  author    = {Joachim von zur Gathen and Shoup, Victor},
  title     = {Computing {F}robenius maps and factoring polynomials},
  booktitle = {STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing},
  year      = {1992},
  pages     = {97--105},
  address   = {New York, NY, USA},
  publisher = {ACM},
  abstract  = {A new probabilistic algorithm for factoring
                   univariate polynomials over finite fields is
                   presented whose asymptotic running time improves upon
                   previous results. To factor a polynomial of degree n
                   over F q , the algorithm uses O (( n 2 + n log q
                   )•(log n ) 2 log log n ) arithmetic operations in F
                   q . The main technical innovation is a new way to
                   compute Frobenius and trace maps in the ring of
                   polynomials modulo the polynomial to be factored.},
  doi       = {10.1145/129712.129722},
  isbn      = {0-89791-511-9},
}

@Article{vzgathen+shoup92:journal,
  author   = {von zur Gathen, Joachim and Shoup, Victor},
  title    = {Computing {F}robenius Maps and Factoring Polynomials},
  journal  = {Computational Complexity},
  year     = {1992},
  volume   = {2},
  pages    = {187--224},
  abstract = {A new probabilistic algorithm for factoring
                   univariate polynomials over finite fields is
                   presented. To factor a polynomial of degree n over F
                   q , the number of arithmetic operations in F q is
                   O((n 2 +n log q) \Delta (log n) 2 loglog n). The main
                   technical innovation is a new way to compute
                   Frobenius and trace maps in the ring of polynomials
                   modulo the polynomial to be factored. Subject
                   classifications. {68Q40}; {11Y16}, {12Y05}. 1.
                   Introduction We consider the problem of factoring a
                   univariate polynomial over a finite field. This
                   problem plays a central role in computational
                   algebra. Indeed, many of the efficient algorithms for
                   factoring univariate and multivariate polynomials
                   over finite fields, the field of rational numbers,
                   and finite extensions of the rationals solve as a
                   subproblem the problem of factoring univariate
                   polynomials over finite fields (Kaltofen 1990). This
                   problem also has important applications in number
                   theory (Buchmann 1990), coding theory (Berlekamp
                   1968), and ...},
}

@Book{vzGG,
  title     = {Modern Computer Algebra},
  publisher = {Cambridge University Press},
  year      = {1999},
  author    = {von zur Gathen, Joachim and Gerhard, Jurgen},
  address   = {New York, NY, USA},
  isbn      = {0-521-64176-4},
}

@InProceedings{Williams12,
  author    = {Vassilevska Williams, Virginia},
  title     = {Multiplying matrices faster than {C}oppersmith-{W}inograd},
  booktitle = {STOC'12},
  year      = {2012},
  pages     = {887--898},
  publisher = {ACM},
}

@Article{williams1982,
  author  = {Williams, Hugh C.},
  title   = {A $p+1$ method of factoring},
  journal = {Mathematics of Computation},
  year    = {1982},
  volume  = {39},
  number  = {159},
  pages   = {225--234},
}

@InProceedings{zhang,
  author    = {Zhang, Shengyu},
  title     = {{Promised and Distributed Quantum Search Computing and Combinatorics}},
  booktitle = {Proceedings of the Eleventh Annual International Conference on Computing and Combinatorics},
  year      = {2005},
  volume    = {3595},
  series    = {Lecture Notes in Computer Science},
  pages     = {430--439},
  address   = {Berlin, Heidelberg},
  publisher = {Springer Berlin / Heidelberg},
  abstract  = {{This paper gives a quantum algorithm to search in an
                   set S for a k -tuple satisfying some predefined
                   relation, with the promise that some components of a
                   desired k -tuple are in some subsets of S . In
                   particular when k =2, we show a tight bound of the
                   quantum query complexity for the Claw Finding
                   problem, improving previous upper and lower bounds by
                   Buhrman, Durr, Heiligman, Hoyer, Magniez, Santha and
                   de Wolf [7]. We also consider the distributed
                   scenario, where two parties each holds an n -element
                   set, and they want to decide whether the two sets
                   share a common element. We show a family of protocols
                   s . t . q ( P ) 3/2 . c ( P )= O ( n 2 log n ), where
                   q ( P ) and c ( P ) are the number of quantum queries
                   and the number of communication qubits that the
                   protocol P makes, respectively. This implies that we
                   can pay more for quantum queries to save on quantum
                   communication, and vice versa. To our knowledge, it
                   is the first result about the tradeoff between the
                   two resources.}},
  chapter   = {44},
  doi       = {10.1007/11533719_44},
  isbn      = {978-3-540-28061-3},
}

@Article{gaudry+hess+smart02,
  author               = {Gaudry, Pierrick and Hess, Florian and Smart, Niegel},
  title                = {Constructive and destructive facets of {W}eil descent on elliptic curves},
  journal              = {Journal of Cryptology},
  year                 = {2002},
  volume               = {15},
  number               = {1},
  pages                = {19-46-46},
  month                = mar,
  issn                 = {0933-2790},
  abstract             = {In this paper we look in detail at the curves which arise in the method of Galbraith and Smart for producing curves in the Weil restriction of an elliptic curve over a finite field of characteristic 2 of composite degree. We explain how this method can be used to construct hyperelliptic cryptosystems which could be as secure as cryptosystems based on the original elliptic curve. On the other hand, we show that the same technique may provide a way of attacking the original elliptic curve cryptosystem using recent advances in the study of the discrete logarithm problem on hyperelliptic curves.  We examine the resulting higher genus curves in some detail and propose an additional check on elliptic curve systems defined over fields of characteristic 2 so as to make them immune from the methods in this paper.},
  citeulike-article-id = {7751788},
  citeulike-linkout-0  = {http://dx.doi.org/10.1007/s00145-001-0011-x},
  citeulike-linkout-1  = {http://www.springerlink.com/content/hx8b621p8p4417qv},
  day                  = {1},
  doi                  = {10.1007/s00145-001-0011-x},
  keywords             = {cryptography, ghs, hyperelliptic\_curves, weil\_descent},
  posted-at            = {2010-09-01 15:45:05},
  publisher            = {Springer New York},
  url                  = {http://dx.doi.org/10.1007/s00145-001-0011-x},
}

@Book{joux2009algorithmic,
  title     = {Algorithmic cryptanalysis},
  publisher = {CRC Press},
  year      = {2009},
  author    = {Joux, Antoine},
}

@Article{koblitz87,
  author               = {Koblitz, Neal},
  title                = {Elliptic Curve Cryptosystems},
  journal              = {Mathematics of Computation},
  year                 = {1987},
  volume               = {48},
  number               = {177},
  pages                = {203-209},
  citeulike-article-id = {2405523},
  citeulike-linkout-0  = {http://www.jstor.org/stable/2007884},
  keywords             = {cryptography},
  posted-at            = {2010-07-13 18:02:46},
  url                  = {http://www.jstor.org/stable/2007884},
}

@PhdThesis{lercier-algorithmique,
  author               = {Lercier, Reynald},
  title                = {Algorithmique des courbes elliptiques dans les corps finis},
  school               = {LIX - CNRS},
  year                 = {1997},
  month                = jun,
  citeulike-article-id = {7300668},
  groups               = {Isogenies},
  keywords             = {lercier},
  posted-at            = {2010-06-14 18:24:56},
}

@Electronic{sutherland10,
  author               = {Sutherland, Andrew V.},
  year                 = {2010},
  title                = {Genus 1 point counting over prime fields},
  howpublished         = {Last accessed July 16, 2010. \url{http://www-math.mit.edu/\~drew/SEArecords.html}},
  url                  = {#},
  citeulike-article-id = {7499834},
  citeulike-linkout-0  = {#},
  groups               = {Isogenies},
  keywords             = {cryptography, elliptic\_curve, schoof},
  posted-at            = {2010-07-16 13:25:40},
}

@article{10.1016/j.dam.2007.12.010,
author = {Galbraith, Steven D. and Paterson, Kenneth G. and Smart, Nigel P.},
title = {Pairings for Cryptographers},
year = {2008},
issue_date = {September, 2008},
publisher = {Elsevier Science Publishers B. V.},
address = {NLD},
volume = {156},
number = {16},
issn = {0166-218X},
doi = {10.1016/j.dam.2007.12.010},
abstract = {Many research papers in pairing-based cryptography treat pairings as a ''black box''. These papers build cryptographic schemes making use of various properties of pairings. If this approach is taken, then it is easy for authors to make invalid assumptions concerning the properties of pairings. The cryptographic schemes developed may not be realizable in practice, or may not be as efficient as the authors assume. The aim of this paper is to outline, in as simple a fashion as possible, the basic choices that are available when using pairings in cryptography. For each choice, the main properties and efficiency issues are summarized. The paper is intended to be of use to non-specialists who are interested in using pairings to design cryptographic schemes.},
journal = {Discrete Applied Mathematics},
month = {sep},
pages = {3113–3121},
numpages = {9},
keywords = {Pairings, Cryptography}
}

@electronic{trevisan-graphs,
  author = {Luca Trevisan},
  title = {Lecture Notes on Graph Partitioning, Expanders and Spectral Methods},
  url = {https://lucatrevisan.github.io/books/expanders-2016.pdf},
  year = {2017},
}

@electronic{sutherland-notes,
  author = {Andrew Sutherland},
  title = {Lecture Notes on Elliptic Curves},
  url = {https://math.mit.edu/classes/18.783/2017/lectures.html},
  year = {2017},
}

@article{waterhouse69,
    author = {Waterhouse, William C.},
    journal = {Annales Scientifiques de l'\'{E}cole Normale Sup\'{e}rieure},
    number = {4},
    pages = {521--560},
    title = {Abelian varieties over finite fields},
    volume = {2},
    year = {1969}
}

@article{mordell61,
  title =	 {Mathematical Notes: The congruence $(p-1/2)! \equiv \pm 1 \mod p$},
  volume =	 {68},
  ISSN =	 {1930-0972},
  DOI =		 {10.1080/00029890.1961.11989636},
  number =	 {2},
  journal =	 {The American Mathematical Monthly},
  publisher =	 {Informa UK Limited},
  author =	 {Mordell, Louis J.},
  year =	 {1961},
  month =	 {Feb},
  pages =	 {131--149}
}

@article{pizer1980,
  title =	 {An algorithm for computing modular forms on $\Gamma_0(N)$},
  volume =	 {64},
  ISSN =	 {0021-8693},
  DOI =		 {10.1016/0021-8693(80)90151-9},
  number =	 {2},
  journal =	 {Journal of Algebra},
  publisher =	 {Elsevier BV},
  author =	 {Pizer, Arnold},
  year =	 {1980},
  month =	 {Jun},
  pages =	 {340--390}
}

@article{isogpoksurvey,
  title =	 {Proving knowledge of isogenies: a survey},
  volume =	 {91},
  ISSN =	 {1573-7586},
  DOI =		 {10.1007/s10623-023-01243-3},
  number =	 {11},
  journal =	 {Designs, Codes and Cryptography},
  publisher =	 {Springer Science and Business Media LLC},
  author =	 {Beullens, Ward and De Feo, Luca and Galbraith,
                  Steven D. and Petit, Christophe},
  year =	 {2023},
  month =	 {Jun},
  pages =	 {3425--3456}
}

@article{onuki2021,
  title =	 {On oriented supersingular elliptic curves},
  volume =	 {69},
  ISSN =	 {1071-5797},
  DOI =		 {10.1016/j.ffa.2020.101777},
  journal =	 {Finite Fields and Their Applications},
  publisher =	 {Elsevier BV},
  author =	 {Onuki, Hiroshi},
  year =	 {2021},
  month =	 {Jan},
  pages =	 {101777}
}