¿Cómo calcular raíces cuadradas 2 adic?

Question

Sé que, para un $2$-adic unidad sea un cuadrado perfecto, debe ser de la forma $\cdots001.$, por ejemplo el número $17$ ($10001.$) es un $2$-Plaza de adic. ¿Cómo puedo encontrar la extensión adic de $2$ de sus raíces cuadradas? Debería haber dos, ya sea que es $-1$ veces el otro, pero no sé cómo encontrar uno.

He intentado configurar multiplicación larga y dígitos que conjetura que funcionan, pero parece haber demasiados grados de libertad. Cualquier ideas son apreciadas.

Answer 1

Debido a que la derivada de $x^2-17$, es decir, $2x$ $0 \bmod{2}$ Hensel del Lema no funciona muy limpia. En esta situación, cuando se va de $p$ $p^2$no hay ascensor, o cada ascensor trabajará$\bmod p^2$. Echemos un vistazo a lo que sucede aquí -

$x^2\equiv 17 \bmod 2 \text{ has the solution }x\equiv 1 \bmod 2$

$(2y+1)^2 \equiv 17 \bmod 4 \text { is always true, telling us } x\equiv 1,3 \bmod 4 \text{ both work}$

Cuando nos levantamos a$\bmod 8$ nos encontramos con $1$ $5$ (ascensores de $1 \bmod 4\,$) tanto en el trabajo$\bmod 8$ $3$ $7$ (de los ascensores de $3 \bmod 4$). Tenga en cuenta que parece que tiene 4 soluciones! Veamos$\bmod 16$ y de más allá. $$ \begin{array}\\ 1,5\pmod 8 & 1^2 \equiv (1+16) \equiv 17 \pmod{16} & 5^2\equiv 9 \not \equiv 17 \pmod{16} \\ 3,7\pmod{ 8} & 3^2 \equiv 9 \not\equiv 17 \pmod{16} & 7^2\equiv 49 \equiv 17 \pmod{16} \\ \end{array} $$ Así que de los 4 sólo las soluciones de $1$ $7\bmod 8$ se eleva a$\bmod 16$. Debemos levantar los e intente$\bmod 32$. $$ \begin{array}\\ 1,9\pmod{16} & 1^2 \not\equiv 17 \pmod{32} & 9^2\equiv 81 \equiv 17 \pmod{32} \\ 7,15\pmod{16} & 7^2 \equiv 49 \equiv 17 \pmod{32} & 15^2\equiv 225 \not\equiv 17 \pmod{32} \\ \end{array} $$ Así que de los 4 sólo las soluciones de $9$ $7\bmod 16$ se eleva a$\bmod 32$. Debemos levantar los e intente$\bmod 64$. \begin{array}\\ 9,25\pmod{32} & 9^2 \equiv 81 \equiv 17 \pmod{64} & 25^2\equiv 625 \not\equiv 17 \pmod{64} \\ 7,23\pmod{32} & 7^2 \equiv 49 \not\equiv 17 \pmod{64} & 23^2\equiv 529 \equiv 17 \pmod{64}\end{array}

Bastante tedioso cosas para los seres humanos, pero nada que un sistema de álgebra computacional no batir en ningún momento. Hemos encontrado 2 raíces, $1 + 2^3 + O(2^5)$$1 + 2+ 2^2 + 2^4 + O(2^5)$.

Al Hacer los cálculos a mano es probable que tenga más sentido para encontrar sólo una raíz y se multiplica por $-1=\frac{1}{1-2}=1+2+2^2+...$ para la otra raíz.

Answer 2

Una forma de aplicar Hensel limpiamente es utilizarlo para encontrar no $\sqrt{17}$ $(1+\sqrt{17}\,)/2$, cuyo polinomio mínimo es $X^2-X-4$. Si desea utilizar el método de Newton-Raphson en lugar de Hensel, también trabaja más limpia en $X^2-X-4$.

Answer 3

La fórmula binominal $(1+x)^\frac 12 = 1 + \frac12 x - \frac 18 x^2 + \ldots$ converge si $x \equiv 0 \pmod 8$, que le da una forma para encontrar las raíces cuadradas de cualquier $y \equiv 1 \pmod 8$.

De hecho, las plazas en el $2$-adics son el producto directo de $\langle 4 \rangle$$(1+8\Bbb Z_2)$.

Aquí se pueden aplicar directamente a $17$, y se pondrán aún más rápido, ya que es $1 \pmod {16}$

---

Otra cosa que esto nos dice es que una raíz cuadrada de $1+x$ está cerca de a $1+\frac x2$, así que usted puede calcular recursivamente al decir $\sqrt{1+8x} = (1+4x)\sqrt{(1+8x)/(1+4x)^2} = (1+4x)\sqrt{1-16(x/(1+4x))^2)}$. Esto le da una infinita producto, cuyos términos se acerca más y más a $1$. El número correcto de dígitos dobles en cada iteración

Answer 4

Permítanme añadir a las otras respuestas, con un carácter más concreto de la iteración. Con precisión , me refiero al número de bits utilizados por $2$-ádico entero.

Hensel elevación se asemeja a la iteración de Newton. La costumbre de Newton-Raphson esquema para el recíproco squareroot también funciona para $p$-ádico plazas, siempre se comienza con un close-suficiente estimación inicial, que aquí significa que la unidad inicial dígito debe ser correcta. Multiplicando $a$ con su recíproco squareroot $1/\sqrt{a}$ le da la ordinario squareroot $\sqrt{a}$.

Newton-Raphson cálculo de $x = \frac{1}{\sqrt{a}}$ encuentra un cero de $f(x)=\frac{1}{a x^2}-1$ el uso de la iteración $$x_{n+1} = x_n\,(3 - a x_n^2)/2,$$ siempre que $a\equiv1\pmod{8}$ $x_0$ es impar. El siguiente bit (peso $2$) de $x_0$ es preservado por la iteración; piensa que es como decidir sobre el signo de la squareroot para volver. Así que, básicamente, comenzar con dos bits correctos. A partir de ahí, cada paso en primer lugar, se duplica el número de bits correctos, luego pierde un poco debido a la división por $2$.

Una nota sobre la división por $2$. No hay problema: La división por $2$ se define en $\mathbb{Q}_2$, y los rendimientos un $2$-ádico entero si el dividendo es una $2$-ádico entero. Este es el caso aquí, como $a$ y todos los $x_n$ son impares. Tan sólo de cambio de 1 bit.

Sin embargo, cuando se trabaja con fija de precisión finita, esto significa que algo necesidades para obtener desplazado en el más alto de bits. El valor correcto dependerá en $a$'s lado de bits mayor que no sabe, pero ninguna de las dos opciones funciona en el sentido de que el cuadrado con la misma precisión que da el mismo resultado. Esta es la razón por la que hay cuatro posibles soluciones con precisión finita. Si usted considera que los bits más alta imprecisión y eliminarlo desde el resultado, sólo hay dos soluciones posibles, dependiendo de su elección de $x_0\equiv\pm1\pmod{4}$.

Answer 5

Use el lema de Hensel.

Lema de Hensel no sólo prueba que $p$-adic soluciones existen, también es un algoritmo que toma una solución modulo $p^k$ y refina una solución modulo una energía más alta de $p$.