Jump to content

Korkine–Zolotarev lattice basis reduction algorithm

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Mo-Al (talk | contribs) at 17:08, 11 December 2021 (→References). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

The Korkine–Zolotarev (KZ) lattice basis reduction algorithm is a lattice reduction algorithm invented by A. Korkine and G. Zolotareff in 1877.

References

Korkine, A.; Zolotareff, G. (1877). "Sur les formes quadratiques positives". {{cite journal}}: Cite journal requires |journal= (help)

Lyu, Shanxiang; Ling, Cong (2017). "Boosted KZ and LLL Algorithms" (PDF). {{cite journal}}: Cite journal requires |journal= (help)

{{cite book|first1=Daniele|last1=Micciancio|

first2=Shafi|last2=Goldwasser |title=Complexity of Lattice Problems |year=2002 |url=https://link.springer.com/book/10.1007/978-1-4615-0897-7 |pages=131-136

v t e Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms

Retrieved from "https://en.wikipedia.org/w/index.php?title=Korkine–Zolotarev_lattice_basis_reduction_algorithm&oldid=1059790634"

Hidden category:

CS1 errors: missing periodical