En la prueba de Schoof de encontrar determinísticamente$\sqrt{x} \bmod p$ cuando$p \neq 1 \bmod 16$

Question

Estoy leyendo Schoof del papel en la que dio un polinomio de tiempo para el algoritmo de conteo de puntos de una curva Elíptica sobre campo Finito allí se dio como una aplicación de un algoritmo de forma determinista el hallazgo $\sqrt x \bmod p$ al $p \neq 1 \bmod 16$. Tengo unas dudas en la comprensión de la misma.

1. ¿Cómo podemos calcular Frobenius automorphism $\phi $ $\mathcal{O}$ (una vez que tenemos una curva elíptica que tiene complejo de la multiplicación por $\mathcal{O}$) con Schoof del Algoritmo.
2. En la última sección que decir que cualquiera de las $\zeta_2=-1, \zeta_4=\sqrt{-1}\mbox{ or } \zeta_8=\frac{\sqrt{2}(1+\sqrt{-1})}{2}$ es un generador de la parte 2 de $Z_p^{*}$. A partir de lo que el análisis en el papel es esta implícita??

Answer 1

La parte 2 es fácil ver como su algoritmo que nos permita tomar la raíz cuadrada de "pequeñas cantidades" módulo p(Como la complejidad depende es = $\sqrt{|x|} \log^{9}p$). Así, se puede evaluar $\zeta_2,\zeta_4,\zeta_8 $, ya que todos ellos implican tomar las raíces cuadradas de los números de pequeña magnitud como $\sqrt{-1},\sqrt{2}$, y como Jyrki mencionar si $p \neq 1 \mod 16$, a continuación, uno de ellos sería un generador de 2-parte de este grupo (básicamente un no residuo).

Tenga en cuenta que tan pronto como me mueva a $\zeta_{16}$ ya no consiste en tomar las raíces cuadradas de sólo un pequeño número, por lo que este método no puede ser extendido.

Para la parte 1 : Después de encontrar una curva elíptica tener complejo de la multiplicación por $\mathcal{O}$ podemos encontrar la Frobenius endomorfismo como se satisface esta ecuación $$ 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 $^2/b^2 = \sqrt{x} \mod p$