The main theorem in the paper is false as stated, for two reasons. First
(and most significantly), the authors assume that one can take ℓ = O(1). While this is
true in most cases, it does not hold in general. Indeed, for any fixed L, we can choose a
fundamental discriminant D < 0 such that (D/ℓ) = -1 for all ℓ ≤ L by imposing congruence
constraints on D modulo ℓ. There are approximately 2^π(L) such D with |D| ≤ 4 ∏_(ℓ≤L) ℓ,
and for each of these discriminants we have L = Ω(log |D|). If we take q to be the least
prime that splits completely in the Hilbert class field of Q(√D), then the Chebotarev density
theorem implies log q = O(log |D|); indeed, one can take 694 for the implied constant, see
[14, Thm. 1.2]. We then have L = Ω(log q). The proposed algorithm requires computing
the modular polynomial Φ_ℓ(X,Y) for all ℓ ≤ L, and this will certainly take Ω(L⁴) time: the
fastest known algorithm [1] to compute Φ_ℓ takes O(ℓ³ log³ ℓ log log ℓ) time, and this bound
is essentially tight, and there are π(L) = Ω(L/ log L) primes ℓ ≤ L to consider. By the
main theorem of complex multiplication, there exist elliptic curves E₁ and E₂ over F_q with
endomorphism algebra Q(√D) (in fact there are h(D) such curves), and given inputs E₁,
E₂, and r, where r is any product of primes that split in Q(√D), the running time of the
proposed algorithm will be Ω((log q)⁴). Thus the claimed bound (1) does not hold.
Under the GRH one can assume ℓ = O((log q)²), which would give an O((log q)⁸) complexity bound. My guess is the truth is more like Õ((log q)⁴), but proving this would require
making heuristic assumptions that are significantly stronger than the GRH. Alternatively,
the authors could give an average or median complexity bound (the latter would give the bound they claim, the former is likely to be worse because it will be heavily impacted by
the worst case performance). I would refer the authors to [9, 10, 11] where these issues
are considered in the context of the SEA algorithm (there one needs a bound L such that
the product of the Elkies primes ℓ ≤ L exceeds 4q, here the authors only need bounds on
the least Elkies prime). I note that while the SEA algorithm is often claimed to run in
Õ((log q)⁴) expected time, this claim depends on a heuristic assumption that is known to
be false (see [9, Thm. 1]); under the GRH the best known bound on the expected running
time of SEA is Õ((log q)⁸) (see [11, Cor. 15]), which is actually worse than the Õ((log q)⁵)
running time of Schoof’s deterministic algorithm. Nevertheless the SEA algorithm is widely
used in practice, and I expect that the algorithm proposed by the authors might similarly
be of practical use, even if they cannot prove a complexity bound that is as strong as they
might like.
The second issue with the main theorem is that the algorithm proposed by the authors
is not deterministic; it relies on efficient probabilistic algorithms for factoring polynomials
over finite fields. If the authors really mean to propose a deterministic algorithm then their
complexity bounds will need to be increased substantially. If not, they should state their complexity bounds as bounds on the expected running time of a probabilistic algorithm (of
Las Vegas type). This applies not only to the main theorem, but also to Proposition 3.1
(and possibly others, the authors should check carefully).
[1] Reiner Bröker, Kristin Lauter, and Andrew V. Sutherland, Modular polynomials via
isogeny volcanoes, Mathematics of Computation 81 (2012), 1201–1231.
[9] Igor E. Shparlinski, On the product of small Elkies primes, Proceedings of the AMS 143
(2015), 1441–1448.
[10] Igor E. Shparlinski and Andrew V. Sutherland, On the distribution of Atkin and Elkies
primes, Foundations of Computational Mathematics 14 (2014), 285–297.
[11] Igor E. Shparlinski and Andrew V. Sutherland, On the distribution of Atkin and Elkies
primes on average, LMS Journal of Computation and Mathematics 18 (2015) 308–322.
[14] Jesse Thorner and Asif Zaman, An explicit bound for the least prime ideal in the Cheb-
otarev density theorem, arXiv:1604.01750.
The main theorem in the paper is false as stated, for two reasons. First (and most significantly), the authors assume that one can take ℓ = O(1). While this is true in most cases, it does not hold in general. Indeed, for any fixed L, we can choose a fundamental discriminant D < 0 such that (D/ℓ) = -1 for all ℓ ≤ L by imposing congruence constraints on D modulo ℓ. There are approximately 2^π(L) such D with |D| ≤ 4 ∏_(ℓ≤L) ℓ, and for each of these discriminants we have L = Ω(log |D|). If we take q to be the least prime that splits completely in the Hilbert class field of Q(√D), then the Chebotarev density theorem implies log q = O(log |D|); indeed, one can take 694 for the implied constant, see [14, Thm. 1.2]. We then have L = Ω(log q). The proposed algorithm requires computing the modular polynomial Φ_ℓ(X,Y) for all ℓ ≤ L, and this will certainly take Ω(L⁴) time: the fastest known algorithm [1] to compute Φ_ℓ takes O(ℓ³ log³ ℓ log log ℓ) time, and this bound is essentially tight, and there are π(L) = Ω(L/ log L) primes ℓ ≤ L to consider. By the main theorem of complex multiplication, there exist elliptic curves E₁ and E₂ over F_q with endomorphism algebra Q(√D) (in fact there are h(D) such curves), and given inputs E₁, E₂, and r, where r is any product of primes that split in Q(√D), the running time of the proposed algorithm will be Ω((log q)⁴). Thus the claimed bound (1) does not hold. Under the GRH one can assume ℓ = O((log q)²), which would give an O((log q)⁸) complexity bound. My guess is the truth is more like Õ((log q)⁴), but proving this would require making heuristic assumptions that are significantly stronger than the GRH. Alternatively, the authors could give an average or median complexity bound (the latter would give the bound they claim, the former is likely to be worse because it will be heavily impacted by the worst case performance). I would refer the authors to [9, 10, 11] where these issues are considered in the context of the SEA algorithm (there one needs a bound L such that the product of the Elkies primes ℓ ≤ L exceeds 4q, here the authors only need bounds on the least Elkies prime). I note that while the SEA algorithm is often claimed to run in Õ((log q)⁴) expected time, this claim depends on a heuristic assumption that is known to be false (see [9, Thm. 1]); under the GRH the best known bound on the expected running time of SEA is Õ((log q)⁸) (see [11, Cor. 15]), which is actually worse than the Õ((log q)⁵) running time of Schoof’s deterministic algorithm. Nevertheless the SEA algorithm is widely used in practice, and I expect that the algorithm proposed by the authors might similarly be of practical use, even if they cannot prove a complexity bound that is as strong as they might like. The second issue with the main theorem is that the algorithm proposed by the authors is not deterministic; it relies on efficient probabilistic algorithms for factoring polynomials over finite fields. If the authors really mean to propose a deterministic algorithm then their complexity bounds will need to be increased substantially. If not, they should state their complexity bounds as bounds on the expected running time of a probabilistic algorithm (of Las Vegas type). This applies not only to the main theorem, but also to Proposition 3.1 (and possibly others, the authors should check carefully).
[1] Reiner Bröker, Kristin Lauter, and Andrew V. Sutherland, Modular polynomials via isogeny volcanoes, Mathematics of Computation 81 (2012), 1201–1231.
[9] Igor E. Shparlinski, On the product of small Elkies primes, Proceedings of the AMS 143 (2015), 1441–1448.
[10] Igor E. Shparlinski and Andrew V. Sutherland, On the distribution of Atkin and Elkies primes, Foundations of Computational Mathematics 14 (2014), 285–297.
[11] Igor E. Shparlinski and Andrew V. Sutherland, On the distribution of Atkin and Elkies primes on average, LMS Journal of Computation and Mathematics 18 (2015) 308–322.
[14] Jesse Thorner and Asif Zaman, An explicit bound for the least prime ideal in the Cheb- otarev density theorem, arXiv:1604.01750.