Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

Modular square roots.

- sqrtModP :: Integer -> Integer -> Maybe Integer
- sqrtModPList :: Integer -> Integer -> [Integer]
- sqrtModP' :: Integer -> Integer -> Integer
- tonelliShanks :: Integer -> Integer -> Integer
- sqrtModPP :: Integer -> (Integer, Int) -> Maybe Integer
- sqrtModPPList :: Integer -> (Integer, Int) -> [Integer]
- sqrtModF :: Integer -> [(Integer, Int)] -> Maybe Integer
- sqrtModFList :: Integer -> [(Integer, Int)] -> [Integer]

# Documentation

sqrtModP :: Integer -> Integer -> Maybe Integer Source #

`sqrtModP n prime`

calculates a modular square root of `n`

modulo `prime`

if that exists. The second argument *must* be a (positive) prime, otherwise
the computation may not terminate and if it does, may yield a wrong result.
The precondition is *not* checked.

If `prime`

is a prime and `n`

a quadratic residue modulo `prime`

, the result
is `Just r`

where `r^2 ≡ n (mod prime)`

, if `n`

is a quadratic nonresidue,
the result is `Nothing`

.

sqrtModPList :: Integer -> Integer -> [Integer] Source #

`sqrtModPList n prime`

computes the list of all square roots of `n`

modulo `prime`

. `prime`

*must* be a (positive) prime.
The precondition is *not* checked.

sqrtModP' :: Integer -> Integer -> Integer Source #

`sqrtModP' square prime`

finds a square root of `square`

modulo
prime. `prime`

*must* be a (positive) prime, and `square`

*must* be a positive
quadratic residue modulo `prime`

, i.e. `'jacobi square prime == 1`

.
The precondition is *not* checked.

tonelliShanks :: Integer -> Integer -> Integer Source #

`tonelliShanks square prime`

calculates a square root of `square`

modulo `prime`

, where `prime`

is a prime of the form `4*k + 1`

and
`square`

is a positive quadratic residue modulo `prime`

, using the
Tonelli-Shanks algorithm.
No checks on the input are performed.

sqrtModPP :: Integer -> (Integer, Int) -> Maybe Integer Source #

`sqrtModPP n (prime,expo)`

calculates a square root of `n`

modulo `prime^expo`

if one exists. `prime`

*must* be a
(positive) prime. `expo`

must be positive, `n`

must be coprime
to `prime`

sqrtModPPList :: Integer -> (Integer, Int) -> [Integer] Source #

`sqrtModPPList n (prime,expo)`

calculates the list of all
square roots of `n`

modulo `prime^expo`

. The same restriction
as in `sqrtModPP`

applies to the arguments.