Project description

Title: Find large prime numbers:

Many cryptographic systems, for example RSA, use prime numbers ("primtal", in Danish). For security, one requires that these primes be very large. A standard method of producing the primes required by these systems, is to randomly choose integers in a certain range (so that the numbers are large enough) until finding one which is prime. However, the security of many cryptographic systems relies on the assumption that it is hard to factor large numbers. Thus, one has the problem of determining if an integer is prime without being able to factor integers. This is actually quite possible. There are algorithms which do this in practice, though this is still an area of active research.

The algorithms which do this are based on an area of mathematics called number theory, which includes the study of prime numbers. Most of the algorithms are probabilistic, in the sense that they use a source of randomness and there is a small probability that the algorithm could make a mistake, answering that a number was prime when it was not.

This project is to investigate and compare algorithms for finding prime numbers, producing a report recommending which algorithm to use in an implementation of RSA. An introduction to some basic number theory and algebra will be included for the understanding of these algorithms. This project is appropriate for either computer science or math groups, or groups containing both types of students. Depending on the group, the project can involve more implementation and testing or more theory, but in all cases, an interest in the mathematics behind these algorithms is necessary.

Recommended minicourses:

Projektarbejde (LaTeX).

Brief summary of primality testing:

Eric W. Weisstein. "Primality Test." From MathWorld--A Wolfram Web Resource. Summary

IMADA HOME | SDU HOME | Previous page |
Last modified: Tue Mar 10 14:19:26 CET 2009 - Joan Boyar <joan@imada.sdu.dk>

Data protection at SDU ▪ Databeskyttelse på SDU