Programming Language :
C on Unix OR
JAVA under Windows NT (write an applet so that it works on web pages)
The GNU Multiple Precision Arithmetic Library Edition 2.0.2
JDK1.1.6 : http://java.sun.com/products/jdk/1.1/docs/api/java.math.BigInteger.html
This program takes key length as an input and outputs two prime numbers.
Description of the function performed by the program(s), including any specific references to standard :
Creating a pair of corresponding public and private keys for the RSA cryptosystem requires generation of two very large prime numbers. The minimum length of these primes used in today's RSA implementations is 256 bits, which corresponds to numbers in the range 10^75. Due to the fast progress in factorization algorithms used to break RSA, it is currently recommended to use 384, 512, or even 1024-bit primes. This program utilizes Rabin-Miller algorithm to produce two prime numbers of length k bits where k is specified by the user. In addition, we compare it with Lucas- Lehmer Test.
Choose a random number, p, to test. Calculate b, where b is the number of times 2 divides p-1. Then calculate m, such that p = 1 + 2bm
1. Choose a random number, a, such that a is less than p.
2. Set j = 0, and set z = am mod p.
3. If z = 1, or if z = p – 1, then p passes the test and may be prime.
4. If j > 0 and z = 1, then p is not prime.
5. Set j = j +1. If j < b and z = z2 mod p-1 != p-1 go back to step 4. If z = p – 1, then p passes the test and may be prime.
6. If j = b and z = p –1, then p is not
Testing functionality and Performance :
Functionality and performance is defined by "speed" of the algorithm and probability of error. We calculate probability of error for algorithm implemented in function and measure the time to produce large prime numbers of length k bits.
Plan of experiements to be performed using the program(s) :
find large prime numbers of length k bits, and measure the performance(time). Try to optimize the program
Following will be also discussed on paper.
March 25 : Initial algorithm implementations. Initial proofs why these algorithms work
April 8 : Refinement.(for any bugs) Measure performance. Generating Strong Primes/Background
April 22 : Further refinement(try to make the code more efficient), Proving that a number was generated at random.
A list of possible areas, where the specification can change depending on the progress of the project.