AKS Primality Testing For Large Numbers

Efficient Implementation of the Agrawal-Kayal-Saxena Primality Testing Algorithm For Very Large Numbers

An Efficient Implementation of the Agrawal-Kayal-Saxena Primality Testing Algorithm For Very Large Numbers. A report on the research conducted to implement and compare the Agrawal-Kayal-Saxena polinomial time deterministic primality testing algorithm also known as cycotomic AKS Test.

AKS Algorithm screenshot

Downloads

Full Report: Implementation of AKS Algorithm.pdf Download
Appendix A: NaiveMethods.jar Download
Appendix B: FermatTest.jar Download
Appendix C: AKSTestLarge.jar Download
Implementation of the Polynomial Time Deterministic Primality Testing Algorithm: AKS.pdf Download

Author Info

Author: Abdullah Al Zakir Hossain
Email: aazhbd@yahoo.com
Phone: +49 176 91442004

Abstract

Prime numbers are particularly important in ensuring security in networks and in computer systems. While prime numbers are easily defined, discovering a polynomial time deterministic algorithm for it required thousands of years of research. There are many ways of determining whether a number is a prime or not. In cryptography and in many other problems choosing very large prime numbers is important. It is known that factoring of an integer is NP-complete. But status of primality testing was unresolved till 2002 when Manindra Agrawal, Nitin Saxena and Neeraj Kayal found an elegant deterministic polynomial time algorithm. Along with the slower algorithms a faster solution like the Fermat’s little test was devised and implemented. But all of them were probabilistic although quite efficient in practice. In this research the main emphasis has been given on the work of Agrawal et al [], and the algorithm has been implemented to compare its performance with already known algorithms.

Usage

The implementations and details can be downloaded and used from here. The implementations are the commonly used naive methods, fermat's little test both in randomized and non-randomized codes and finally the AKS implementation. The AKS alogrithm implementation is done with polynomial time algorithm in every steps and implemented for large numbers that has hundreds of digits.

Table of Contents

Chapter 1: Introduction
1.1 Preliminaries
1.2 Prospect and Importance
1.3 Objective of the Thesis
1.4 Organization of the Thesis
1.5 Remarks on Notations
1.6 Literature Survey
1.7 Choice of Programming Language: Java
Chapter 2: Naive Methods for Primality Testing
2.1 A Simple Test
2.2 A Common Primality Testing Algorithm
2.3 Sieve of Eratosthenes
2.4 An Implementation of the discussed algorithms
Chapter 3: A Probabilistic Algorithm: Fermat’s Little Test
3.1 Overview of the Fermat’s Theorem
3.1.1 Related Theorems
3.1.2 Proof of Fermat’s Theorem
3.1.3 The Idea & algorithm
3.2 Carmichael & Pseudo-prime Numbers
3.3 Korslet’s Criterion
3.4 An Implementation of the discussed algorithms
Chapter 4: Deterministic Polynomial Time AKS Algorithm
4.1 Primes is in P: AKS Algorithm
4.2 Overview
4.2.1 Idea
4.2.2 The Algorithm
4.2.3 Notations & Preliminaries
4.3 Theorems and Correctness of the algorithm
4.4 Complexity Analysis
4.5 An Implementation of the discussed algorithms
Chapter 5: Conclusion
Appendix A
Appendix B
Appendix C
Bibliographical Notes