Template:Number-theoretic algorithms: Difference between revisions

Revision as of 15:30, 22 May 2012

Latest revision as of 06:37, 8 May 2025

(47 intermediate revisions by 32 users not shown)

Line 1:

{{Navbox

| name = Number-theoretic algorithms

| state = {{{state|uncollapsed}}}

| title = [[number theory|Number-theoretic]] [[algorithm]]s

| listclass = hlist

| group1 = [[Primality test]]s

| list1 =

*<span style='border-bottom:1px solid black'>[[AKS primality test|AKS]]</span>

*<span style='border-bottom:1px solid black'>[[Adleman–Pomerance–Rumely primality test|APR]]</span>

* [[Baillie–PSW primality test|Baillie–PSW]]

*<span style='border-bottom:1px solid black'>[[Elliptic curve primality proving|ECPPElliptic curve]]</span>

* [[Elliptic curvePocklington primality testingtest|Elliptic curvePocklington]]

* [[PocklingtonFermat primality test|PocklingtonFermat]]

* [[FermatLucas primality test|FermatLucas]]

* ''[[LucasLucas–Lehmer primality test|LucasLucas–Lehmer]]''

*<span style='border-bottom:1px solid black'>''[[Lucas–Lehmer–Riesel test|Lucas–Lehmer–Riesel]]''</span>

*<span style='border-bottom:1px solid black'>''[[Lucas–Lehmer primality test|Lucas–Lehmer]]''</span>

* ''[[Proth's theorem]]''

*<span style='border-bottom:1px solid black'>''[[Lucas–Lehmer–Riesel test|Lucas–Lehmer–Riesel]]''</span>

* ''[[Pépin's test|Pépin's]]''

*<span style='border-bottom:1px solid black'>''[[Proth's theorem]]''</span>

* [[Quadratic Frobenius test|Quadratic Frobenius]]

*<span style='border-bottom:1px solid black'>''[[Pépin's test|Pépin's]]''</span>

* [[Solovay–Strassen primality test|Solovay–Strassen]]

* [[Miller–Rabin primality test|Miller–Rabin]]

*<span style='border-bottom:1px solid black'>[[Trial division]]</span>

| group2 = [[generatingGenerating primes|Prime -generating]] algorithms

| list2 =

* [[Sieve of Atkin]]

* [[Sieve of Eratosthenes]]

* [[Sieve of SundaramPritchard]]

* [[WheelSieve of factorizationSundaram]]

* [[Wheel factorization]]

| group3 = [[Integer factorization]] algorithms

| list3 =

* [[continuedContinued fraction factorization|Continued fraction (CFRAC)]]

* [[Dixon's factorization method|Dixon's]]

* [[Lenstra elliptic -curve factorization|Lenstra elliptic curve (ECM)]]

* [[Euler's factorization method|Euler's]]

* [[Pollard's rho algorithm|Pollard's rho]]

* [[Pollard's p &minus; 1 algorithm|''p'' − 1]]

* [[Williams's p + 1 algorithm|''p'' + 1]]

* [[quadraticQuadratic sieve|Quadratic sieve (QS)]]

* [[generalGeneral number field sieve|General number field sieve (GNFS)]]

* ''[[specialSpecial number field sieve|''Special number field sieve (SNFS'')]]''

* [[rationalRational sieve]]

* [[Fermat's factorization method|Fermat's]]

* [[Shanks's square forms factorization|Shanks's square forms]]

* [[Trial division]]

* [[Shor's algorithm|Shor's]]

| group4 = [[Multiplication algorithm|Multiplication]]s

| list4 =

* [[Ancient Egyptian multiplication|Ancient Egyptian]]

* [[Toom–CookLong multiplication|Long]]

* [[Karatsuba algorithm|Karatsuba]]

*[[Toom–Cook multiplication]]

* [[Toom–Cook multiplication|Toom–Cook]]

*[[Schönhage–Strassen algorithm]]

* [[Fürer'sSchönhage–Strassen algorithm|Schönhage–Strassen]]

* [[SchoofFürer's algorithm|SchoofFürer's]]

| group5 = [[DiscreteEuclidean logarithmdivision|Euclidean]] algorithms[[Division algorithm|division]]

| list5 =

* [[Binary division|Binary]]

*[[Baby-step giant-step]]

* [[Chunking (division)|Chunking]]

*[[Pollard's rho algorithm for logarithms|Pollard rho]]

* [[Fourier division|Fourier]]

*[[Pollard's kangaroo algorithm|Pollard kangaroo]]

* [[Goldschmidt division|Goldschmidt]]

*[[Pohlig–Hellman algorithm|Pohlig–Hellman]]

* [[Newton–Raphson division|Newton-Raphson]]

*[[Index calculus algorithm|Index calculus]]

* [[Long division|Long]]

*[[Function field sieve]]

* [[Short division|Short]]

* [[SRT division|SRT]]

| group6 = [[GreatestDiscrete common divisor|GCDlogarithm]] algorithms

| list6 =

* [[Baby-step giant-step]]

*[[binary GCD algorithm|Binary GCD]]

* [[EuclideanPollard's rho algorithm for logarithms|EuclideanPollard rho]]

* [[ExtendedPollard's Euclideankangaroo algorithm|ExtendedPollard Euclideankangaroo]]

* [[Lehmer's GCDPohlig–Hellman algorithm|Lehmer'sPohlig–Hellman]]

* [[Index calculus algorithm|Index calculus]]

* [[Function field sieve]]

| group7 = Modular[[Greatest squarecommon root algorithmsdivisor]]

| list7 =

* [[Cipolla'sBinary GCD algorithm|CipollaBinary]]

* [[Pocklington'sEuclidean algorithm|Pocklington'sEuclidean]]

* [[Tonelli–ShanksExtended Euclidean algorithm|Tonelli–ShanksExtended Euclidean]]

* [[binaryLehmer's GCD algorithm|Binary GCDLehmer's]]

| group8 = Other[[Quadratic algorithmsresidue|Modular square root]]

| list8 =

* [[Cipolla's algorithm|Cipolla]]

*[[chakravala method|Chakravala]]

* [[CornacchiaPocklington's algorithm|CornacchiaPocklington's]]

* [[integer relationTonelli–Shanks algorithm|Tonelli–Shanks]]

* [[Berlekamp–Rabin algorithm|Berlekamp]]

*[[integer square root]]

*[[Modular exponentiation]]

*[[Schoof's algorithm|Schoof's]]

| group9 = Other algorithms

| list9 =

* [[chakravalaChakravala method|Chakravala]]

* [[Cornacchia's algorithm|Cornacchia]]

* [[Exponentiation by squaring]]

* [[integerInteger square root]]

* [[Integer relation algorithm|Integer relation]] ([[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|LLL]]; [[Korkine–Zolotarev lattice basis reduction algorithm|KZ]])

* [[Modular exponentiation]]

* [[Montgomery reduction]]

* [[Schoof's algorithm|Schoof]]

* [[Trachtenberg system]]

| belowclass = hlist

| below =

* ''Italics'' indicate that algorithm is for numbers of special forms

| below = ''Italics'' indicate that algorithm is for numbers of special forms; <span style='border-bottom:1px solid black;'>underline</span> indicates [[deterministic algorithm]] for primality tests.

}}<noinclude>

{{doc|content=

[[Category:Computer science templates]]

{{collapsible option}}

[[Category:Computer science templatesnavigational boxes]]

[[Category:Number theory navigational boxes]]

}}

</noinclude>