-- | Prime fields without type safety, naive implementation using 'Integer'-s
--
-- This module is considered internal.


{-# LANGUAGE BangPatterns, DataKinds, KindSignatures #-}
module Math.FiniteField.PrimeField.Generic.Raw where

--------------------------------------------------------------------------------

import Data.Bits
import GHC.TypeNats (Nat)

import Math.FiniteField.Primes
import Math.FiniteField.TypeLevel

--------------------------------------------------------------------------------

type P = Integer
type F = Integer

neg :: P -> F -> F
neg :: P -> P -> P
neg !P
p !P
x = if P
x P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0 then P
x else (P
p P -> P -> P
forall a. Num a => a -> a -> a
- P
x)

add :: P -> F -> F -> F
add :: P -> P -> P -> P
add !P
p !P
x !P
y = let a :: P
a = P
x P -> P -> P
forall a. Num a => a -> a -> a
+ P
y in if P
a P -> P -> Bool
forall a. Ord a => a -> a -> Bool
< P
p then P
a else (P
a P -> P -> P
forall a. Num a => a -> a -> a
- P
p)

sub :: P -> F -> F -> F
sub :: P -> P -> P -> P
sub !P
p !P
x !P
y = let a :: P
a = P
x P -> P -> P
forall a. Num a => a -> a -> a
- P
y in if P
a P -> P -> Bool
forall a. Ord a => a -> a -> Bool
>= P
0 then P
a else (P
a P -> P -> P
forall a. Num a => a -> a -> a
+ P
p)

mul :: P -> F -> F -> F
mul :: P -> P -> P -> P
mul !P
p !P
x !P
y = P -> P -> P
forall a. Integral a => a -> a -> a
mod (P
xP -> P -> P
forall a. Num a => a -> a -> a
*P
y) P
p

--------------------------------------------------------------------------------
-- * Nontrivial operations

pow :: P -> F -> Integer -> F
pow :: P -> P -> P -> P
pow P
p P
z P
e 
  | P
z P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0    = P
0
  | P
e P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0    = P
1
  | P
e P -> P -> Bool
forall a. Ord a => a -> a -> Bool
< P
0     = P -> P -> P -> P
pow P
p (P -> P -> P
inv P
p P
z) (P -> P
forall a. Num a => a -> a
negate P
e)
  | P
e P -> P -> Bool
forall a. Ord a => a -> a -> Bool
>= P
pm1  = P -> P -> P -> P
go P
1 P
z (P -> P -> P
forall a. Integral a => a -> a -> a
mod P
e P
pm1)
  | Bool
otherwise = P -> P -> P -> P
go P
1 P
z P
e
  where
    pm1 :: P
pm1 = P
p P -> P -> P
forall a. Num a => a -> a -> a
- P
1

    go :: F -> F -> Integer -> F
    go :: P -> P -> P -> P
go !P
acc !P
y !P
e = if P
e P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0 
      then P
acc
      else case (P
e P -> P -> P
forall a. Bits a => a -> a -> a
.&. P
1) of
        P
0 -> P -> P -> P -> P
go        P
acc    (P -> P -> P -> P
mul P
p P
y P
y) (P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
e Int
1)
        P
_ -> P -> P -> P -> P
go (P -> P -> P -> P
mul P
p P
acc P
y) (P -> P -> P -> P
mul P
p P
y P
y) (P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
e Int
1)

-- | Inversion (using Euclid's algorithm)
inv :: P -> F -> F
inv :: P -> P -> P
inv !P
p !P
a 
  | P
a P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0    = P
0
  | Bool
otherwise = (P -> P -> P -> P -> P -> P
euclid P
p P
1 P
0 P
a P
p) 

-- | Division via Euclid's algorithm
div :: P -> F -> F -> F
div :: P -> P -> P -> P
div !P
p !P
a !P
b
  | P
b P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0    = P
0
  | Bool
otherwise = (P -> P -> P -> P -> P -> P
euclid P
p P
a P
0 P
b P
p) 

-- | Division via multiplying by the inverse
div2 :: P -> F -> F -> F
div2 :: P -> P -> P -> P
div2 !P
p !P
a !P
b = P -> P -> P -> P
mul P
p P
a (P -> P -> P
inv P
p P
b)

--------------------------------------------------------------------------------
-- * Euclidean algorithm

-- | Extended binary Euclidean algorithm
euclid :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer 
euclid :: P -> P -> P -> P -> P -> P
euclid !P
p !P
x1 !P
x2 !P
u !P
v = P -> P -> P -> P -> P
go P
x1 P
x2 P
u P
v where

  halfp1 :: P
halfp1 = P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR (P
pP -> P -> P
forall a. Num a => a -> a -> a
+P
1) Int
1

  modp :: Integer -> Integer
  modp :: P -> P
modp P
n = P -> P -> P
forall a. Integral a => a -> a -> a
mod P
n P
p

  -- Inverse using the binary Euclidean algorithm 
  euclid :: Integer -> Integer
  euclid :: P -> P
euclid P
a 
    | P
a P -> P -> Bool
forall a. Eq a => a -> a -> Bool
== P
0     = P
0
    | Bool
otherwise  = P -> P -> P -> P -> P
go P
1 P
0 P
a P
p
  
  go :: Integer -> Integer -> Integer -> Integer -> Integer
  go :: P -> P -> P -> P -> P
go !P
x1 !P
x2 !P
u !P
v 
    | P
uP -> P -> Bool
forall a. Eq a => a -> a -> Bool
==P
1       = P
x1
    | P
vP -> P -> Bool
forall a. Eq a => a -> a -> Bool
==P
1       = P
x2
    | Bool
otherwise  = P -> P -> P -> P -> P
stepU P
x1 P
x2 P
u P
v

  stepU :: Integer -> Integer -> Integer -> Integer -> Integer
  stepU :: P -> P -> P -> P -> P
stepU !P
x1 !P
x2 !P
u !P
v = if P -> Bool
forall a. Integral a => a -> Bool
even P
u 
    then let u' :: P
u'  = P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
u Int
1
             x1' :: P
x1' = if P -> Bool
forall a. Integral a => a -> Bool
even P
x1 then P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
x1 Int
1 else P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
x1 Int
1 P -> P -> P
forall a. Num a => a -> a -> a
+ P
halfp1
         in  P -> P -> P -> P -> P
stepU P
x1' P
x2 P
u' P
v
    else     P -> P -> P -> P -> P
stepV P
x1  P
x2 P
u  P
v

  stepV :: Integer -> Integer -> Integer -> Integer -> Integer
  stepV :: P -> P -> P -> P -> P
stepV !P
x1 !P
x2 !P
u !P
v = if P -> Bool
forall a. Integral a => a -> Bool
even P
v
    then let v' :: P
v'  = P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
v Int
1
             x2' :: P
x2' = if P -> Bool
forall a. Integral a => a -> Bool
even P
x2 then P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
x2 Int
1 else P -> Int -> P
forall a. Bits a => a -> Int -> a
shiftR P
x2 Int
1 P -> P -> P
forall a. Num a => a -> a -> a
+ P
halfp1
         in  P -> P -> P -> P -> P
stepV P
x1 P
x2' P
u P
v' 
    else     P -> P -> P -> P -> P
final P
x1 P
x2  P
u P
v

  final :: Integer -> Integer -> Integer -> Integer -> Integer
  final :: P -> P -> P -> P -> P
final !P
x1 !P
x2 !P
u !P
v = if P
uP -> P -> Bool
forall a. Ord a => a -> a -> Bool
>=P
v

    then let u' :: P
u'  = P
uP -> P -> P
forall a. Num a => a -> a -> a
-P
v
             x1' :: P
x1' = if P
x1 P -> P -> Bool
forall a. Ord a => a -> a -> Bool
>= P
x2 then P -> P
modp (P
x1P -> P -> P
forall a. Num a => a -> a -> a
-P
x2) else P -> P
modp (P
x1P -> P -> P
forall a. Num a => a -> a -> a
+P
pP -> P -> P
forall a. Num a => a -> a -> a
-P
x2)               
         in  P -> P -> P -> P -> P
go P
x1' P
x2  P
u' P
v 

    else let v' :: P
v'  = P
vP -> P -> P
forall a. Num a => a -> a -> a
-P
u
             x2' :: P
x2' = if P
x2 P -> P -> Bool
forall a. Ord a => a -> a -> Bool
>= P
x1 then P -> P
modp (P
x2P -> P -> P
forall a. Num a => a -> a -> a
-P
x1) else P -> P
modp (P
x2P -> P -> P
forall a. Num a => a -> a -> a
+P
pP -> P -> P
forall a. Num a => a -> a -> a
-P
x1)
         in  P -> P -> P -> P -> P
go P
x1  P
x2' P
u  P
v'

--------------------------------------------------------------------------------