Algorytm Cornacchii

W $m$ teorii Cornacchii jest algorytmem rozwiązywania równania , 1 $_ 1\leq d<m}$ i d oraz m są względnie pierwsze . Algorytm został opisany w 1908 roku przez Giuseppe Cornacchię.

Algorytm

Najpierw znajdź $)$ być wymienionego jeśli takie nie $nie$ może być prymitywnego rozwiązania pierwotnego równania. Bez utraty ogólności możemy założyć, że ₀ r ≤ m / 2 (jeśli nie, to zamień r ₀ na m - r ₀ , które nadal będzie pierwiastkiem z - d ). Następnie użyj algorytmu Euklidesa , aby znaleźć ${\ Displaystyle r_ {1} \ równoważnik m {\ pmod {r_ {0}}}}$ , ${\ displaystyle r_ {2}\equiv r_{0}{\pmod {r_{1}}}}$ i tak dalej; przestań, gdy ${\ displaystyle r_ {k}< {\ sqrt {m}}}$ . Jeśli $_$ , ${\ displaystyle x = r_ {k}, y = s$ } w przeciwnym razie wypróbuj inny pierwiastek z - d , aż zostanie znalezione rozwiązanie lub wszystkie pierwiastki zostaną wyczerpane. W tym przypadku nie ma prymitywnego rozwiązania.

Aby znaleźć nieprymitywne rozwiązania ( x , y ) gdzie gcd( x , y ) = g ≠ 1 , zauważ, że istnienie takiego rozwiązania implikuje, że g ² dzieli m (i równoważnie, że jeśli m jest wolne od kwadratów , to wszystkie rozwiązania są prymitywne). Zatem powyższy algorytm może być wykorzystany do poszukiwania prymitywnego rozwiązania ( u , v ) dla u ² + dv ² = m / g ² . Jeśli takie rozwiązanie zostanie znalezione, to ( gu , gv ) będzie rozwiązaniem pierwotnego równania.

Przykład

Rozwiąż równanie ${\ Displaystyle x ^ {2} + 6y ^ {2} = 103}$ . Pierwiastek kwadratowy z −6 (mod 103) to 32, a 103 ≡ 7 (mod 32); od ${\ Displaystyle 7 ^ {2}<103}$ i ${\ Displaystyle {\ sqrt {\ tfrac {103-7 ^ {2}} {6}}} = 3}$ , istnieje rozwiązanie x = 7, y = 3.

Linki zewnętrzne

• Basilla, JM (2004). „O rozwiązaniach ${\ Displaystyle x ^ {2} + dy ^ {2} = m}$ " (PDF) . proc. Japonia Acad . 80 (A): 40–41.