Math 626 -- Computer Projects

Here are some Maple worksheets to help you get started. Notice that there is a new item (2/19) for the probabilistic factoring algorithm.
 First Maple Worksheet Number theory and linear algebra. Second Maple Worksheet Primes and finite fields (skip the finite fields section). Simple text: For handling text within Maple. Text processing: For reading text from a file and writing to a file. Ngraphs For parsing a list of letters into a Vector of numbers. Matrices : For rewriting a Vector as a Matrix for use with an affine matrix cryptosystem. Probabilistic factoring: For use with Problem F, factoring by creating a square root of 1. Finite Fields: Constructing and doing arithmetic in finite fields.
Here's an html version of the finite fields worksheet.

Computer Projects

You should implement all of the following algorithms.
For the cryptosystems, try exchanging messages with another student.
Also, try attacking a cipher that another student sets up.

1. Euclidean algorithm
2. Affine cryptosystem
3. RSA cryptosystem
4. Discrete Log cryptosystems:
• Massey-Omura message transmission,
• El Gamal message transmission
• Diffie Hellman key exchange
5. Knapsack cryptosystem

The following are more complex algorithms: implement a simplified version of each, then add complexity to build up to the final algorithm. Try experimenting with varied parameters to see how the algorithm performs.

1. Miller-Rabin primality test,
2. Factor base algorithm,
3. The Silver-Pohlig-Hellman algorithm for computing discrete logs,
4. Index calculus for computing discrete logs.
For help with Maple, here are a few references:

Andre Heck, Intorduction to Maple, Springer, QA 155.7 E4 H43 1996.

R. Klima, N. Stigmon, E. Stitziger, Applications of Abstract Algebra with Maple, , CRC Press, QA 162 K65 2000.