This brief article has nothing to do with Azure Kubernetes Service, and I do not have the faintest interest in cases filed against whatever entity called AKS.
Recently I had the opportunity to read the following paper:
The algorithm introduced in the paper is called AKS Algorithm, an acronym for these three computer scientists.
Its abstract goes:
We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.
I'm not going to provide a full explanation of the paper, but let me write about a few points that impressed me very much.
AKS Algorithm at a glance
And the main theorem of the paper "PRIMES is in P" goes:
Theorem 4.1. The algorithm above returns PRIME if and only if n is prime.
Some basic facts used
① The AKS Algorithm enhances the fact that (X + a)ⁿ ≡ Xⁿ + a (mod n) holds if any only if n is prime (according to Fermat's little theorem) to the following modified condition:
for appropriately chosen and sufficiently small r (prime) and sufficiently enough a.
② Ord(n; r) stands for the order of n in (Z/rZ)*, in other words, the smallest positive integer m satisfying
Then the following is another important fact for AKS Algorithm:
In the original paper log stands for base 2 logarithm, and the above claim is described as follows about the above condition for r:
<Example> Let n = 5690023. If I choose r = 15053, r−1 = 2² × 53 × 71, and calculation shows:
The proof of the above assertion (Lemma 4.3 in the original paper) is remarkably elementary but impressively clever. As a matter of fact r can be chosen in the following process. One would feel the dominoes from step #4 to #5:
Steps to prove Theorem 4.1.
What has to be proved is that a composite number is never mistakenly identified as a prime. The proof consists of the following steps:
Time Complexity Analysis
The importance of the paper by Agrawal-Kayal-Saxena lies not only in the algorithm, but also in the conclusion on the time complex analysis.
■
この記事が気に入ったらサポートをしてみませんか？