Cornacchias algoritm

I beräkningstalteorin är Cornacchias algoritm en algoritm för att lösa den diofantiska ekvationen $x^{2}+dy^{2}=m$ , där $1\leq d<m$ och d och m är coprime . Algoritmen beskrevs 1908 av Giuseppe Cornacchia.

Algoritmen

Hitta först valfri lösning på ${\displaystyle r_{0}^{2}\equiv -d{\pmod {m}}} ($ kanske genom att använda en algoritm som listas här ); om det inte finns någon sådan $r_{0}$ kan det inte finnas någon primitiv lösning på den ursprungliga ekvationen. Utan förlust av generalitet kan vi anta att ₀ r ≤ m / 2 (om inte, ersätt r ₀ med m - r ₀ , som fortfarande kommer att vara en rot av - d ). Använd sedan den euklidiska algoritmen för att hitta ${\displaystyle r_{1}\equiv m{\pmod {r_{0}}}} ,$ r $\displaystyle r_ {2}\equiv r_{0}{\pmod {r_{1}}}}$ och så vidare; stoppa när $r_{k}<{\sqrt {m}}$ . Om $s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}$ är ett heltal, då är lösningen $x=r_{k},y=s$ ; annars prova en annan rot av - d tills antingen en lösning hittas eller alla rötter har uttömts. I det här fallet finns det ingen primitiv lösning.

För att hitta icke-primitiva lösningar ( x , y ) där gcd( x , y ) = g ≠ 1 , notera att förekomsten av en sådan lösning innebär att g ² delar m (och ekvivalent, att om m är kvadratfri , då alla lösningar är primitiva). Således kan ovanstående algoritm användas för att söka efter en primitiv lösning ( u , v ) till u ² + dv ² = m / g ² . Om en sådan lösning hittas kommer ( gu , gv ) att vara en lösning på den ursprungliga ekvationen.

Exempel

Lös ekvationen $x^{2}+6y^{2}=103$ . En kvadratrot av −6 (mod 103) är 32 och 103 ≡ 7 (mod 32); sedan $7^{2}<103$ och ${\sqrt {\tfrac {103-7^{2}}{6}}}=3$ , det finns en lösning x = 7, y = 3.

externa länkar

• Basilla, JM (2004). "Om lösningarna för $x^{2}+dy^{2}=m$ " (PDF) . Proc. Japan Acad . 80(A): 40–41.