** **

__Programming Language__ :

C on Unix OR

JAVA under Windows NT (write an applet so that it works on web pages)

** **

__Libraries :__

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

** **

__Input/Output__ :

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.

**Rabin-Milller 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 + 2^{b}m

1. Choose a random number, *a*, such that *a* is less than
*p*.

2. Set *j *= 0, and set *z* = *a ^{m}* mod

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*
= *z*^{2 }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
prime.

__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.**

- Proofs that these algorithms work
- Number of iterations required
- Generating a Strong Primes/Why they are necessary
- Proving that a number was generated at random
- Comparison of speed at various algorithms for various key sizes

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.

- Grantham-Frobenius Method can be done in addition to two algorithms if time allows.
- C with GNU Multiple Precision Arithmetic Library 2.0.2 will be used as first approach; however, if time allows, attempt to write it in JAVA will be explored.