Cornacchia's algorithm


Cornacchia's algorithm

In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where 1\le d<m and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1].

Contents

The algorithm

First, find any solution to r_0^2\equiv-d\pmod m; if no such r0 exist, there can be no solution to the original equation. Then use the Euclidean algorithm to find r_1\equiv m\pmod{r_0}, r_2\equiv r_0\pmod{r_1} and so on; stop when r_k<\sqrt m. If s=\sqrt{\tfrac{m-r_k^2}d} is an integer, then the solution is x = rk,y = s; otherwise there is no solution.

Example

Solve the equation x2 + 6y2 = 103. A square root of −6 (mod 103) is 32, and 103 ≡ 7 (mod 32); since 72 < 103 and \sqrt{\tfrac{103-7^2}6}=3, there is a solution x = 7, y = 3.

References

  1. ^ Cornacchia, G. (1908). "Su di un metodo per la risoluzione in numeri interi dell' equazione \sum_{h=0}^nC_hx^{n-h}y^h=P.". 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 u2 + dv2 = 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 u2 + dv2 = m" (PDF). http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1116442240. 


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