Algebra.Algorithms.PrimeTest

Documentation

repeatedSquare :: Multiplicative r => r -> Natural -> r

Calculates n-th power efficiently, using repeated square method.

modPow :: (Integral a, Euclidean r) => r -> r -> a -> r

modPow x m p efficiently calculates x ^ p `mod' m.

fermatTest :: MonadRandom m => Integer -> m PrimeResult

Fermat-test for pseudo-primeness.

isPseudoPrime :: MonadRandom m => Integer -> m (Either Integer Bool)

isPseudoPrime n tests if the given integer n is pseudo prime. It returns Left p if p < n divides n, Right True if n is pseudo-prime, Right False if it is not pseudo-prime but no clue can be found.