Random Prime Generator

Hi folks,

yesterday I published a random number generator which is realized by the algorithm of Blum-Blum-Shub. Today, I added a random prime generator to the publications section.

Primes are applied in several routines in information technology, such as public-key cryptography, which makes use of the difficulty of factoring large numbers into their prime factors. Searching for big primes, often using distributed computing, has stimulated studying special types of primes, chiefly Mersenne primes whose primality is comparably quick to decide. As of 2009, the largest known prime has about 12 million decimal digits. To create such large primes it is not possible to find pseudo primes by multiplication of two other primes. Therefore, algorithms have to be used. My algorithm produces a sum of a random integer within a certain range and a pre-calculated number resulting out of the size the prime should be. To verify primalty of the produced number the Rabin-Miller-Test has been implemented.

The Miller–Rabin primality test or Rabin–Miller primality test is a primality test, an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version, due to Gary L. Miller, is deterministic, but the determinism relies on the unproven generalized Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm. This algorithm is implemented in the Mathematica notebook provided in my publications section.

For more questions regarding the algorithm please feel free to leave me comments.