Portability | Good |
---|---|
Stability | experimental |
Maintainer | Vincent Hanquez <vincent@snarc.org> |
Safe Haskell | Safe-Infered |
Number.Prime
Description
- generatePrime :: CryptoRandomGen g => g -> Int -> Either GenError (Integer, g)
- generateSafePrime :: CryptoRandomGen g => g -> Int -> Either GenError (Integer, g)
- isProbablyPrime :: CryptoRandomGen g => g -> Integer -> Either GenError (Bool, g)
- findPrimeFrom :: CryptoRandomGen g => g -> Integer -> Either GenError (Integer, g)
- findPrimeFromWith :: CryptoRandomGen g => g -> (g -> Integer -> Either GenError (Bool, g)) -> Integer -> Either GenError (Integer, g)
- primalityTestNaive :: Integer -> Bool
- primalityTestMillerRabin :: CryptoRandomGen g => g -> Int -> Integer -> Either GenError (Bool, g)
- isCoprime :: Integer -> Integer -> Bool
Documentation
generatePrime :: CryptoRandomGen g => g -> Int -> Either GenError (Integer, g)Source
generate a prime number of the required bitsize
generateSafePrime :: CryptoRandomGen g => g -> Int -> Either GenError (Integer, g)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.
isProbablyPrime :: CryptoRandomGen g => g -> Integer -> Either GenError (Bool, g)Source
returns if the number is probably prime. first a list of small primes are implicitely tested for divisibility, then the Miller Rabin algorithm is used with an accuracy of 30 recursions
findPrimeFrom :: CryptoRandomGen g => g -> Integer -> Either GenError (Integer, g)Source
find a prime from a starting point with no specific property.
findPrimeFromWith :: CryptoRandomGen g => g -> (g -> Integer -> Either GenError (Bool, g)) -> Integer -> Either GenError (Integer, g)Source
find a prime from a starting point where the property hold.
primalityTestNaive :: Integer -> BoolSource
Test naively is integer is prime. while naive, we skip even number and stop iteration at i > sqrt(n)
primalityTestMillerRabin :: CryptoRandomGen g => g -> Int -> Integer -> Either GenError (Bool, g)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.