p. 1 line -7: Given that this article is focused on the computational complexity of
the problems it aims to solve, identifying the computation of ψ with the computation
of h requires some justification (in particular, the authors should justify the “optimal
time” claim in line -8). One would like to know that the cost of deriving ψ from h is
negligible compared to the cost of computing h. The latter depends on the degree n of
the extension of F_q defined by the points in the kernel of ψ; when n is large the cost
of computing h is high and the cost of deriving ψ will be negligible by comparison, but
when n is small (say n = 1), the cost of computing h is very low and it is not obvious
that it will dominate that the cost of computing ψ (I agree with the authors that in this
case deriving ψ form h is the optimal method for computing ψ, but it is not obvious to
me that the complexity of doing so is negligible).
p. 1 line -7: Given that this article is focused on the computational complexity of the problems it aims to solve, identifying the computation of ψ with the computation of h requires some justification (in particular, the authors should justify the “optimal time” claim in line -8). One would like to know that the cost of deriving ψ from h is negligible compared to the cost of computing h. The latter depends on the degree n of the extension of F_q defined by the points in the kernel of ψ; when n is large the cost of computing h is high and the cost of deriving ψ will be negligible by comparison, but when n is small (say n = 1), the cost of computing h is very low and it is not obvious that it will dominate that the cost of computing ψ (I agree with the authors that in this case deriving ψ form h is the optimal method for computing ψ, but it is not obvious to me that the complexity of doing so is negligible).