 Cornacchia's algorithm

In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation x^{2} + dy^{2} = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia^{[1]}.
Contents
The algorithm
First, find any solution to ; if no such r_{0} exist, there can be no solution to the original equation. Then use the Euclidean algorithm to find , and so on; stop when . If is an integer, then the solution is x = r_{k},y = s; otherwise there is no solution.
Example
Solve the equation x^{2} + 6y^{2} = 103. A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since 7^{2} < 103 and , there is a solution x = 7, y = 3.
References
 ^ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione .". Giornale di Matematiche di Battaglini 46: 33–90.
External links
Morain, M.; Nicolas, J.L. (12 September 1990). "On Cornacchia's algorithm for solving the diophantine equation u^{2} + dv^{2} = m" (PDF). http://www.gage.polytechnique.fr/~morain/Articles/cornac.pdf. Basilla, Julius Magalona (12 May 2004). "On Cornacchia's algorithm for solving the diophantine equation u^{2} + dv^{2} = m" (PDF). http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1116442240.
Primality tests AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial divisionSieving algorithms Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · p − 1 · p + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor'sMultiplication algorithms Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithmDiscrete logarithm algorithms Babystep giantstep · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieveGCD algorithms Modular square root algorithms Cipolla · Pocklington's · Tonelli–ShanksOther algorithms Chakravala · Cornacchia · integer relation algorithm · integer square root · Modular exponentiation · Schoof'sItalics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).Categories: Number theoretic algorithms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Cornacchia — is the Italian word for crow. It is also an Italian surname, and as such may refer to: Michael Cornacchia (born February 23, 1975) is an American actor. Giovanni Cornacchia (born 18 June 1939) is a retired Italian hurdler. Cornacchia s algorithm… … Wikipedia
Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… … Wikipedia
Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th … Wikipedia
Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… … Wikipedia
AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… … Wikipedia
Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version … Wikipedia
Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… … Wikipedia
Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… … Wikipedia
Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… … Wikipedia
Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… … Wikipedia