Cornacchia's algorithm

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

1 The algorithm
2 Example
3 References
4 External links

The algorithm

First, find any solution to $r_0^2\equiv-d\pmod m$ ; if no such $r 0$ 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 = r k, y = s$ ; otherwise there is no solution.

Example

Solve the equation $x 2 + 6 y 2 = 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

^ 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

Basilla, Julius Magalona (12 May 2004). "On Cornacchia's algorithm for solving the diophantine equation $u 2 + d v 2 = m$ " (PDF). http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pja/1116442240.

Number-theoretic algorithms

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 division

Sieving algorithms	Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization

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's

Multiplication algorithms	Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithm

Discrete logarithm algorithms	Baby-step giant-step · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieve

GCD algorithms	Binary GCD · Euclidean · Extended Euclidean · Lehmer's

Modular square root algorithms	Cipolla · Pocklington's · Tonelli–Shanks

Other algorithms	Chakravala · Cornacchia · integer relation algorithm · integer square root · Modular exponentiation · Schoof's

Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).

fonte: https://web.archive.org/web/20120425211759/https://en.wikipedia.org/wiki/Cornacchia%27s_algorithm

Personal tools

Interaction

Toolbox

What links here
Related changes
Upload file
Special pages
Permanent link
Cite this page

Print/export

Create a book
Download as PDF
Printable version

Conheça Walt Disney World

Cornacchia's algorithm

Contents

The algorithm

Example

References

External links

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Interaction

Toolbox

Print/export