Math.NumberTheory.Moduli.Sqrt

Modular square roots.

New interface

sqrtsMod :: SFactors Integer m -> Mod m -> [Mod m]

List all modular square roots.

>>> :set -XDataKinds
>>> sqrtsMod sfactors (1 :: Mod 60)
[(1 `modulo` 60),(49 `modulo` 60),(41 `modulo` 60),(29 `modulo` 60),(31 `modulo` 60),(19 `modulo` 60),(11 `modulo` 60),(59 `modulo` 60)]

sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer]

List all square roots modulo a number, the factorisation of which is passed as a second argument.

>>> sqrtsModFactorisation 1 (factorise 60)
[1,49,41,29,31,19,11,59]

sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer]

List all square roots modulo the power of a prime.

>>> import Data.Maybe
>>> import Math.NumberTheory.Primes
>>> sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2
[4,5]
>>> sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3
[3,12,21,24,6,15]

sqrtsModPrime :: Integer -> Prime Integer -> [Integer]

List all square roots by prime modulo.

>>> import Data.Maybe
>>> import Math.NumberTheory.Primes
>>> sqrtsModPrime 1 (fromJust (isPrime 5))
[1,4]
>>> sqrtsModPrime 0 (fromJust (isPrime 5))
[0]
>>> sqrtsModPrime 2 (fromJust (isPrime 5))
[]