{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveDataTypeable #-}
module Crypto.Number.ModArithmetic
(
expSafe
, expFast
, inverse
, inverseCoprimes
, jacobi
) where
import Control.Exception (throw, Exception)
import Crypto.Number.Basic
import Crypto.Number.Compat
data CoprimesAssertionError = CoprimesAssertionError
deriving (Int -> CoprimesAssertionError -> ShowS
[CoprimesAssertionError] -> ShowS
CoprimesAssertionError -> String
(Int -> CoprimesAssertionError -> ShowS)
-> (CoprimesAssertionError -> String)
-> ([CoprimesAssertionError] -> ShowS)
-> Show CoprimesAssertionError
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [CoprimesAssertionError] -> ShowS
$cshowList :: [CoprimesAssertionError] -> ShowS
show :: CoprimesAssertionError -> String
$cshow :: CoprimesAssertionError -> String
showsPrec :: Int -> CoprimesAssertionError -> ShowS
$cshowsPrec :: Int -> CoprimesAssertionError -> ShowS
Show)
instance Exception CoprimesAssertionError
expSafe :: Integer
-> Integer
-> Integer
-> Integer
expSafe :: Integer -> Integer -> Integer -> Integer
expSafe Integer
b Integer
e Integer
m
| Integer -> Bool
forall a. Integral a => a -> Bool
odd Integer
m = Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModSecInteger Integer
b Integer
e Integer
m GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported`
(Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModInteger Integer
b Integer
e Integer
m GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported`
Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m)
| Bool
otherwise = Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModInteger Integer
b Integer
e Integer
m GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported`
Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m
expFast :: Integer
-> Integer
-> Integer
-> Integer
expFast :: Integer -> Integer -> Integer -> Integer
expFast Integer
b Integer
e Integer
m = Integer -> Integer -> Integer -> GmpSupported Integer
gmpPowModInteger Integer
b Integer
e Integer
m GmpSupported Integer -> Integer -> Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m
exponentiation :: Integer -> Integer -> Integer -> Integer
exponentiation :: Integer -> Integer -> Integer -> Integer
exponentiation Integer
b Integer
e Integer
m
| Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
b
| Integer
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Integer
1
| Integer
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
| Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
e = let p :: Integer
p = (Integer -> Integer -> Integer -> Integer
exponentiation Integer
b (Integer
e Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
2) Integer
m) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
in (Integer
pInteger -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^(Integer
2::Integer)) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
| Bool
otherwise = (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer -> Integer -> Integer -> Integer
exponentiation Integer
b (Integer
eInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
1) Integer
m) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m
inverse :: Integer -> Integer -> Maybe Integer
inverse :: Integer -> Integer -> Maybe Integer
inverse Integer
g Integer
m = Integer -> Integer -> GmpSupported (Maybe Integer)
gmpInverse Integer
g Integer
m GmpSupported (Maybe Integer) -> Maybe Integer -> Maybe Integer
forall a. GmpSupported a -> a -> a
`onGmpUnsupported` Maybe Integer
v
where
v :: Maybe Integer
v
| Integer
d Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
1 = Maybe Integer
forall a. Maybe a
Nothing
| Bool
otherwise = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer
x Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
m)
(Integer
x,Integer
_,Integer
d) = Integer -> Integer -> (Integer, Integer, Integer)
gcde Integer
g Integer
m
inverseCoprimes :: Integer -> Integer -> Integer
inverseCoprimes :: Integer -> Integer -> Integer
inverseCoprimes Integer
g Integer
m =
case Integer -> Integer -> Maybe Integer
inverse Integer
g Integer
m of
Maybe Integer
Nothing -> CoprimesAssertionError -> Integer
forall a e. Exception e => e -> a
throw CoprimesAssertionError
CoprimesAssertionError
Just Integer
i -> Integer
i
jacobi :: Integer -> Integer -> Maybe Integer
jacobi :: Integer -> Integer -> Maybe Integer
jacobi Integer
a Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
3 Bool -> Bool -> Bool
|| Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
n = Maybe Integer
forall a. Maybe a
Nothing
| Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
|| Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
a
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
a = Integer -> Integer -> Maybe Integer
jacobi (Integer
a Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n) Integer
n
| Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 =
let b :: Integer
b = if Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then Integer
1 else -Integer
1
in (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
b) (Integer -> Integer -> Maybe Integer
jacobi (-Integer
a) Integer
n)
| Bool
otherwise =
let (Int
e, Integer
a1) = Integer -> (Int, Integer)
asPowerOf2AndOdd Integer
a
nMod8 :: Integer
nMod8 = Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
8
nMod4 :: Integer
nMod4 = Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4
a1Mod4 :: Integer
a1Mod4 = Integer
a1 Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
4
s' :: Integer
s' = if Int -> Bool
forall a. Integral a => a -> Bool
even Int
e Bool -> Bool -> Bool
|| Integer
nMod8 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 Bool -> Bool -> Bool
|| Integer
nMod8 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
7 then Integer
1 else -Integer
1
s :: Integer
s = if Integer
nMod4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
3 Bool -> Bool -> Bool
&& Integer
a1Mod4 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
3 then -Integer
s' else Integer
s'
n1 :: Integer
n1 = Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
a1
in if Integer
a1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
s
else (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
s) (Integer -> Integer -> Maybe Integer
jacobi Integer
n1 Integer
a1)