Primes are in P

From Indian Institute of Technology, Kanpur
Jump to: navigation, search

Prime numbers have fascinated mathematicians since ancient times. Their properties play a crucial role in classic results and proofs of number theory. Primality testing have seen extensive applications in cryptography. There are several algorithms for testing primes, both deterministic and randomized. The first ever polynomial time deterministic algorithm was presented by professors

Manindrda Agrawal, Neeraj Kayal and Nitin Saxena from Indian Institute of Technology, Kanpur in year 2002.
(thumbnail)
Professor Manindra Agrawal
The paper is famously known as Primes is in P

or AKS Primality Test (or Agrawal-Kayal-Saxena primality test).The authors were awarded the renowned Gödel prize[1] for it's discovery. The following article is based upon their revolutionary work in the field of algebra.

Contents

History

Some of the basic techniques for primality testing include Sieve of Eratosthenes, extremely powerful to calculate first n primes. The probabilistic techniques are based upon certain properties which are predominantly found in primes. These properties correspondingly result in providing faster means to detect prime numbers with high probability. Miller-Rabin is one such example.

Since a number < n requires at most logn bits to be represented, a polynomial algorithm must be logarithmic in n.
(thumbnail)
Sieve of Eratosthenes

Basic Idea & Approach

The algorithm is based upon a unique identity satisfied by prime numbers.

Identity: Suppose that a is coprime to p. Then p is prime if and only if

(x - a)^p = (x^p - a ) (mod p) .

However, computing the validity of this statement is bound to take time at-least O(n). Thus, to reduce the terms in the polynomial and increase the efficiency, primality is tested instead upon the following identity

(x - a)^p = (x^p - a) mod (x^r - 1, p)

.

Notations & preliminaries

The algorithm and its proof extensively uses the following number theoretic results:
Let p and r be prime numbers, p!=r

  1. The multiplicative group of any field F_{p^t} for t>0, denoted by F_{p^t}^* is cyclic
  2. Let f(x) be a polynomial with integral coefficients. Then
  3. f(x)^p = f(x^p) (mod p)

  4. Let h(x) be any factor of x^r -1. Let m =m_r (mod r). Then
  5. x^m = x^{m_r} (mod h(x))

  6. Let o_r(p) be the order of p modulo r. Then in F_p, \frac{x^r-1}{x-1} factorises into irreducible polynomials each of degree o_r(p).

Algorithm

On a high level, the algorithm firsts checks in O(logn)^2 time if the number if a power of another number and outputs composite if it is. If this test fails, then the algorithm begins to check divisibility of the number n by a number r smaller than it. This is the most trivial method for checking primality of a number. In order to make this process more efficient, the case when r is prime uses a special property as described in basic idea. For a limited set of numbers lesser than such an r, verification of the polynomial equality upon modulo n, ensures correct result. The input is a number n > 1. The output is PRIME or COMPOSITE.

References

  1. Gödel prize

External Links

Primes is in P

Personal tools
Namespaces

Variants
Actions
Navigation
Tools