Safe Haskell	None
Language	Haskell2010

Algebra.Arithmetic

Synopsis

repeatedSquare :: Multiplicative r => r -> Natural -> r
modPow :: (Integral a, Euclidean r) => r -> r -> a -> r
fermatTest :: MonadRandom m => Integer -> m PrimeResult
isPseudoPrime :: MonadRandom m => Integer -> m (Either Integer Bool)

Documentation

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

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

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

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

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

Fermat-test for pseudo-primeness.

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

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.