Cornacchiasův algoritmus - Cornacchias algorithm - Wikipedia

v výpočetní teorie čísel, Cornacchiaův algoritmus je algoritmus pro řešení Diophantine rovnice ${ displaystyle x ^ {2} + dy ^ {2} = m}$, kde ${ displaystyle 1 leq d$ a d a m jsou coprime. Algoritmus popsal v roce 1908 Giuseppe Cornacchia.^[1]

Algoritmus

Nejprve najděte jakékoli řešení ${ displaystyle r_ {0} ^ {2} equiv -d { pmod {m}}}$ (možná pomocí uvedeného algoritmu tady ); pokud žádný takový není ${ displaystyle r_ {0}}$ existují, nemůže existovat primitivní řešení původní rovnice. Bez ztráty všeobecnosti to můžeme předpokládat r₀ ≤ m/2 (pokud ne, pak vyměňte r₀ s m - r₀, který bude i nadále kořenem -d). Poté použijte Euklidovský algoritmus najít ${ displaystyle r_ {1} equiv m { pmod {r_ {0}}}}$, ${ displaystyle r_ {2} equiv r_ {0} { pmod {r_ {1}}}}$ a tak dále; zastavit, když ${ displaystyle r_ {k} <{ sqrt {m}}}$. Li ${ displaystyle s = { sqrt { tfrac {m-r_ {k} ^ {2}} {d}}}}$ je celé číslo, pak řešení je ${ displaystyle x = r_ {k}, y = s}$; jinak zkuste jiný kořen -d dokud není nalezeno řešení nebo nejsou vyčerpány všechny kořeny. V tomto případě neexistuje primitivní řešení.

Najít neprimitivní řešení (X, y) kde gcd (X, y) = G ≠ 1, všimněte si, že existence takového řešení z toho vyplývá G² rozděluje m (a ekvivalentně, že pokud m je bez čtverce, pak jsou všechna řešení primitivní). Výše uvedený algoritmus lze tedy použít k hledání primitivního řešení (u, proti) na u² + dv² = m/G². Pokud se takové řešení najde, pak (gu, gv) bude řešením původní rovnice.

Příklad

Vyřešte rovnici ${ displaystyle x ^ {2} + 6y ^ {2} = 103}$. Druhá odmocnina −6 (mod 103) je 32 a 103 ≡ 7 (mod 32); od té doby ${ displaystyle 7 ^ {2} <103}$ a ${ displaystyle { sqrt { tfrac {103-7 ^ {2}} {6}}} = 3}$existuje řešení X = 7, y = 3.

Reference

externí odkazy

• Basilla, J. M. (2004). "Na řešení ${ displaystyle x ^ {2} + dy ^ {2} = m}$" (PDF). Proc. Japan Acad. 80 (A): 40–41.