Concepts
The AKS primality test is based upon the following theorem: An integer n (≥ 2) is prime if and only if the polynomial congruence relation
holds for all integers a coprime to n (or even just for some such integer a, in particular for a = 1). Note that x is a free variable. It is never substituted by a number; instead you have to expand and compare the coefficients of the x powers.
This theorem is a generalization to polynomials of Fermat's little theorem, and can easily be proven using the binomial theorem together with the following property of the binomial coefficient:
- for all if and only if n is prime.
While the relation (1) constitutes a primality test in itself, verifying it takes exponential time. Therefore, to reduce the computational complexity, AKS makes use of the related congruence
which is the same as:
for some polynomials f and g. This congruence can be checked in polynomial time with respect to the number of digits in n, because it is provable that r need only be logarithmic with respect to n. Note that all primes satisfy this relation (choosing g = 0 in (3) gives (1), which holds for n prime). However, some composite numbers also satisfy the relation. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that, if the congruence holds for all such a in A, then n must be prime.
Read more about this topic: AKS Primality Test
Famous quotes containing the word concepts:
“It is impossible to dissociate language from science or science from language, because every natural science always involves three things: the sequence of phenomena on which the science is based; the abstract concepts which call these phenomena to mind; and the words in which the concepts are expressed. To call forth a concept, a word is needed; to portray a phenomenon, a concept is needed. All three mirror one and the same reality.”
—Antoine Lavoisier (1743–1794)
“Germany collapsed as a result of having engaged in a struggle for empire with the concepts of provincial politics.”
—Albert Camus (1913–1960)
“During our twenties...we act toward the new adulthood the way sociologists tell us new waves of immigrants acted on becoming Americans: we adopt the host culture’s values in an exaggerated and rigid fashion until we can rethink them and make them our own. Our idea of what adults are and what we’re supposed to be is composed of outdated childhood concepts brought forward.”
—Roger Gould (20th century)