Algoritmo de Cornacchia

En teoría de números computacionales , el algoritmo de Cornacchia es un algoritmo para resolver la ecuación diofántica , donde d y m son primos entre sí . El algoritmo fue descrito en 1908 por Giuseppe Cornacchia. ^[1] $x^{2}+dy^{2}=m$ $1\leq d<m$

El algoritmo

Primero, encuentre una solución para (quizás usando un algoritmo que se menciona aquí ); si no existe, no puede haber una solución primitiva para la ecuación original. Sin pérdida de generalidad, podemos suponer que $r$ $0$ $\leq$ $⁠$ $r_{0}^{2}\equiv -d{\pmod {m}}$ $estilo de visualización r_{0}$ $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}metro/2⁠$ (si no, entonces reemplace $r 0$ con $m$ $-$ $r$ $0$ , que seguirá siendo una raíz de $-$ $d$ ). Luego use el algoritmo euclidiano para encontrar,y así sucesivamente; deténgase cuando. Sies un entero, entonces la solución es; de lo contrario, intente con otra raíz de $-$ $d$ hasta que se encuentre una solución o se hayan agotado todas las raíces. En este caso no hay una solución primitiva. $r_{1}\equiv m{\pmod {r_{0}}}$ $r_{2}\equiv r_{0}{\pmod {r_{1}}}$ $r_{k}<{\sqrt {m}}$ $s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}$ $x=r_{k},y=s$

Para encontrar soluciones no primitivas $(x, y)$ donde $mcd(x, y) = g \neq 1$ , tenga en cuenta que la existencia de dicha solución implica que $g 2$ divide $a m$ (y, equivalentemente, que si $m$ no tiene cuadrados , entonces todas las soluciones son primitivas). Por lo tanto, el algoritmo anterior se puede utilizar para buscar una solución primitiva $(u, v)$ para $u$ $2$ $+$ $dv$ $2$ $=$ $⁠$ $metro / g 2 ⁠$ . Si se encuentra dicha solución, entonces $(gu, gv)$ será una solución a la ecuación original.

Ejemplo

Resuelve la ecuación . La raíz cuadrada de −6 (mod 103) es 32, y 103 ≡ 7 (mod 32); como y , hay una solución x = 7, y = 3. $x^{2}+6y^{2}=103$ $7^{2}<103$ ${\sqrt {\tfrac {103-7^{2}}{6}}}=3$

Referencias

^ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione ". Giornale di Matematiche di Battaglini . 46 : 33–90. $\sum _{h=0}^{n}C_{h}x^{n-h}y^{h}=P$

Enlaces externos

Basilla, JM (2004). "Sobre las soluciones de x 2 + d y 2 = m {\displaystyle x^{2}+dy^{2}=m} " (PDF) . Proc. Japan Acad . 80(A): 40–41.