Cornacci algoritme

Cornacci-algoritmen er en algoritme til løsning af en diophantinsk ligning , hvor , og d og m er coprime . Algoritmen blev beskrevet i 1908 af Giuseppe Cornacci [1] . $x^{2}+dy^{2}=m$ $1\leq d<m$

Algoritme

Først finder vi en løsning . Hvis dette ikke eksisterer, har den oprindelige ligning ingen primitive løsninger. Uden tab af generalitet kan vi antage, at (hvis dette ikke er tilfældet, erstat r 0 med m - r 0 , som forbliver roden til - d ). Nu bruger vi Euklids algoritme til at finde , og så videre. Vi stopper når . Hvis er et heltal, så er løsningen . Ellers er der ingen primitiv løsning. $r_{0}^{2}\equiv -d{\pmod {m))$ $r_{0}$ $r_{0}\leq {\tfrac {m}{2))$ ${\displaystyle r_{1}\equiv m{\pmod {r_{0))))$ ${\displaystyle r_{2}\equiv r_{0}{\pmod {r_{1))))$ $r_{k}<{\sqrt {m))$ ${\displaystyle s={\sqrt {\tfrac {m-r_{k}^{2}}{d))))$ $x=r_{k},y=s$

For at finde ikke-primitive løsninger ( x , y ) hvor gcd( x , y ) = g ≠ 1, skal du bemærke, at eksistensen af en sådan løsning indebærer, at g 2 deler m (og tilsvarende, hvis m er kvadratfri , så alle løsninger er primitive). Så kan ovenstående algoritme bruges til at finde en primitiv løsning ( u , v ) af ligningen . Hvis en sådan løsning findes, så vil ( gu , gv ) være løsningen til den oprindelige ligning. ${\displaystyle u^{2}+dv^{2}={\tfrac {m}{g^{2))))$

Eksempel

Vi løser ligningen . Kvadratroden af −6 (mod 103) er 32 og 103 ≡ 7 (mod 32). Da og , er der en løsning x = 7, y = 3. $x^{2}+6y^{2}=103$ $7^{2}<103$ ${\sqrt {\tfrac {103-7^{2}}{6}}}=3$

Noter

↑ Cornacchia, 1908 , s. 33-90.

Litteratur

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

Links

Basilla, Julius Magalona Om Cornacchias algoritme til løsning af den diofantinske ligning $u^{2}+dv^{2}=m$ (PDF) (12. maj 2004). (ubestemt)

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme