Trial Divison:

Fermat Test:

This is the supposed "Socat prime"


How Many MR witnesses does a given integer have?

Generating a large prime:
Here we select a random odd integer of size k and use MR test to check for primality. In practice it is good to look for small prime factors using trial division. This implementation does not do this.

The prime number theorem can be used to estimate the probability that a random kbit integer is prime as:

Fermat Factoring:

Fermat factoring works well when n = ab is a product with a ~ b. We can generate some such examples

Unfortunately, the difference between 2 random kbit primes is usually around O(2^k)

A MR witness that is not a Fermat witness allows us to factor n. These are however, are usually not very common. An exception to this is Carmichael Numbers.

Fermat Factoring when a multiple of phi(n) is known:


Largest known prime:





