Template:Number-theoretic algorithms: Difference between revisions

Revision as of 08:02, 9 February 2015

Latest revision as of 06:37, 8 May 2025

(37 intermediate revisions by 24 users not shown)

Line 7:

| group1 = [[Primality test]]s

| list1 =

* {{smallcaps|[[AKS primality test|AKS test]]}}

* {{smallcaps|[[Adleman–Pomerance–Rumely primality test|APR test]]}}

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

* {{smallcaps|[[Elliptic curve primality proving|ECPP test]]}}

* [[Elliptic curve primality |Elliptic curve]]

* [[Pocklington primality test|Pocklington]]

* [[Fermat primality test|Fermat]]

* [[Lucas primality test|Lucas]]

* {{smallcaps|''[[Lucas–Lehmer primality test|Lucas–Lehmer]]''}}

* {{smallcaps|''[[Lucas–Lehmer–Riesel test|Lucas–Lehmer–Riesel]]''}}

* {{smallcaps|''[[Proth's theorem]]''}}

* {{smallcaps|''[[Pépin's test|Pépin's]]''}}

* [[Quadratic Frobenius test|Quadratic Frobenius]]

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

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

* {{smallcaps|[[Trial division]]}}

| group2 = [[Generating primes|Prime-generating]]

Line 28 ⟶ 26:

* [[Sieve of Atkin]]

* [[Sieve of Eratosthenes]]

* [[Sieve of Pritchard]]

* [[Sieve of Sundaram]]

* [[Wheel factorization]]

Line 35 ⟶ 34:

* [[Continued 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 − 1 algorithm|''p'' − 1]]

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

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

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

Line 45 ⟶ 44:

* [[Rational sieve]]

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

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

* [[Trial division]]

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

Line 58 ⟶ 57:

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

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

| list5 =

* [[Binary division|Binary]]

* {{smallcaps|[[Baby-step giant-step]]}}

* [[Chunking (division)|Chunking]]

* [[Fourier division|Fourier]]

* [[Goldschmidt division|Goldschmidt]]

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

* [[Long division|Long]]

* [[Short division|Short]]

* [[SRT division|SRT]]

| group6 = [[Discrete logarithm]]

| list6 =

* {{smallcaps|[[Baby-step giant-step]]}}

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

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

* {{smallcaps|[[Pohlig–Hellman algorithm|Pohlig–Hellman]]}}

* [[Index calculus algorithm|Index calculus]]

* [[Function field sieve]]

| group6group7 = [[Greatest common divisor]]

| list6list7 =

* [[Binary GCD algorithm|Binary]]

* [[Euclidean algorithm|Euclidean]]

Line 74 ⟶ 84:

* [[Lehmer's GCD algorithm|Lehmer's]]

| group7group8 = [[Quadratic residue|Modular square root]]

| list7list8 =

* [[Cipolla's algorithm|Cipolla]]

* [[Pocklington's algorithm|Pocklington's]]

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

* [[Berlekamp–Rabin algorithm|Berlekamp]]

| group8group9 = Other algorithms

| list8list9 =

* [[Chakravala method|Chakravala]]

* [[Cornacchia's algorithm|Cornacchia]]

* [[Exponentiation by squaring]]

* [[Integer relation algorithm|Integer relation]]

* [[Integer 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's]]

* [[Trachtenberg system]]

| belowclass = hlist

| below =

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

* {{smallcaps|Smallcaps}} indicate a [[deterministic algorithm]]

}}<noinclude>

{{doc|content=

{{collapsible option}}

[[Category:Computer science templatesnavigational boxes]]

[[Category:MathematicsNumber theory navigational boxes]]

}}

</noinclude>