Safe Haskell	Safe-Inferred
Language	GHC2021

Math.Modulus.Sqrt

Synopsis

legendreSymbol :: Int -> Int -> Int
sqrtMod :: Int -> Int -> [Int]
cipolla :: Int -> Int -> Int

Documentation

legendreSymbol :: Int -> Int -> Int Source #

Legendre symbol (Euler's criterion)

p is odd prime

sqrtMod :: Int -> Int -> [Int] Source #

x^2 = a (mod p) p is prime

>>> sqrtMod 2 1000000007
[59713600,940286407]
>>> sqrtMod 3 1000000007
[82062379,917937628]
>>> sqrtMod 4 1000000007
[2,1000000005]
>>> sqrtMod 5 1000000007
[]

cipolla :: Int -> Int -> Int Source #

cipolla a p ^ 2 = a (mod p) p is odd prime, (a | p) = 1

>>> cipolla 9 998244353
3
>>> cipolla 9 1000000007
1000000004