License | BSD-style |
---|---|

Maintainer | Vincent Hanquez <vincent@snarc.org> |

Stability | experimental |

Portability | Good |

Safe Haskell | None |

Language | Haskell2010 |

## Synopsis

- generatePrime :: MonadRandom m => Int -> m Integer
- generateSafePrime :: MonadRandom m => Int -> m Integer
- isProbablyPrime :: Integer -> Bool
- findPrimeFrom :: Integer -> Integer
- findPrimeFromWith :: (Integer -> Bool) -> Integer -> Integer
- primalityTestMillerRabin :: Int -> Integer -> Bool
- primalityTestNaive :: Integer -> Bool
- primalityTestFermat :: Int -> Integer -> Integer -> Bool
- isCoprime :: Integer -> Integer -> Bool

# Documentation

generatePrime :: MonadRandom m => Int -> m Integer Source #

Generate a prime number of the required bitsize (i.e. in the range [2^(b-1)+2^(b-2), 2^b)).

May throw a `CryptoError_PrimeSizeInvalid`

if the requested size is less
than 5 bits, as the smallest prime meeting these conditions is 29.
This function requires that the two highest bits are set, so that when
multiplied with another prime to create a key, it is guaranteed to be of
the proper size.

generateSafePrime :: MonadRandom m => Int -> m Integer Source #

Generate a prime number of the form 2p+1 where p is also prime. it is also knowed as a Sophie Germaine prime or safe prime.

The number of safe prime is significantly smaller to the number of prime, as such it shouldn't be used if this number is supposed to be kept safe.

May throw a `CryptoError_PrimeSizeInvalid`

if the requested size is less than
6 bits, as the smallest safe prime with the two highest bits set is 59.

isProbablyPrime :: Integer -> Bool Source #

Returns if the number is probably prime. First a list of small primes are implicitely tested for divisibility, then a fermat primality test is used with arbitrary numbers and then the Miller Rabin algorithm is used with an accuracy of 30 recursions.

findPrimeFrom :: Integer -> Integer Source #

Find a prime from a starting point with no specific property.

findPrimeFromWith :: (Integer -> Bool) -> Integer -> Integer Source #

Find a prime from a starting point where the property hold.

primalityTestMillerRabin :: Int -> Integer -> Bool Source #

Miller Rabin algorithm return if the number is probably prime or composite. the tries parameter is the number of recursion, that determines the accuracy of the test.

primalityTestNaive :: Integer -> Bool Source #

Test naively is integer is prime. while naive, we skip even number and stop iteration at i > sqrt(n)