Abstract

Number theory is the branch of mathematics which is concerned with the properties of integers. For centuries, the great mathematical minds of the world such as Euclid, Euler, and Fermat have developed have developed and proved numerous theories and conjectures which have come to be the foundation of number theory. These theories and conjectures are often easily understood, even by individuals who are not mathematically minded, but are not so easily prooved. Likewise, problems involving number theory, which appear mathematically simple, can take a large amount of time to solve; computers can potentially spend hundreds of years determining the result to a number theory problem.

It is this property of time consuming computation that makes number theory the ideal language for cryptography. One key element in the relationship between number theory and cryptography is prime numbers. Ever since Euclid proved the infinitude of primes, there have been numerous algorithms developed to test the primality of a number; that is, to test whether a given integer is considered prime.

The most retarded method for testing primality is to divide a prime number, p, by every number between two and the square root of p. If any number between two and the square root of p divides p, then p is said to be composite, else it is prime. While effective, this type of primality testing is highly inefficient. A more efficient method for testing primality is with Fermat's Little Theorem. This theorem states, for any prime number p, and any number a relatively prime to p it can be said that a to the power of p-1 is congruent to 1 mod p. The inefficiency of this test lies in the fact that some composite numbers can also satisfy this lemma.

Manindra Agrawal, Neeraj Kayal and Nitin Saxena [AKS2002] released a paper describing a unconditional deterministic polynomial-time algorith for primality testing which sought to eliminate any difficulties associated with previous methods of primality testing. The method used for primality testing had remained elusive until Agrawal, Kayal and Saxena released their results. This project seeks to implement the ideas developed by Agrawal, Kayal and Saxena using Maple as a platform.

Algorithm

The algorithm was first described in a paper written by Agrawal, Neeraj and Saxena [AKS2002] in 2002. The paper describes the algorithm seen below and gives a mathematical proof for its validity.

The basic idea for the algorithm stems from a simple identity, an identity which has been used in other primality testing algorithms.The identity states, suppose that a is relatively prime to p. Then p is prime if and only if:

All primes, p satisfy the above Identity for a given a and r. The problem is that some composite numbers may also satisfy the identity. The algorithm chooses an r which would satisfy the above equation through the following portion of the algorithm.

This stage in the algorithm evaluates p to choose a suitable r. The prime number must be relatively prime to r. r must also be a prime number. If those two caveats are true, then the algorithm finds the largest prime factor of r-1 and calls it q.

The complete algorithm above returns a result of prime if and only if n is prime. The algorithm is comprised of two loops. As previously stated, the first loop tries to find a prime r such that r-1 has a large prime factor q where q is greater than or equal to 4 multipled by the log base 10 of n and the square root of r. Additionally, q must also divide the order of n mod r.

Demonstration

The first step in executing the algorithm is to erase Maple of any useless information which may be floating around in its memory. To do this, place the cursor anywhere in the RESTART code represented by the image seen below and hit Enter.

The second step in executing the algorithm is to execute the Maple program. Hitting Enter in the RESTART code should automatically bring the cursor to the PROGRAM section. If not, place the cursor anywhere in the code represented by the image seen below and hit Enter. Note that the PROGRAM section is actually larger than what is represented in the image below.

The second step in executing the algorithm is to execute the Maple program. Hitting Enter in the RESTART code should automatically bring the cursor to the PROGRAM section. If not, place the cursor anywhere in the code represented by the image seen below and hit Enter. Note that the PROGRAM section is actually larger than what is represented in the image below.

At this point there are two possible ways to run the program. The first way, shown below is to test an individual number for primality. This can be done by simply inserting a number into the parenthesis. For example, 'primality(11)' as shown below.

The second way to run the program is to test a range of numbers. This can be done by entering a finite range of numbers into the for loop. For example, 'for i from 10 to 1000. This will test all integers in this range and report back which numbers are prime.

Download the program in one of the following formats and try it out.

• Maple 9.0: primality.rar (~2.1mb) or primality.mw (~16mb).
• Maple 8.1 or ealier: primality.rar (~2.1mb) or primality.mws (~8mb).
• Presentation: presentation.ppt.

Program Limitations and Future Work

One major limitation on the program is the time it takes to execute. For smaller numbers the program can readily produce results. However, for larger numbers, the computation times grows rapidly since there are many more steps in the process for testing the primality of a large number

In the future, the program could be augmented to perform time calculations. Part of what Agrawal, Saxena and Kayal were trying to accompished was also time based.

References

Agrawal, M., Saxena, N. & Kayal, N. PRIMES in P August 6, 2002.

Last Updated: 11.22.04