Algoritmul Cornacci

Algoritmul Cornacci este un algoritm pentru rezolvarea unei ecuații diofantine , unde , și d și m sunt coprime . Algoritmul a fost descris în 1908 de Giuseppe Cornacci [1] . $x^{2}+dy^{2}=m$ $1\leq d<m$

Algoritm

Mai întâi găsim orice soluție . Dacă aceasta nu există, ecuația originală nu are soluții primitive. Fără pierderea generalității, putem presupune că (dacă nu este cazul, înlocuiți r 0 cu m - r 0 , care rămâne rădăcina lui - d ). Acum folosim algoritmul lui Euclid pentru a găsi , și așa mai departe. Ne oprim când . Dacă este un număr întreg, atunci soluția este . Altfel, nu există o soluție primitivă. $r_{0}^{2}\equiv -d{\pmod {m)}$ $r_{0}$ $r_{0}\leq {\tfrac {m}{2)}$ $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$

Pentru a găsi soluții neprimitive ( x , y ) unde gcd( x , y ) = g ≠ 1, rețineți că existența unei astfel de soluții implică faptul că g 2 împarte m (și, în mod echivalent, dacă m este fără pătrat , atunci toate solutiile sunt primitive). Apoi algoritmul de mai sus poate fi folosit pentru a găsi o soluție primitivă ( u , v ) a ecuației . Dacă se găsește o astfel de soluție, atunci ( gu , gv ) va fi soluția ecuației inițiale. $u^{2}+dv^{2}={\tfrac {m}{g^{2)})$

Exemplu

Rezolvăm ecuația . Rădăcina pătrată a lui −6 (mod 103) este 32 și 103 ≡ 7 (mod 32). Deoarece și , există o soluție x = 7, y = 3. $x^{2}+6y^{2}=103$ $7^{2}<103$ ${\sqrt {\tfrac {103-7^{2}}{6}}}=3$

Note

↑ Cornacchia, 1908 , p. 33–90.

Literatură

G. Cornacchia. Su di un metodo per la rezoluție în numeri interi dell' equazione . // Giornale di Matematiche di Battaglini. - 1908. - T. 46 . $\sum _{h=0}^{n}C_{h}x^{nh}y^{h}=P$

Link -uri

Basilla, Julius Magalona Despre algoritmul lui Cornacchia pentru rezolvarea ecuației diofantine $u^{2}+dv^{2}=m$ (PDF) (12 mai 2004). (nedefinit)

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin