Tomando raíces cuadradas modulo$2^N$

Question

Estaba intentando resolver$y^2 - y \equiv 16 \pmod{512}$ completando el cuadrado. Aquí está mi solución.

\begin{align} y^2 - y &\equiv 16 \pmod{512} \\ 4y^2 - 4y + 1 &\equiv 65 \pmod{512} \\ (2y-1)^2 &\equiv 65 \pmod{512} \\ 2y - 1 &\equiv \pm 33 \pmod{512} &\text{Found by pointwise search.}\\ 2y &\equiv 34, -32 \pmod{512} \\ y &\equiv 17, -16 \pmod{256} \\ y &\in \{17, 273, 240, 496\} \pmod{512} &\text{These values need to be verified.}\\ y &\in \{240, 273\}\pmod{512} \end{align}

Tuve que resolver$x^2 \equiv 65 \pmod{2^9}$ por una búsqueda puntual. ¿Existe algún método sistemático para resolver equivalencias de la forma$x^2 \equiv a \pmod{2^N}$, o más generalmente$x^2 \equiv a \pmod{p^N}$ para un número primo$p$.

Answer 1

Puede resolverlo en $p$-adics?

Para cualquier $2$-ádico entero $n$ tenemos el familiar Taylor/binomio de potencia de la serie para $\sqrt{1+8n}$:

$\sqrt{1+8n}=1+(1/2)(8n)-...$

Todos omitido términos desaparecen $\bmod 512$ Al $n$ es un múltiplo de a $8$, por lo tanto con $n=8$

$\sqrt{65}\equiv 1+(1/2)(8×8) \bmod 512$

$\sqrt{65}\equiv 1+32\equiv 33 \bmod 512$

Así que una raíz cuadrada (raíz más cerca de $1$ $2$- adics) es $33 \bmod 512$.

Para referencia aquí son más términos en la expansión binomial usados:

$\sqrt{1+8n}=1+(2^2)n-(2^3)n^2+(2^5)n^3-(5×2^5)n^4+(7×2^7)n^5-(21×2^8)n^6+(33×2^{10})n^7-(429×2^9)n^8+...$

Por lo tanto es lo suficientemente muchos términos para obtener, al menos, once bits en la plaza de la raíz ($\bmod 2048$) para cualquier entero $n$ (no sólo los múltiplos de 8 como en el anterior); el exponente en $2$ al menos $11$ en todos los términos. El exponente en $2$ es siempre, al menos, el número de términos prestados (por ejemplo, $2^9$ en el noveno término), lo que garantiza la convergencia en $2$-adics. Tenga en cuenta también que una convencional entero de la plaza de la obtenida de la raíz cuadrada es mayor que un múltiplo de $4$, que en el álgebra convencional podría ser el negativo de la raíz (por ejemplo,$\sqrt{9}=-3$).

Answer 2

Un básico de refinamiento sería utilizar el hecho de que si $x^2\equiv y \pmod{p^N}$, entonces para cada a $N'<N$ también contamos $x^2\equiv y\pmod{p^{N'}}$. Usted podría asumir $y$ es coprime a $p$, ya que de lo contrario usted puede fácilmente sacar sus factores de $p$.

A continuación, puede proceder de la siguiente manera: Encontrar todas las soluciones $x$ a este mod $p$. A continuación, cada una de estas soluciones podrían levantar a $p$ cosas mod $p^2$ - así que usted puede encontrar las soluciones de mod $p^2$ comprobación de los. Entonces usted puede levantar de nuevo a $p^3$ y así sucesivamente - y, desde allí será como máximo de cuatro* las raíces cuadradas de mod $p^N$ (y sólo dos si $p$ es impar). Por lo tanto, usted sólo tendrá que comprobar por $4pN$ valores para que este método de trabajo - mucho mejor que la comprobación $p^N$ valores - pero espera, podemos hacerlo aún mejor!

---

Tenga en cuenta que la elevación real paso puede ser simplificado aún más: Si sabemos que $x^2\equiv y\pmod{p^N}$, entonces podemos intentar buscar algo de $z=x+p^Nc$ tal que $z^2\equiv y\pmod{p^{N+1}}$. De trabajo esto da $x^2+2p^Nc\equiv y\pmod{p^{N+1}}$, que es fácil de resolver para $c$ (o, si $p=2$, nos encontramos con que $c$ incluso no importa la mitad de nuestro anterior de las raíces cuadradas de elevación a dos nuevas raíces cuadradas, y la otra mitad no se levante a todos!!!!). Haciendo esto, una vez que calcule la raíz cuadrada mod $p$, básicamente consiste en limpiar la vela desde allí.

---

Como para realmente solucionar $x^2\equiv y\pmod{p}$, hay algunas maneras - por ejemplo, si $p=4k+3$, usted puede encontrar uno con Fermat poco teorema, pero parece que está muy interesante, en pequeños números primos (por ejemplo,$2$), donde no es difícil comprobar todos los posibles $x$.

---

(*Yo también debería explícitamente señalan que, por $k\geq 3$, hay cuatro soluciones a $x^2=1\pmod{2^k}$ - y, en consecuencia, cualquier número con una raíz cuadrada en realidad tiene cuatro raíces cuadradas las que se olvidó de $65$ mod $512$ se $\pm 223$, el cual puede ser encontrado mediante la adición de $256$ a sus raíces existentes, ya que la adición de $256$ no cambia la plaza de mod $512$.)

Answer 3

Este no es un método general, pero aquí es un truco si $2^k|a-1$ para algunos lo suficientemente grande como $k$.

La reclamación. Si $x^2\equiv a\bmod 2^n$$a\equiv 1\bmod 2^k$,$n\leq 2k$, luego

$$x\equiv \pm \frac{a+1}{2}\bmod 2^{n-1}.$$

Prueba. Como sólo hay dos clases de residuos $\bmod 2^{n-1}$ que va a satisfacer a esto, es suficiente para mostrar que estos dos la tienen. Establecimiento $b=(a+1)/2$ tenemos que mostrar que

$$b^2\equiv a=2b-1\bmod 2^n.$$

De hecho, esto es equivalente a

$$2^n|(b-1)^2 \Leftrightarrow b\equiv 1\bmod 2^{\left\lceil\frac{n}{2}\right\rceil},$$

que es equivalente a

$$a\equiv 1\bmod 2^{\left\lceil\frac{n}{2}\right\rceil},$$

lo cual es cierto como $\left\lceil\frac{n}{2}\right\rceil \leq k$.

Así que, ya que tenemos a $x^2\equiv a\bmod 2^9$$a\equiv 1\bmod 2^6$, $x\equiv \pm \frac{a+1}{2} = \pm 33\bmod 2^8.$

Un resultado similar se sostiene en general:

Si $p$ es una extraña prime con $x^2\equiv a\bmod p^n$$a\equiv 1\bmod 2^k$$n\leq 2k$, luego

$$x\equiv \pm \frac{a+1}{2}\bmod p^n.$$

Esto puede ser demostrado en casi idéntica a la moda.