{'fraction_non_alphanumeric': 0.049408165979518553, 'fraction_numerical': 0.011969676818725895, 'mean_word_length': 3.6638238486587067, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 36, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deterministic Primality Testing - understanding the AKS algorithm

Prime numbers play a very vital role in modern cryptography and especially the difficulties involved in factoring numbers composed of product of two large prime numbers have been put to use in many modern cryptographic designs. Thus, the problem of distinguishing prime numbers from the rest is vital and therefore there is a need to have efficient primality testing algorithms. Although there had been many probabilistic algorithms for primality testing, there wasn't a deterministic polynomial time algorithm until 2002 when Agrawal, Kayal and Saxena came with an algorithm, popularly known as the AKS algorithm, which could test whether a given number is prime or composite in polynomial time. This project is an attempt at understanding the ingenious idea behind this algorithm and the underlying principles of mathematics that is required to study it. In fact, through out this project, one of the major objectives has been to make it as much self contained as possible. Finally, the project provides an implementation of the algorithm using Software for Algebra and Geometry Experimentation (SAGE) and arrives at conclusions on how practical or otherwise it is.


Introduction
Prime numbers have been studied for a long time because of their fundamental importance in mathematics in general and number theory in particular. Of all the properties of prime numbers that have been widely looked into is an age-old problem, perhaps one of the very few well understood problems in pure mathematics, which is to determine whether a given number is prime or composite.
This problem referred to as the Primality Testing problem is of special interest because of a very vital role it plays in cryptography. The difficulty involved in factoring large numbers composed of a product of two primes, as used in the Rivest-Shamir-Adleman (RSA) crypto system, is one such example where the prime numbers are of at most importance and here, efficient primality testing algorithms need to be in place to ensure that the key used in the RSA encryption system indeed uses only prime numbers.
Primality testing has a long history. One of the very first attempts at the problem was the Sieve of Eratosthenes which finds all the prime numbers until a required n. The idea, though simple was ingenious and it only relies on a basic understanding of numbers. It merely involves listing down all the numbers from 2 to n and then beginning with the first number eliminating its factors. At the end of the exercise the numbers remaining unmarked are the prime numbers. Another way to test whether a given number is prime or composite was formulated; this test was based on the fact that for any given number n, if p is a factor of n greater than √ n then there exists a factor k such that k < √ n.
This fundamental property of numbers led to an algorithm which basically dealt with testing if there exists any number p ≤ √ n such that p | n 1 .
Although both the above tests where simple, none of them where feasible since the complexity involved in determining whether a given number n was prime or composite was Ω(n). An almost 'efficient' test was found with the Fermat's little theorem which states that: Given a number prime p and an a such that (p, a) = 1, then a p−1 = 1 (mod p). Although the above test could be efficiently computed, it could not be used as such since there were numbers called the Carmichael numbers which satisfied the Fermat's property for all a's.
Even though the direct application of the Fermat's little theorem was discarded, it lay the foundation for many different algorithms which were primarily based on this important theorem. Several randomized algorithms were formulated like the Miller-Rabin Test and the Solvay-Strassen Test but none of them, although they were very efficient, could fit into the category of an 'unconditional deterministic polynomial-time algorithm'.
In August 2002, a major breakthrough was achieved by Agrawal, Kayal and Saxena who, together, proposed an algorithm (popularly known as the AKS algorithm) in their paper "'PRIMES is in P". The algorithm which is based on a slight modification of the Fermat's Little Theorem was the first deterministic polynomial-time algorithm for primality testing.
Because of the importance of prime numbers especially in cryptography, it is worth investigating and understanding the algorithm. This project is an attempt in this direction i.e. to study the AKS algorithm, understand the basic principle(s) involved and to implement the same in Software for Algebra and Geometry Experimentation (SAGE).

Chapter 2 Some Prerequisites
In this chapter we present an overview of the Algebra and Number Theory that will be required in the course of reading this report. The main objective here is to make the report as much self contained as possible. The reader may refer to [1], [2] and [3] for a structured and more formal treatment of the topics.

Number Theory essentials
This section introduces some definitions, terminology and certain proofs, in Number Theory, which will be useful during course of the reading this report.

Congruences
Definition 2.1.4: For any positive integer n and for any a, b ∈ Z, we say that a is congruent to b modulo n, denoted by a = b (mod n), if n | a − b.
The relation a = b (mod n) is called a congruence relation and n is called the modulus of the congruence. If n ∤ a − b then we write the congruence relation as a = b (mod n).
Theorem 2.1.5: For any composite number n, there exists a prime p such that p < √ n.
Proof. Since n is a composite number, it can be written of the form a · b for some a, b ∈ Z. Now, we know that both a and b cannot be greater than √ n.
Therefore let us assume that one of them is greater than √ n i.e let b > √ n.
Hence we have, Hence from above we have a < √ n or in other words we have proved that for any factor b > √ n we have a corresponding factor a such that a < √ n. Now, a can either be prime or composite. If a is composite then let p be a prime factor of a and since a < √ n this implies p < √ n. On the other hand if a is prime then a = p.

Residue Classes
Definition 2.1.6: Consider the equivalence relation · = · (mod n). Now, this relation is an equivalence relation on the set Z and it partitions Z into equivalence classes. For any a ∈ Z, the equivalence class containing n is denoted by [a] n and an element z is said to belong to [a] n if z = a (mod n). So in effect [a] n = a + m Z. All these equivalence classes are called residual classes modulo n. Also, it is easy to check that for a positive integer n, there are precisely n distinct residue classes modulo n, namely, [a] n for a = 0, ..., n − 1. The set of residue classes modulo n is denoted by Z n . For any α, β ∈ Z n , β is called as the multiplicative inverse of α if α β = [1] n or in other words α β = 1 (mod n). Also, it is easy to see that a multiplicative inverse for an element a exists if and only if(a, n) = 1.
Notation: Z * n denotes the set of all elements of Z n which have a multiplicative inverse Euler's Phi function Definition 2.1.10: Euler's phi function also known as the Euler's totinet function is defined as the number of elements in the set Z * n . Alternatively, it can also be defined as the number of elements which are co-prime to a given number n. The totient function of a number n is denoted by φ(n).
For any number n = p e 1 1 p e 2 2 .....p er r , where p 1 , p 2 , ..., p r are prime, Proof of the above claim can be found in [1].
Definition 2.1.11: The multiplicative order of a number a modulo n is defined as the smallest integer k such that a k = 1 (mod n ).
Euler's theorem and Fermat's little theorem 1 Theorem 2.1.12: Eulers Theorem: Let n be any positive integer and let a ∈ Z * n then, a φ(n) = 1 (mod n ).In other words, the multiplicative order of a mod n divides φ(n)( i.e. O n (a)) | φ(n)).
A consequence of the Euler's theorem is the Fermat's theorem little theorem, which states that: Theorem 2.1.13: Fermat's Little Theorem: Let p be a prime number and let a ∈ Z p − {[0] p } then, a p−1 = 1 (mod p).
The Fermat's theorem is a very important result which is used in many primality testing algorithms.

Algebra essentials
In this section we introduce the notion of abelian groups, rings and finite fields and a few important properties of each of them which will be used in the subsequent chapters.
Abelian groups Definition 2.2.1: An abelian group is defined as a set G with a binary operation * defined on G such that: ii. there exists an element e ∈ G called the identity element such that for any a ∈ G, a * e = e * a = a.
iii. for every a ∈ G there exists an a ′ called the inverse of a such that a * a ′ = e = a ′ * a.
iv. the binary operation * defined on G is commutative i.e. a * b = b * a Although an abelian group is a smaller notion compared to the a 'Group' in general, we do not define the group and its properties as such since, all the groups which would be dealt with in this report are abelian groups. As a matter of fact, a group can be simply defined as above with an exception that the property (iv) given above is not true for a group. In fact, this is the property which distinguishes between a Group and an Abelian Group.
Note: From the above definition it is easy to see that both Z and Z n form an abelian group under the binary operation addition while, Z * n forms an abelian group under multiplication. ii. for a ∈ H, −a ∈ H.
Then H is called a subgroup of G.

Definition 2.2.3:
The order of a group G is defined as the number of elements in it. It can be finite or infinite and is denoted by |G|.

Cosets and quotient groups
Now, just like we defined in the case of integers in section 2.1, here we generalize the notion of congruences to abelian groups. Definition 2.2.4: Let G be an abelian group, and let H be a subgroup of From this generalization it is easy to see that the relation · = · (mod H) is an equivalence relation on the set G. And since this is an equivalence relation, it partitions G into equivalence classes. For any element a ∈ G we can see that the equivalence class containing a is the set [a] H = a + H = {a + h | h ∈ H } and these equivalence classes are called cosets of H in G.
From the above definition we can see that the number of elements i.e. the cardinality of each of the cosets of H in G is the same and this is same as the number of elements in H or put in other words the cardinality of each of the cosets = order (H) = |H|. Another observation that can be made is that, since the equivalence relation partitions G into equivalence classes we can say that the cardinality of each of cosets = order of H (|H|) will divide order of G (|G|) because we need to have |H| * m = |G| where m is the total number of cosets of h in G. This observation precisely translates as the Lagrange's theorem. Proof. Refer the paragraph above for an explanation.

Rings
Definition 2.2.7: A commutative ring with unity is a set R together with two operations called addition and multiplication defined on R such that i. the set R forms an abelian group under addition with the additive identity as 0 R .
ii. multiplication is associative on the set R such that for iii. the operation of multiplication distributes over addition i.e. a (b + c) = a b + a c.
iv. there exists a multiplicative identity 1 R .
v. multiplication is commutative i.e for a, b ∈ R, a b = b a.
Again as in the case of groups, there does exist a more general notion of Rings. But the reason we give the definition of commutative rings with unity is because we would be using only those here.
Definition 2.2.8: Let R be a ring and let a ∈ R then, we call a as a unit if there exists a b ∈ R such that a b = 1 R . Here b is called the multiplicative inverse of a and vice-versa.

Fields
Definition 2.2.9: Let R be a ring. If all the non -zero elements in the ring R have multiplicative inverses then the ring R is called a Field.
Polynomial rings Definition 2.2.10: Let R be a ring, then we can form the ring of polynomials denoted by R[X] which is the set of all polynomials of the form a 0 + a 1 X + a 2 X 2 + .... + a n X n where a 0 , a 1 , ..., a n ∈ R. Here the X is not a variable but is indeterminate. Put in other words we say a polynomial f ( Cyclotomic Polynomials Definition 2.2.11: Consider the polynomial x n − 1. The factors of this polynomial are e( k n ) where e(t) = e 2πit . Therefore this polynomial can be written as: x − e k n Now, consider the set C n = {k : 1 ≤ k ≤ n, (k, n) = 1}. We define the cyclotomic polynomial Φ n for all n ≥ 1 as: It is easy to see that the cyclotomic polynomial Φ n is a monic polynomial (i.e. polynomial with leading coefficient 1) and has a degree of φ(n).

Additional Theorems
Theorem 2.3.1: Given n is prime, prove that n i = 0 (mod n) . Now, if we assume that the given statement is wrong then, the n in the numerator should be divisible by one of 1 or 2 or · · · i. But then, if that is true then n cannot be prime. Hence our assumption is false and therefore we can conclude that n i = 0 (mod n) when n is prime.
Proof. For n = 2, we can see that 5 2 > 2 3 . Now, we will prove this theorem by induction. Let this be true for some value say, k, k > 2. So, now we have 2k+1 k > 2 k+1 . Now, we have to prove that this is true for k + 1. This implies that we have to show that 2k+3 k+1 > 2 k+2 . This implies But, from our assumption that it is true for n = k, we have: 2k+1 Therefore the it remains to prove that (2k + 2) (2K + 3) (k + 1) (k + 2) > 2. This is true for all k > 1. Therefore our assumption that it is true for n = k is true and therefore the theorem is proved by the principle of mathematical induction.

Chapter 3
The AKS algorithm The objective here is to describe the Primality Testing Algorithm which, when given an input n outputs whether the given input n is prime or composite.
Since the aim is to find a polynomial-time algorithm, the final algorithm should output a result (of whether n is prime or composite) in O(log k n) where log n refers to log 2 n.

Basic Idea
The AKS algorithm is primarily based on a polynomial generalization of the Fermat's Little Theorem which states that: Lemma 3.1.: Let a ∈ Z * n and let n ∈ N. Then n is prime if and only if (X + a) n = X n + a (mod n) Proof. Given n is prime. Then since n i = 0 (mod n) 1 for all i therefore all the coefficients in the equation become zero. Hence the theorem is satisfied. Now consider that (X + a) n = X n + a (mod n), therefore it needs to be proved that any n satisfying the above equation should be prime. Let's assume the contrary. Let n be a composite number. Now, consider a k such that k | n and also co-prime to a. Here the coefficient of X n−q which is n k = 0 (mod n). Therefore, our assumption that n is composite is false. Hence n should be a prime number.
Although the above lemma could be used as a primality test, it is not done since the process of determining whether the given input n is prime or composite would involve computing all the n coefficients, in the worst case. Therefore the time complexity here would be Ω(n) which is not polynomial-time.
Therefore, in order to reduce the complexity involved we take the above lemma but divide both sides of the equation by X r − 1 for a chosen r so that the number of computations needed to be performed is less. Hence, the main objective now is to choose an appropriately small r and test if the equation (X + a) n = X n + a (mod X r − 1,n) is satisfied for sufficient number of a's.

The Algorithm
Below is the algorithm proposed by Agrawal, Kayal and Saxena for primality testing: i. If n = a b for a ∈ N, b > 1 output COMPOSITE ii. Find the smallest r such that O r (n) > log 2 n iii. If 1 < (a, n) < n for some a ≤ r then output COMPOSITE iv. If n ≤ r output PRIME v. For a = 1 to ⌊ φ(n) log n⌋ do if (x + a) n = x n + a mod (x r − 1, n) output COMPOSITE vi. output PRIME A closer look at the algorithm reveals that a slight modification can be done in the step 2, step 3 and step 4 .
The following are the modifications: 2. Find the smallest r such that either (n, r) > 1 or (n, r) = 1 and O r (n) > log 2 n 3. if r ≥ n output PRIME 4. if (n, r) > 1 output COMPOSITE The advantage of doing the above mentioned modifications is that it reduces the computational time involved in finding an appropriate r, although the computational complexity of the whole algorithm remains unchanged. In fact, if (n, r) = 1 then it suffices to check for an r in the range 2 (log 2 n, log 5 n) such that O r (n) > log 2 n.

Proof of Correctness
In this section we present the proof of the algorithm through a serious of theorems and lemmas 3 . In order to prove that the algorithm is indeed correct we need to prove only one theorem.
Theorem: The algorithm returns PRIME if and only if the input n is prime.
Proof. In order to prove the above theorem we present the following lemmas.
Lemma 3.3.1: Given n is prime, the algorithm will return PRIME.
Proof. If n is prime then the return statements in step 1 and step 3 will not be evoked. Now, in the step 5 of the algorithm the equation would never turn out to be false since by lemma 3.1 (proved earlier) it is satisfied for all prime n. Therefore it will return PRIME.
Therefore having proved the above Lemma, the only thing that remains to be shown is the converse i.e. -if it returns PRIME then n is a prime number. To prove this we make use of the following lemmas. Our first objective is to show that there exists an r in a definite range which satisfies the condition that O r (n) > log 2 n. This is a crucial step since both the important steps 2 and 5 (important in terms of taking the maximum computational time) depend on this value of r.
Proof. For n=2, we can see that the smallest such r which satisfies O r (n) > log 2 n is r = 3. Therefore we need to see only for n > 2. Now, let us assume that there exists no such r which satisfies O r (n) > log 2 n in the given interval. That is assume that for all r ∈ (0, log 5 n], O r (n) ≤ log 2 n Next, consider Also since we have assumed that for all r ∈ (0, log 5 n], O r (n) ≤ log 2 n,therefore But, Also, we know that n log 4 n ≤ 2 log 5 n Therefore, combining all the above results we have which is a contradiction! This arises because of the fact that we assumed there exists no r ∈ (0, log 5 n] such that O r (n) > log 2 n. Hence we can conclude that there indeed exists at least one r ∈ (0, log 5 n] such that O r (n) > log 2 n.
Note 1: A closer examination using Wolfram Alpha reveals that the bound on r can be relaxed to r ≤ log 4.7 n.
Note 2: If (r, n) = 1 then we need to check for an r only in the range (log 2 n, log 5 n] since by Euler's Theorem we have O r (n) | φ(r) and therefore r ≥ O r (n) ≥ φ(r) > log 2 n Now, we know that O r (n) > 1. Therefore there must exist a prime p which divides n such that O r (p) > 1. Let us assume that p > r for, if it is otherwise then step 3 or step 4 of the algorithm will find that n is composite. Since, we assume that p > r therefore, we have (n, r) = 1 , (p, r) = 1 i.e. p, n ∈ Z * r .
So, having made the above observation we now go to step 5 of the algorithm where l = ⌊ φ(n) log n⌋ equations need to be verified. Let us assume that it does not output COMPOSITE in this step, so we have: (X + a) n = X n + a (mod X r − 1, n) for all a, 0 ≤ a ≤ l.
Now, since p | n we have: for all a, 0 ≤ a ≤ l. Also by Lemma 3.1 we know that for any prime p for all a, 0 ≤ a ≤ l. So from the above two equations we have: for all a, 0 ≤ a ≤ l.
Here, we define an idea called 'Introspective Numbers' as they call it.
So, from above we can see that both p and n p are introspective. In fact, this property can be generalized as a theorem.

Theorem 3.3.3: The set of introspective numbers is closed under multiplication
Proof. Let m 1 , m 2 be two introspective numbers introspective to a polynomial f (X). So we need to prove that m 1 · m 2 is also introspective. Since m 1 is introspective, we have: We also know that m 2 is introspective. Therefore, we replace X by X m 1 to have: Therefore from above we have: Similarly we can have one more theorem which states that: Proof. Let f (X), g(X) be the two polynomials introspective with respect to m. Therefore we have: Having proved the above two theorems, we now move to the what can be called as the main part of the proof. This involves constructing of two groups G 1 and G 2 . Now, construct a group G 1 of the residues of I modulo r. This is a subgroup of Z * r since (n, r) = 1 and (p, r) = 1. Let |G 1 | = t. Since the O r (n) > log 2 n therefore, t > log 2 n.
Before, we construct the second group we state a important theorem (without proof) 4 . Theorem 3.3.5: Consider the r th cyclotomic polynomial 5 Q r (X) over the finite field 6 F p . Q r (X) divides the polynomial X r − 1 into irreducible factors of degree > O r (p).
As a consequence of the above theorem if h(X) is one such irreducible factor then the degree of h(x) > 1 since the O r (p) > 1. Now, to construct the second group G 2 consider the residues of all the polynomials in P modulo p and h(X). This group G 2 will be generated by X, X + 1, X + 2, · · · , X + l in the field F = F p [X]/h(X).
After having constructed the two groups we have the following lemmas. Proof. Consider two polynomials f (X) and g(X) both in P of degree < t. First, we show that both f (X) and g(X) map differently in G 2 . For that, let us assume f (X) = g(X) in F and let m ∈ I. Since m is introspective to both f (X) and g(X), we have: has roots of the form X m and this is true for all m ∈ G 1 . Therefore we know that the polynomial Q(Y ) has |G 1 | = t distinct roots in F . But then, both f (Y ) and g(Y ) are of degree < t, which implies that it is impossible for Q(Y ) to have t distinct roots. This is contradiction and has arised since we assumed that f (X) = g(X) in F . Therefore, f (X) = g(X) in F . Now, l = ⌊ φ(n) log n⌋ < √ r log n < r (since we have assumed that (n, r) = 1) 7 and we also know that p > r. Therefore, the elements X, X + 1, X + 2, · · · , X + l are all distinct in F p . Also, since the degree of h(X) > 1 therefore X + a = 0 in F for any a ∈ [0, l]. This shows that there are at least l + 1 polynomials of degree one in G 2 . Hence, the number of polynomials with degree < t is: = no: of polynomials of the form (X) e 0 · (X + 1) e 1 · · · (X + l) e l with degree < t = no: of solutions of : e 0 + e 1 + e 2 + · · · + e l < t Therefore the number of elements in G 2 has to be greater than t+l t−1 . Or in other words | G 2 | ≥ t+l t−1 .
With a lower bound on the number of elements in |G 2 | we can now show that if n is not a power of a prime number p then we can arrive at an upper bound on the number of elements. This is illustrated in the following lemma: Proof. Consider a subset of the set of introspective numbers I say is not a power of prime p then the number of distinct elements in I * = ( √ t + 1) 2 > t. This implies that when the elements of I * are taken modulo r at least, two of them will be equivalent since, we know that the number of elements in |G 1 | = t. Now, let the two numbers in I * which are equivalent modulo r be m 1 , m 2 : m 1 > m 2 . So we have: If f (X) ∈ P then, since both m 1 , m 2 ∈ I, we have: Therefore from above we have: And this implies that all f (X) ∈ G 2 is a solution to the polynomial We also know that this polynomial can have a maximum of m 1 roots and the maximum value of m 1 is n Therefore from above we have | G 2 | ≥ n √ t . This implies that n is a power of prime p because otherwise from Lemma 3.3.7 we would have had | G 2 | ≤ n √ t . But then, if n was a prime power of p that would have been detected in the very first step. Therefore, the only possibility is n = p 1 which implies that n is a prime number and hence this proves the correctness of the AKS algorithm.

Chapter 4 Implementation
Having proved the correctness of the AKS algorithm in the previous chapter we now move on to the implementation of the algorithm. In this chapter we look at the various modules which are involved in the implementation of the algorithm and finally we present the algorithm which was implemented in SAGE (Software for Algebra and Geometry Experimentation). The implementation was done by defining a function AKS(n) which takes a number n as the input and outputs whether the number is prime or composite.

Testing for perfect-power
This part of the algorithm is used to check if the given number n is a perfect power i.e here we check if the number n can be written in the form a b .Now, if n = a b then we know that the maximum value of b is log n where log here refers to the base 2 (as has been the case throughout). Therefore the problem here reduces to probing whether an a exists such that a b = n for b ∈ [2, log n]. The algorithm for the same is given below:

Finding an appropriate r
Having checked whether the given number n is a perfect power or otherwise we now move on to the step 2 of the algorithm, which as mentioned earlier is one of the most important step of the AKS algorithm. The objective here is to find an appropriate r such that O r (n) > log 2 n. Now, in the correctness proof of the algorithm we found that such an r can be found in the range (0, log 5 n] so, using that we need find an r which satisfies the above condition. To do so, we test all r ∈ [2, log 5 n] to see if there is a k ∈ [1, log 2 n] such that n k = 1 mod(r). If there is no such k then that particular r is the appropriate r that we want. Given below is the algorithm for finding such an r.
i. for r = 2 to ⌊log 5 n⌋ + 1 ii. if for all k ∈ [1, log 2 n] n k = 1 (mod r) then output r iii. else continue till finding such an r

Checking l equations
Here we move on to the step 5 of the algorithm which basically checks l equations. Now, one reason for choosing SAGE to implement the algorithm was because SAGE basically has built-in libraries and routines which can form rings modulo n, form polynomial rings and perform quotienting over polynomial rings. The routines we used here are Integers(), PolynomialRing() and quotient(). Integers() is used to form the ring of integers modulo any n where n will be given as a parameter to it. The PolynomialRing() forms a polynomial ring over the ring say s, which will be given as a parameter to it and the quotient() is used for quotienting over polynomial rings.
Now putting together all the pieces we present the SAGE 1 code for the AKS algorithm: def AKS(n): c=1 k=0 for b in range(2,ceil(log(n,2))+1): y=(log(n,2)/b).n() c=(pow(2,y)).n(30) if (pow(floor(c),b)==n) : print 'Composite' print 'It is a perfect power. n =', n, '=',floor(c),'^', b return m=((log(n,2)))^5 r=2 while(r<=floor(m)): Having presented the implementation of the AKS algorithm in the previous chapter, we now present the results obtained on running the code. Here, in order to be sure that the implemented algorithm is correct we test the individual components and check if it gives the right results.

Perfect Power Checking
In order to prove that the algorithm given for perfect power checking is true, we present the table (5.1) below which tests this algorithm for certain values. The values are selected so that, it is tested for numbers with different number of digits. In the result column, a 0 implies that the entered number is not a perfect power while otherwise, it displays the perfect power of the given number such that n = a b .

Finding the appropriate r
The table below (5.2) shows the values of r for different values of n such that the O r (n) > log 2 n. The 'r' column gives the values of the smallest r which satisfies the above condition.

Testing AKS(n)
Finally, after having checked the correctness of perfect-power algorithm and the value of r for some values of n, here we see the output of AKS(n) for certain n. Table(5.3) below tabulates the results obtained for certain values of n and in this table the result column indicates whether the number n is PRIME or COMPOSITE.

Conclusions
The formulation of a Deterministic Polynomial Time Primality Testing Algorithm has certainly been a huge leap considering the fact that there where none until then and the AKS algorithm has certainly thrown us some light on one of the oldest problems confronting mathematics, which is to test whether a given number is prime or composite. But having said that, it is also to be reminded that the AKS algorithm though a remarkable theoretical result, is still nowhere near to being practical since we have better performing probabilistic algorithms (with very less margin for error). The very fact that the check for whether the number 9965468763136528274628451 is prime ( in Table 5.3 ) took as much as around 70 minutes shows how inefficient it is. And although, there has been considerable work undertaken to improve the algorithm, most of these have been based on results which haven't been proven yet.
Considering the situations where these primality testing algorithms are used, like in cryptography where they have to confront very large numbers, it is an absolute need of the hour to improve it so as to make it more practical and therefore, I certainly believe that there is still a lot of work to be done in this area.
Although I do feel that this project would have been better off if it had resulted in some contributions towards making the algorithm more practical, I certainly believe that I have been able to meet the modest target I had set (especially because of the insufficient mathematical background I possessed) -which was to basically study and have a good understanding of the deterministic primality testing. In addition, it has also given me an opportunity to understand some basic Number Theory and Abstract Algebra, most of which, were new to me, and appreciate some results which have huge significance in this and many other related areas. Also, an introduction into SAGE programing, I feel, was a definite positive considering how powerful the tool turned out to be, especially during the implementation phase of this project.