Sale!
Placeholder

The PRIME Problem

10,000 3,000

Topic Description

Summary
The problem of trying to determine if a given number is prime is an ancient problem, which
has riddled some of the world’s greatest minds for centuries. This problem has been
investigated since the days of the famous mathematicians Euclid (ca. 325 – ca.270) and
Eratosthenes (ca. 248 – ca. 192) due to the fundamental importance of prime numbers in
number theory. But it is only up until recent that computer scientists have also developed a
fascination with prime number due to their use in encryption algorithms such as the RSA
algorithm. All such systems presently use probalistic primality-testing algorithms. This is
mainly due to the fact that these probalistic primality-testing algorithms can be used to obtain
extremely fast and confident results. No deterministic primality-testing algorithm could have
possibly been used in such systems since until recent, no one had been able to devise an
unconditional deterministic primality-testing algorithm, which had polynomial time
complexity.
It was on 6thAugust 2002 that three Indian computer scientists M. Agrawal, N. Kayal, and N.
Saxana, distributed a report “PRIMES is in P” which contained a deterministic polynomial
time primality-testing algorithm. This algorithm was an incredible discovery, and it solved an
age-old question of whether primality could be tested in polynomial time.
This report contains details of how this project has successfully dealt with the problem of
understanding and evaluating this deterministic primality-testing algorithm as well as
determining any possible outcomes of the algorithm in the field of cryptography. The project
has also examined other primality-testing algorithms and techniques and has explored the
computational issues associated with these problems, and also with the factorisation problem
which is another problem faced by computer scientists, which if solved would have an
tremendous immediate impact in the field of cryptography. The report also contains a
description of possible future work and enhancements that could be made to this area of
research.

Table of Contents
Chapter 1
1.1 Introduction to the problem……………………………………………………………..…1
1.2 Statement of the Problem……………………………………………………………….…2
1.3 Objectives…………………………………………………………………………………. 2
1.4 Minimum requirements…………………………………………………………………… 3
1.5 Possible enhancements…………………………………………………………………. …3
1.6 Relevance to degree program………………………………………………………………3
1.7 Solution to the problem……………………………………………………………………3
Chapter 2
2.1 Summary of press coverage of the AKS algorithm.……………………………………….6
Chapter 3
Basic principles
3.1 Number Theory. …………………………………………………………………………..8
3.2 Group and Field Theory…………………………………………………………………..12
3.2 Time Complexity Theory…………………………………………………………………13
3.3 Other Important Definitions…………………………………………………………… …13
Chapter 4
The AKS algorithm
4.1 Basis of the AKS algorithm………………………………………………………………16
4.2 Proof of Correctness………………………………………………………………………17
4.3 Time Complexity Analysis……………………………………………………………….21
Chapter 5
Sieve of Eratosthenes
5.1 Introduction…………… ……………………………………………………………… ..23
5.2 Experimental Analysis……………………………………………………………………23
Chapter 6
Miller-Rabin algorithm
6.1 Introduction…………… …………………………………………………………………25
6.2 Experimental Analysis……………………………………………………………………26
Chapter 7
7.1 The impact of the AKS algorithm in the field of cryptography.…………………………28
Chapter 8
Brief description and investigation of the factorisation problem. ……………………………29
iv
Chapter 9
9.1 Conclusion. …………………………………………………………………………… …30
9.2 Future Work………………………………………………………………………………30
Appendix A
Personal Reflection……………………………………………………………………………31
Appendix B
1.1 Sieve of Eratosthenes Experimental Analysis Results……………………………………32
1.2 Miller-Rabin Experimental Analysis Results…………….………………………………35
REFERENCES………………………………………………………………………………

PROJECT SAMPLE/DEPARTMENTS

REVIEW OUR SERVICES

SEE FAQ