-- Copyright (c) David Amos, 2008. All rights reserved.


{-# LANGUAGE GeneralizedNewtypeDeriving, ScopedTypeVariables #-}

module Math.Algebra.Field.Base where

import Data.Ratio
import Math.Common.IntegerAsType
import Math.Core.Utils

-- RATIONALS


-- |Q is just the rationals, but with a better show function than the Prelude version

newtype Q = Q Rational deriving (Q -> Q -> Bool
(Q -> Q -> Bool) -> (Q -> Q -> Bool) -> Eq Q
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Q -> Q -> Bool
$c/= :: Q -> Q -> Bool
== :: Q -> Q -> Bool
$c== :: Q -> Q -> Bool
Eq,Eq Q
Eq Q =>
(Q -> Q -> Ordering)
-> (Q -> Q -> Bool)
-> (Q -> Q -> Bool)
-> (Q -> Q -> Bool)
-> (Q -> Q -> Bool)
-> (Q -> Q -> Q)
-> (Q -> Q -> Q)
-> Ord Q
Q -> Q -> Bool
Q -> Q -> Ordering
Q -> Q -> Q
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: Q -> Q -> Q
$cmin :: Q -> Q -> Q
max :: Q -> Q -> Q
$cmax :: Q -> Q -> Q
>= :: Q -> Q -> Bool
$c>= :: Q -> Q -> Bool
> :: Q -> Q -> Bool
$c> :: Q -> Q -> Bool
<= :: Q -> Q -> Bool
$c<= :: Q -> Q -> Bool
< :: Q -> Q -> Bool
$c< :: Q -> Q -> Bool
compare :: Q -> Q -> Ordering
$ccompare :: Q -> Q -> Ordering
$cp1Ord :: Eq Q
Ord,Integer -> Q
Q -> Q
Q -> Q -> Q
(Q -> Q -> Q)
-> (Q -> Q -> Q)
-> (Q -> Q -> Q)
-> (Q -> Q)
-> (Q -> Q)
-> (Q -> Q)
-> (Integer -> Q)
-> Num Q
forall a.
(a -> a -> a)
-> (a -> a -> a)
-> (a -> a -> a)
-> (a -> a)
-> (a -> a)
-> (a -> a)
-> (Integer -> a)
-> Num a
fromInteger :: Integer -> Q
$cfromInteger :: Integer -> Q
signum :: Q -> Q
$csignum :: Q -> Q
abs :: Q -> Q
$cabs :: Q -> Q
negate :: Q -> Q
$cnegate :: Q -> Q
* :: Q -> Q -> Q
$c* :: Q -> Q -> Q
- :: Q -> Q -> Q
$c- :: Q -> Q -> Q
+ :: Q -> Q -> Q
$c+ :: Q -> Q -> Q
Num,Num Q
Num Q =>
(Q -> Q -> Q) -> (Q -> Q) -> (Rational -> Q) -> Fractional Q
Rational -> Q
Q -> Q
Q -> Q -> Q
forall a.
Num a =>
(a -> a -> a) -> (a -> a) -> (Rational -> a) -> Fractional a
fromRational :: Rational -> Q
$cfromRational :: Rational -> Q
recip :: Q -> Q
$crecip :: Q -> Q
/ :: Q -> Q -> Q
$c/ :: Q -> Q -> Q
$cp1Fractional :: Num Q
Fractional)

instance Show Q where
    show :: Q -> String
show (Q x :: Rational
x) | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1    = Integer -> String
forall a. Show a => a -> String
show Integer
a
               | Bool
otherwise = Integer -> String
forall a. Show a => a -> String
show Integer
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ "/" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
b
               where a :: Integer
a = Rational -> Integer
forall a. Ratio a -> a
numerator Rational
x
                     b :: Integer
b = Rational -> Integer
forall a. Ratio a -> a
denominator Rational
x


numeratorQ :: Q -> Integer
numeratorQ (Q x :: Rational
x) = Rational -> Integer
forall a. Ratio a -> a
Data.Ratio.numerator Rational
x
denominatorQ :: Q -> Integer
denominatorQ (Q x :: Rational
x) = Rational -> Integer
forall a. Ratio a -> a
Data.Ratio.denominator Rational
x


-- PRIME FIELDS


-- extendedEuclid a b returns (u,v,d) such that u*a + v*b = d

extendedEuclid :: b -> b -> (b, b, b)
extendedEuclid a :: b
a b :: b
b | b
a b -> b -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 Bool -> Bool -> Bool
&& b
b b -> b -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 = b -> b -> [b] -> (b, b, b)
forall b. Integral b => b -> b -> [b] -> (b, b, b)
extendedEuclid' b
a b
b [] where
    extendedEuclid' :: b -> b -> [b] -> (b, b, b)
extendedEuclid' d :: b
d 0 qs :: [b]
qs = let (u :: b
u,v :: b
v) = b -> b -> [b] -> (b, b)
forall t. Num t => t -> t -> [t] -> (t, t)
unwind 1 0 [b]
qs in (b
u,b
v,b
d)
    extendedEuclid' a :: b
a b :: b
b qs :: [b]
qs = let (q :: b
q,r :: b
r) = b -> b -> (b, b)
forall a. Integral a => a -> a -> (a, a)
quotRem b
a b
b in b -> b -> [b] -> (b, b, b)
extendedEuclid' b
b b
r (b
qb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
qs)
    unwind :: t -> t -> [t] -> (t, t)
unwind u :: t
u v :: t
v [] = (t
u,t
v)
    unwind u :: t
u v :: t
v (q :: t
q:qs :: [t]
qs) = t -> t -> [t] -> (t, t)
unwind t
v (t
ut -> t -> t
forall a. Num a => a -> a -> a
-t
vt -> t -> t
forall a. Num a => a -> a -> a
*t
q) [t]
qs


newtype Fp n = Fp Integer deriving (Fp n -> Fp n -> Bool
(Fp n -> Fp n -> Bool) -> (Fp n -> Fp n -> Bool) -> Eq (Fp n)
forall n. Fp n -> Fp n -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Fp n -> Fp n -> Bool
$c/= :: forall n. Fp n -> Fp n -> Bool
== :: Fp n -> Fp n -> Bool
$c== :: forall n. Fp n -> Fp n -> Bool
Eq,Eq (Fp n)
Eq (Fp n) =>
(Fp n -> Fp n -> Ordering)
-> (Fp n -> Fp n -> Bool)
-> (Fp n -> Fp n -> Bool)
-> (Fp n -> Fp n -> Bool)
-> (Fp n -> Fp n -> Bool)
-> (Fp n -> Fp n -> Fp n)
-> (Fp n -> Fp n -> Fp n)
-> Ord (Fp n)
Fp n -> Fp n -> Bool
Fp n -> Fp n -> Ordering
Fp n -> Fp n -> Fp n
forall n. Eq (Fp n)
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall n. Fp n -> Fp n -> Bool
forall n. Fp n -> Fp n -> Ordering
forall n. Fp n -> Fp n -> Fp n
min :: Fp n -> Fp n -> Fp n
$cmin :: forall n. Fp n -> Fp n -> Fp n
max :: Fp n -> Fp n -> Fp n
$cmax :: forall n. Fp n -> Fp n -> Fp n
>= :: Fp n -> Fp n -> Bool
$c>= :: forall n. Fp n -> Fp n -> Bool
> :: Fp n -> Fp n -> Bool
$c> :: forall n. Fp n -> Fp n -> Bool
<= :: Fp n -> Fp n -> Bool
$c<= :: forall n. Fp n -> Fp n -> Bool
< :: Fp n -> Fp n -> Bool
$c< :: forall n. Fp n -> Fp n -> Bool
compare :: Fp n -> Fp n -> Ordering
$ccompare :: forall n. Fp n -> Fp n -> Ordering
$cp1Ord :: forall n. Eq (Fp n)
Ord)

instance Show (Fp n) where
    show :: Fp n -> String
show (Fp x :: Integer
x) = Integer -> String
forall a. Show a => a -> String
show Integer
x

instance IntegerAsType n => Num (Fp n) where
    Fp x :: Integer
x + :: Fp n -> Fp n -> Fp n
+ Fp y :: Integer
y = Integer -> Fp n
forall n. Integer -> Fp n
Fp (Integer -> Fp n) -> Integer -> Fp n
forall a b. (a -> b) -> a -> b
$ (Integer
xInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
y) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p where p :: Integer
p = n -> Integer
forall a. IntegerAsType a => a -> Integer
value (n
forall a. HasCallStack => a
undefined :: n)
    negate :: Fp n -> Fp n
negate (Fp 0) = Integer -> Fp n
forall n. Integer -> Fp n
Fp 0
    negate (Fp x :: Integer
x) = Integer -> Fp n
forall n. Integer -> Fp n
Fp (Integer -> Fp n) -> Integer -> Fp n
forall a b. (a -> b) -> a -> b
$ Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
x where p :: Integer
p = n -> Integer
forall a. IntegerAsType a => a -> Integer
value (n
forall a. HasCallStack => a
undefined :: n)
    Fp x :: Integer
x * :: Fp n -> Fp n -> Fp n
* Fp y :: Integer
y = Integer -> Fp n
forall n. Integer -> Fp n
Fp (Integer -> Fp n) -> Integer -> Fp n
forall a b. (a -> b) -> a -> b
$ (Integer
xInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
y) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p where p :: Integer
p = n -> Integer
forall a. IntegerAsType a => a -> Integer
value (n
forall a. HasCallStack => a
undefined :: n)
    fromInteger :: Integer -> Fp n
fromInteger m :: Integer
m = Integer -> Fp n
forall n. Integer -> Fp n
Fp (Integer -> Fp n) -> Integer -> Fp n
forall a b. (a -> b) -> a -> b
$ Integer
m Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p where p :: Integer
p = n -> Integer
forall a. IntegerAsType a => a -> Integer
value (n
forall a. HasCallStack => a
undefined :: n)
    abs :: Fp n -> Fp n
abs _ = String -> Fp n
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: Fp n -> Fp n
signum _ = String -> Fp n
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

-- n must be prime - could perhaps use a type to guarantee this

instance IntegerAsType n => Fractional (Fp n) where
    recip :: Fp n -> Fp n
recip 0 = String -> Fp n
forall a. HasCallStack => String -> a
error "Fp.recip 0"
    recip (Fp x :: Integer
x) = let (u :: Integer
u,v :: Integer
v,1) = Integer -> Integer -> (Integer, Integer, Integer)
forall b. Integral b => b -> b -> (b, b, b)
extendedEuclid Integer
x Integer
p -- so ux+vp = 1. (We know the gcd is 1 as p prime)

                   in Integer -> Fp n
forall n. Integer -> Fp n
Fp (Integer -> Fp n) -> Integer -> Fp n
forall a b. (a -> b) -> a -> b
$ Integer
u Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
p
                   where p :: Integer
p = n -> Integer
forall a. IntegerAsType a => a -> Integer
value (n
forall a. HasCallStack => a
undefined :: n)

-- Not sure if Eq fq is required, need to try with ghc >= 7.4.1

class (Eq fq, Fractional fq) => FiniteField fq where
    eltsFq :: fq -> [fq]  -- return all elts of the field

    basisFq :: fq -> [fq] -- return an additive basis for the field (as Z-module)


instance IntegerAsType p => FiniteField (Fp p) where
    eltsFq :: Fp p -> [Fp p]
eltsFq _ = (Integer -> Fp p) -> [Integer] -> [Fp p]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> Fp p
forall a. Num a => Integer -> a
fromInteger [0..Integer
p'Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-1] where p' :: Integer
p' = p -> Integer
forall a. IntegerAsType a => a -> Integer
value (p
forall a. HasCallStack => a
undefined :: p)
    basisFq :: Fp p -> [Fp p]
basisFq _ = [Integer -> Fp p
forall a. Num a => Integer -> a
fromInteger 1]

instance IntegerAsType p => FinSet (Fp p) where
    elts :: [Fp p]
elts = (Integer -> Fp p) -> [Integer] -> [Fp p]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> Fp p
forall a. Num a => Integer -> a
fromInteger [0..Integer
p'Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-1] where p' :: Integer
p' = p -> Integer
forall a. IntegerAsType a => a -> Integer
value (p
forall a. HasCallStack => a
undefined :: p)

primitiveElt :: [a] -> a
primitiveElt fq :: [a]
fq = [a] -> a
forall a. [a] -> a
head [a
x | a
x <- [a] -> [a]
forall a. [a] -> [a]
tail [a]
fq, [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (a -> [a]
forall a. (Eq a, Num a) => a -> [a]
powers a
x) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
qInt -> Int -> Int
forall a. Num a => a -> a -> a
-1] where
    q :: Int
q = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
fq

powers :: a -> [a]
powers x :: a
x | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = 1 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/=1) ((a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate (a -> a -> a
forall a. Num a => a -> a -> a
*a
x) a
x)


-- characteristic of a finite field

char :: t a -> Int
char fq :: t a
fq = [Int] -> Int
forall a. [a] -> a
head [Int
p | Int
p <- [2..], t a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length t a
fq Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0]


-- |F2 is a type for the finite field with 2 elements

type F2 = Fp T2

-- |f2 lists the elements of F2

f2 :: [F2]
f2 :: [F2]
f2 = (Integer -> F2) -> [Integer] -> [F2]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F2
forall a. Num a => Integer -> a
fromInteger [0..1] -- :: [F2]


-- |F3 is a type for the finite field with 3 elements

type F3 = Fp T3

-- |f3 lists the elements of F3

f3 :: [F3]
f3 :: [F3]
f3 = (Integer -> F3) -> [Integer] -> [F3]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F3
forall a. Num a => Integer -> a
fromInteger [0..2] -- :: [F3]


-- |F5 is a type for the finite field with 5 elements

type F5 = Fp T5

-- |f5 lists the elements of F5

f5 :: [F5]
f5 :: [F5]
f5 = (Integer -> F5) -> [Integer] -> [F5]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F5
forall a. Num a => Integer -> a
fromInteger [0..4] -- :: [F5]


-- |F7 is a type for the finite field with 7 elements

type F7 = Fp T7

-- |f7 lists the elements of F7

f7 :: [F7]
f7 :: [F7]
f7 = (Integer -> F7) -> [Integer] -> [F7]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F7
forall a. Num a => Integer -> a
fromInteger [0..6] -- :: [F7]


type F11 = Fp T11
f11 :: [F11]
f11 = (Integer -> F11) -> [Integer] -> [F11]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F11
forall a. Num a => Integer -> a
fromInteger [0..10] :: [F11]

type F13 = Fp T13
f13 :: [F13]
f13 = (Integer -> F13) -> [Integer] -> [F13]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F13
forall a. Num a => Integer -> a
fromInteger [0..12] :: [F13]

type F17 = Fp T17
f17 :: [F17]
f17 = (Integer -> F17) -> [Integer] -> [F17]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F17
forall a. Num a => Integer -> a
fromInteger [0..16] :: [F17]

type F19 = Fp T19
f19 :: [F19]
f19 = (Integer -> F19) -> [Integer] -> [F19]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F19
forall a. Num a => Integer -> a
fromInteger [0..18] :: [F19]

type F23 = Fp T23
f23 :: [F23]
f23 = (Integer -> F23) -> [Integer] -> [F23]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F23
forall a. Num a => Integer -> a
fromInteger [0..22] :: [F23]

type F29 = Fp T29
f29 :: [F29]
f29 = (Integer -> F29) -> [Integer] -> [F29]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F29
forall a. Num a => Integer -> a
fromInteger [0..28] :: [F29]

type F31 = Fp T31
f31 :: [F31]
f31 = (Integer -> F31) -> [Integer] -> [F31]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F31
forall a. Num a => Integer -> a
fromInteger [0..30] :: [F31]

type F37 = Fp T37
f37 :: [F37]
f37 = (Integer -> F37) -> [Integer] -> [F37]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F37
forall a. Num a => Integer -> a
fromInteger [0..36] :: [F37]

type F41 = Fp T41
f41 :: [F41]
f41 = (Integer -> F41) -> [Integer] -> [F41]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F41
forall a. Num a => Integer -> a
fromInteger [0..40] :: [F41]

type F43 = Fp T43
f43 :: [F43]
f43 = (Integer -> F43) -> [Integer] -> [F43]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F43
forall a. Num a => Integer -> a
fromInteger [0..42] :: [F43]

type F47 = Fp T47
f47 :: [F47]
f47 = (Integer -> F47) -> [Integer] -> [F47]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F47
forall a. Num a => Integer -> a
fromInteger [0..46] :: [F47]

type F53 = Fp T53
f53 :: [F53]
f53 = (Integer -> F53) -> [Integer] -> [F53]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F53
forall a. Num a => Integer -> a
fromInteger [0..52] :: [F53]

type F59 = Fp T59
f59 :: [F59]
f59 = (Integer -> F59) -> [Integer] -> [F59]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F59
forall a. Num a => Integer -> a
fromInteger [0..58] :: [F59]

type F61 = Fp T61
f61 :: [F61]
f61 = (Integer -> F61) -> [Integer] -> [F61]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F61
forall a. Num a => Integer -> a
fromInteger [0..60] :: [F61]

type F67 = Fp T67
f67 :: [F67]
f67 = (Integer -> F67) -> [Integer] -> [F67]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F67
forall a. Num a => Integer -> a
fromInteger [0..66] :: [F67]

type F71 = Fp T71
f71 :: [F71]
f71 = (Integer -> F71) -> [Integer] -> [F71]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F71
forall a. Num a => Integer -> a
fromInteger [0..70] :: [F71]

type F73 = Fp T73
f73 :: [F73]
f73 = (Integer -> F73) -> [Integer] -> [F73]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F73
forall a. Num a => Integer -> a
fromInteger [0..72] :: [F73]

type F79 = Fp T79
f79 :: [F79]
f79 = (Integer -> F79) -> [Integer] -> [F79]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F79
forall a. Num a => Integer -> a
fromInteger [0..78] :: [F79]

type F83 = Fp T83
f83 :: [F83]
f83 = (Integer -> F83) -> [Integer] -> [F83]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F83
forall a. Num a => Integer -> a
fromInteger [0..82] :: [F83]

type F89 = Fp T89
f89 :: [F89]
f89 = (Integer -> F89) -> [Integer] -> [F89]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F89
forall a. Num a => Integer -> a
fromInteger [0..88] :: [F89]

type F97 = Fp T97
f97 :: [F97]
f97 = (Integer -> F97) -> [Integer] -> [F97]
forall a b. (a -> b) -> [a] -> [b]
map Integer -> F97
forall a. Num a => Integer -> a
fromInteger [0..96] :: [F97]