Galactic algorithm: Difference between revisions

Revision as of 17:24, 27 January 2025

Revision as of 07:44, 29 January 2025

Line 13:

=== Primality testing ===

The [[AKS primality test]] is galactic. It is the most theoretically sound of any known algorithm that can take an arbitrary number and tell if it is prime. In particular, is ''provably polynomial-time'', ''deterministic'', and ''unconditionally correct''. All other known algorithms fall short on at least one of these criteria, but the shortcomings are minor and the calculations are much faster, so they are used instead. [[Elliptic curve primality proving|ECPP]] in practice runs much faster than AKS, but it has never been proven to be polynomial time. The [[Miller–Rabin primality test|Miller–Rabin]] test is also much faster than AKS, but produces only a probabilistic result. However the probability of error can be driven down to arbitrarily small values (say <math>< 10^{-100}</math>), good enough for practical purposes. There is also a [[Miller–Rabin primality test#Deterministic variants|deterministic version]] of the Miller-Rabin test, which runs in runs in polynomial time over all inputs, but its correctness depends on the [[generalized Riemann hypothesis]] (which is widely believed, but not proven). The existence of these (much) faster alternatives means AKS is not used in practice.

=== Matrix multiplication ===