I am reading Schoof's paper in which he gave a polynomial time algorithm for counting points on an Elliptic curve over Finite field there he gave as an application an algorithm for deterministically finding $\sqrt x \bmod p$ when $p \neq 1 \bmod 16$. I have few doubts in understanding the same.
- How can we compute Frobenius automorphism $\phi $ in $\mathcal{O}$ (once we have an elliptic curve which has complex multiplication by $\mathcal{O}$) using Schoof's Algorithm.
- In the last section they say that either $\zeta_2=-1, \zeta_4=\sqrt{-1}\mbox{ or } \zeta_8=\frac{\sqrt{2}(1+\sqrt{-1})}{2}$ is a generator of the 2-part of $Z_p^{*}$. From what analysis in the paper is this implied??
Part 2 is easy to see as his algorithm allow us to take square root of "small numbers" modulo p(As the complexity depends is = $\sqrt{|x|} \log^{9}p$). So one can evaluate $\zeta_2,\zeta_4,\zeta_8 $ as all of them involve taking square roots of numbers of small magnitude like $\sqrt{-1},\sqrt{2}$ and as Jyrki mention if $p \neq 1 \mod 16$ then one of them would be a generator of 2-part of this group (basically a non residue).
Note that as soon as me move to $\zeta_{16}$ it no longer involves taking square roots of only small numbers, so this method cannot be further extended.
For part 1 : After finding an elliptic curve having complex multiplication by $\mathcal{O}$ we can find the Frobenius endomorphism as it satisfies this equation $$ X^2-aX+q=0$$ and since endomorphism belong to the quadratic number ring we can also write it in the form of $\frac{a+b\sqrt{x}}{2}$ where $4q=a^2-b^2x$ and thus $a^2/b^2 = \sqrt{x} \mod p$