-- | 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 :: Integer -> Integer -> Integer
neg !Integer
p !Integer
x = if Integer
x forall a. Eq a => a -> a -> Bool
== Integer
0 then Integer
x else (Integer
p forall a. Num a => a -> a -> a
- Integer
x)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    then let u' :: Integer
u'  = Integer
uforall a. Num a => a -> a -> a
-Integer
v
             x1' :: Integer
x1' = if Integer
x1 forall a. Ord a => a -> a -> Bool
>= Integer
x2 then Integer -> Integer
modp (Integer
x1forall a. Num a => a -> a -> a
-Integer
x2) else Integer -> Integer
modp (Integer
x1forall a. Num a => a -> a -> a
+Integer
pforall a. Num a => a -> a -> a
-Integer
x2)               
         in  Integer -> Integer -> Integer -> Integer -> Integer
go Integer
x1' Integer
x2  Integer
u' Integer
v 

    else let v' :: Integer
v'  = Integer
vforall a. Num a => a -> a -> a
-Integer
u
             x2' :: Integer
x2' = if Integer
x2 forall a. Ord a => a -> a -> Bool
>= Integer
x1 then Integer -> Integer
modp (Integer
x2forall a. Num a => a -> a -> a
-Integer
x1) else Integer -> Integer
modp (Integer
x2forall a. Num a => a -> a -> a
+Integer
pforall a. Num a => a -> a -> a
-Integer
x1)
         in  Integer -> Integer -> Integer -> Integer -> Integer
go Integer
x1  Integer
x2' Integer
u  Integer
v'

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