# On Schoof's proof of deterministically finding $\sqrt{x} \bmod p$ when $p \neq 1 \bmod 16$

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.

1. 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.
2. 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??
• Re: Part 2. The multiplicative group of the field $\Bbb{Z}/p\Bbb{Z}$ is cyclic of order $p-1$. As $16\nmid (p-1)$ the 2-part of this group is of order $2,4$ or $8$, and thus generated by a root of unity of the appropriate order. Commented Jul 9, 2016 at 6:34

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$