Minor issues

[defeo]

• [x] Abstract “the finite field” → “a finite field”
• [x] p. 1 line 1: “point at infinity” → “identity element” or “distinguished rational point”.
• [x] p. 1 lines -10 and -8: “the rational fractions” → “rational functions”.
• [x] p. 1 line -8: “abscissas of ker” → “abscissas of the points in ker”.
• [x] p. 1 line -9: given that [Vél71] is not easily available, as a favor to the reader I suggest also citing a more accessible reference such as [5, §25,1,1] or [16, §12.3].
• [x] p. 1 line -5: give a citation for Tate’s isogeny theorem [15].
• [x] p. 1 line -2: “of which we want to compute the cardinality” → “whose rational points we wish to count”
• [x] p. 1 line -1: log(#E) → log(#E(F_q)), or better, just write log q.
• [x] p. 2 line 1: “cardinality of E” → “cardinality of E(F_q)”
• [x] p. 2 line 10: The optimized computation for computing (instantiated) modular polynomials in the context of the SEA algorithm is actually in [12], which builds on [BLS10](a complete reference for [BLS10] is [1]); I suggest citing both.
• [x] p. 2 line 21: An algorithm which takes as input E/F_q and an integer r and has a running time that is quasi-quadratic in r is not, strictly speaking, a polynomial-time algorithm, since the input has size O(log q + log r) (but it is polynomial in the size of the desired output h or ψ).
• [x] p. 2 line -13: “d_k the discriminant” → “d_k is the discriminant”
• [x] p. 2 line -12: “reunion” → “union” (I’m not sure why a direct limit is needed, but OK).
• [x] p. 2 line -10: “in ℤ_ℓ” → “over ℤ_ℓ” or “in ℤ_ℓ[x]”.
• [x] p. 2 line -7: I’m not sure what “binary costs” mean (presumably elements of F_q are represented in binary), “other costs” would be better.
• [x] p. 3 line 4: “structure of” → “structure as”.
• [x] p. 3 line 10: comma after “return it”.
• [x] p. 4 line 1: “with classic modular polynomial arithmetic” → “using polynomial arithmetic over F_q ”
• [x] p. 4 line 6: “time” → “expected time”
• [x] p. 4 Proof of Lemma 1.1 line 2: it is confusing to use the symbol σ to denote an integer exponent, since it is often used to denote an automorphism and written in the same place; I suggest e or s as an alternative choice.
• [x] p. 5 line 8: “address” → “refer”
• [x] p. 5 line -1: it might be worth explaining why v_ℓ(λ - μ) is equal to the depth of the ℓ-volcano (it follows from Theorem 7.iv of [Sut13], for example).
• [ ] p. 6 line 7: “trigonalizable” → “conjugate to an upper triangular matrix”.
• [x] p. 6 Def 2.4: Perhaps add that you call a point P of order ℓ^k is horizontal if it generates the kernel of a horizontal ℓ^k -isogeny, since you use this terminology in several places where P is not explicitly defined as part of a basis for E[ℓ^k].
• [x] p. 6 line -1: It does not make sense to speak of the “multiplicative order” of a point in an additive group (that is not embedded in a ring); what exactly do you mean here?
• [x] p.7 line 19: Should mod h be mod ℓ^h? It is clear that μ and λ cannot both be 1 mod ℓ^(h+1) (since h = v_ℓ(λ − μ)), but it is not clear to me why they cannot both be 1 mod ℓ^h; this should be explained (or corrected).
• [x] p.7 Prop 2.8.iii: what happens if β > k?
• [x] p.7 line -2: You might remind the reader again that E is assumed to be ordinary.
• [x] p. 8 Alg 1: Please do not use the symbol h as a variable name. Elsewhere you define h as the height/depth of the ℓ-volcano, and you refer to h with tis understanding just six lines above the algorithm!
• [x] p. 8 Alg 1: Why is line 9 well defined? (i.e. why are ℓ^(i-1-h)b' and ℓ^(i-1-h)c' integers?)
• [x] p. 9 Alg 2: Do you want k > h? If not, how is line 7 to be interpreted?
• [x] Fix all incomplete/incorrect references! I understand that [Atk88,Atk91,CCR91,Elk92] may be difficult (but you can cite [4] for the latter). For preprints such as [LV16] you should give a citation as in [8]. However, [BLS10] is published (see [1] below), and I think perhaps [BS11] is a reference to the published paper [7](which has the same title but one of the authors is different).
• [x] In reference [Koh96], “Berkely” → “Berkeley”

[1] Reiner Bröker, Kristin Lauter, and Andrew V. Sutherland, Modular polynomials via isogeny volcanoes, Mathematics of Computation 81 (2012), 1201–1231. [4] Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, in Computational perspectives on number theory: proceedings of a conference in honor of A.O.L. Atkin (D.A. Buell and J.T. Teitelbaum eds.), 21–76, AMS, 1997. [5] Steven D. Galbraith, Mathematics of public key cryptography, Cambridge University Press, 2012. [7] Patrick Longa and Francesco Sica, Four-dimensional Gallant-Lambert-Vanstone Scalar Multiplication, Journal of Cryptology 27 (2014), 248–283. [8] Pierre Lairez and Tristan Vaccon, On p-adic differential equations with separation of variables, 2016 preprint available at http://arxiv.org/abs/1602.00244. [12] Andrew V. Sutherland, On the evaluation of modular polynomials, in Algorithmic Num- ber Theory 10th International Symposium (ANTS X), Open Book Series 1, Mathemat- ical Science Publishers, 2013, 531–555. [15] John Tate, Endomorphisms of abelian varieties over finite fields, Inventiones Mathemat- icae 2, 134–144. [16] Lawrence C. Washington, Elliptic curves: Number theory and cryptography, CRC Press, 2008.

[plut]

• “trigonalizable” exists, https://www.encyclopediaofmath.org/index.php/Trigonalizable_element (and this is the right definition)
• I don't understand the sentence immediately following (in the parentheses) Prop. 2.6
• 2.8.(iii) I agree that this is not exactly elegant, but it works when considering lcm in ℚ; the alternative would be ℓ^{\min (v_ℓ(d_2), k-β)} which is even worse.

[defeo]

I don't understand the sentence immediately following (in the parentheses) Prop. 2.6

Me neither. Git blames you, though :)

[plut]

Alors personne ne sera embêté que je l'efface...

[plut]

Il y a un moyen de dire “Wontfix” sur un de ces items? (Par exemple celui sur d_K, où le reviewer a lu un peu vite)

[defeo]

Tu peux éditer la description (voir mon edit)