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??
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 9 '16 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.