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

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

-- |A module defining the field Q of rationals and the small finite fields (Galois fields)
-- F2, F3, F4, F5, F7, F8, F9, F11, F13, F16, F17, F19, F23, F25.
--
-- Given a prime power q, Fq is the type representing elements of the field (eg @F4@),
-- fq is a list of the elements of the field, beginning 0,1,... (eg @f4@),
-- and for prime power fields, aq is a primitive element, which generates the multiplicative group (eg @a4@).
--
-- The design philosophy is that fq, the list of elements, represents the field.
-- Thus, many functions elsewhere in the library expect to take fq as an argument,
-- telling them which field to work over.
module Math.Core.Field where

import Data.Ratio
import Data.Bits
import Data.List as L

import Math.Core.Utils (FinSet, elts)

-- |Q is just the rationals, but with a better show function than the Prelude version
newtype Q = Q Rational deriving (Eq,Ord,Num,Fractional)

instance Show Q where
    show (Q x) | b == 1    = show a
               | otherwise = show a ++ "/" ++ show b
               where a = numerator x
                     b = denominator x


numeratorQ (Q x) = Data.Ratio.numerator x
denominatorQ (Q x) = Data.Ratio.denominator x


-- The following implementations of the prime fields are only slightly faster than the versions in Math.Algebra.Field.Base

-- |F2 is a type for the finite field with 2 elements
newtype F2 = F2 Int deriving (Eq,Ord)

instance Show F2 where
    show (F2 x) = show x

instance Num F2 where
    F2 x + F2 y = F2 $ (x+y) .&. 1 -- `mod` 2
    negate x = x
    F2 x * F2 y = F2 $ x*y
    fromInteger n = F2 $ fromInteger n `mod` 2
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F2 where
    recip (F2 0) = error "F2.recip 0"
    recip (F2 1) = F2 1
    fromRational _ = error "F2.fromRational: not well defined"

instance FinSet F2 where elts = f2

-- |f2 is a list of the elements of F2
f2 :: [F2]
f2 = map fromInteger [0..1] -- :: [F2]


-- |F3 is a type for the finite field with 3 elements
newtype F3 = F3 Int deriving (Eq,Ord)

instance Show F3 where
    show (F3 x) = show x

instance Num F3 where
    F3 x + F3 y = F3 $ (x+y) `mod` 3
    negate (F3 0) = F3 0
    negate (F3 x) = F3 $ 3 - x
    F3 x * F3 y = F3 $ (x*y) `mod` 3
    fromInteger n = F3 $ fromInteger n `mod` 3
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F3 where
    recip (F3 0) = error "F3.recip 0"
    recip (F3 x) = F3 x
    fromRational _ = error "F3.fromRational: not well defined"

instance FinSet F3 where elts = f3

-- |f3 is a list of the elements of F3
f3 :: [F3]
f3 = map fromInteger [0..2] -- :: [F3]


-- |F5 is a type for the finite field with 5 elements
newtype F5 = F5 Int deriving (Eq,Ord)

instance Show F5 where
    show (F5 x) = show x

instance Num F5 where
    F5 x + F5 y = F5 $ (x+y) `mod` 5
    negate (F5 0) = F5 0
    negate (F5 x) = F5 $ 5 - x
    F5 x * F5 y = F5 $ (x*y) `mod` 5
    fromInteger n = F5 $ fromInteger n `mod` 5
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F5 where
    recip (F5 0) = error "F5.recip 0"
    recip (F5 x) = F5 $ (x^3) `mod` 5
    fromRational _ = error "F5.fromRational: not well defined"

instance FinSet F5 where elts = f5

-- |f5 is a list of the elements of F5
f5 :: [F5]
f5 = map fromInteger [0..4]


-- |F7 is a type for the finite field with 7 elements
newtype F7 = F7 Int deriving (Eq,Ord)

instance Show F7 where
    show (F7 x) = show x

instance Num F7 where
    F7 x + F7 y = F7 $ (x+y) `mod` 7
    negate (F7 0) = F7 0
    negate (F7 x) = F7 $ 7 - x
    F7 x * F7 y = F7 $ (x*y) `mod` 7
    fromInteger n = F7 $ fromInteger n `mod` 7
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F7 where
    recip (F7 0) = error "F7.recip 0"
    recip (F7 x) = F7 $ (x^5) `mod` 7
    fromRational _ = error "F7.fromRational: not well defined"

instance FinSet F7 where elts = f7

-- |f7 is a list of the elements of F7
f7 :: [F7]
f7 = map fromInteger [0..6]


-- |F11 is a type for the finite field with 11 elements
newtype F11 = F11 Int deriving (Eq,Ord)

instance Show F11 where
    show (F11 x) = show x

instance Num F11 where
    F11 x + F11 y = F11 $ (x+y) `mod` 11
    negate (F11 0) = F11 0
    negate (F11 x) = F11 $ 11 - x
    F11 x * F11 y = F11 $ (x*y) `mod` 11
    fromInteger n = F11 $ fromInteger n `mod` 11
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F11 where
    recip (F11 0) = error "F11.recip 0"
    recip (F11 x) = F11 $ (x^9) `mod` 11
    fromRational _ = error "F11.fromRational: not well defined"

instance FinSet F11 where elts = f11

-- |f11 is a list of the elements of F11
f11 :: [F11]
f11 = map fromInteger [0..10]


-- |F13 is a type for the finite field with 13 elements
newtype F13 = F13 Int deriving (Eq,Ord)

instance Show F13 where
    show (F13 x) = show x

instance Num F13 where
    F13 x + F13 y = F13 $ (x+y) `mod` 13
    negate (F13 0) = F13 0
    negate (F13 x) = F13 $ 13 - x
    F13 x * F13 y = F13 $ (x*y) `mod` 13
    fromInteger n = F13 $ fromInteger n `mod` 13
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F13 where
    recip (F13 0) = error "F13.recip 0"
    recip (F13 x) = F13 $ (x5*x5*x) `mod` 13 where x5 = x^5 `mod` 13 -- 12^11 would overflow Int
    fromRational _ = error "F13.fromRational: not well defined"

instance FinSet F13 where elts = f13

-- |f13 is a list of the elements of F13
f13 :: [F13]
f13 = map fromInteger [0..12]


-- |F17 is a type for the finite field with 17 elements
newtype F17 = F17 Int deriving (Eq,Ord)

instance Show F17 where
    show (F17 x) = show x

instance Num F17 where
    F17 x + F17 y = F17 $ (x+y) `mod` 17
    negate (F17 0) = F17 0
    negate (F17 x) = F17 $ 17 - x
    F17 x * F17 y = F17 $ (x*y) `mod` 17
    fromInteger n = F17 $ fromInteger n `mod` 17
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F17 where
    recip (F17 0) = error "F17.recip 0"
    recip (F17 x) = F17 $ (x5^3) `mod` 17 where x5 = x^5 `mod` 17 -- 16^15 would overflow Int
    fromRational _ = error "F17.fromRational: not well defined"

instance FinSet F17 where elts = f17

-- |f17 is a list of the elements of F17
f17 :: [F17]
f17 = map fromInteger [0..16]


-- |F19 is a type for the finite field with 19 elements
newtype F19 = F19 Int deriving (Eq,Ord)

instance Show F19 where
    show (F19 x) = show x

instance Num F19 where
    F19 x + F19 y = F19 $ (x+y) `mod` 19
    negate (F19 0) = F19 0
    negate (F19 x) = F19 $ 19 - x
    F19 x * F19 y = F19 $ (x*y) `mod` 19
    fromInteger n = F19 $ fromInteger n `mod` 19
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F19 where
    recip (F19 0) = error "F17.recip 0"
    recip (F19 x) = F19 $ (x4^4*x) `mod` 19 where x4 = x^4 `mod` 19 -- 18^17 would overflow Int
    fromRational _ = error "F19.fromRational: not well defined"

instance FinSet F19 where elts = f19

-- |f19 is a list of the elements of F19
f19 :: [F19]
f19 = map fromInteger [0..18]


-- |F23 is a type for the finite field with 23 elements
newtype F23 = F23 Int deriving (Eq,Ord)

instance Show F23 where
    show (F23 x) = show x

instance Num F23 where
    F23 x + F23 y = F23 $ (x+y) `mod` 23
    negate (F23 0) = F23 0
    negate (F23 x) = F23 $ 23 - x
    F23 x * F23 y = F23 $ (x*y) `mod` 23
    fromInteger n = F23 $ fromInteger n `mod` 23
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F23 where
    recip (F23 0) = error "F23.recip 0"
    recip (F23 x) = F23 $ (x5^4*x) `mod` 23 where x5 = x^5 `mod` 23 -- 22^21 would overflow Int
    fromRational _ = error "F23.fromRational: not well defined"

instance FinSet F23 where elts = f23

-- |f23 is a list of the elements of F23
f23 :: [F23]
f23 = map fromInteger [0..22]


-- The following implementations of the prime power fields are significantly faster than the versions in Math.Algebra.Field.Extension

-- |F4 is a type for the finite field with 4 elements.
-- F4 is represented as the extension of F2 by an element a4 satisfying x^2+x+1 = 0
newtype F4 = F4 Int deriving (Eq,Ord)

instance Show F4 where
    show (F4 0x00) = "0"
    show (F4 0x01) = "1"
    show (F4 0x10) = "a4"
    show (F4 0x11) = "a4+1" -- == a4^2

-- |a4 is a primitive element for F4 as an extension over F2. a4 satisfies x^2+x+1 = 0.
a4 :: F4
a4 = F4 0x10

instance Num F4 where
    F4 x + F4 y = F4 $ (x+y) .&. 0x11
    negate x = x
    F4 x * F4 y = let z = x*y in
                  if z `testBit` 8
                  then F4 ((z + 0x11) .&. 0x11) -- this is replacing x^2 by x+1
                  else F4 z
    fromInteger n = F4 $ fromInteger n .&. 1
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F4 where
    recip (F4 0) = error "F4.recip 0"
    recip (F4 1) = F4 1
    recip (F4 x) = F4 (x `xor` 1)
    fromRational _ = error "F4.fromRational: not well defined"

instance FinSet F4 where elts = f4

-- |f4 is a list of the elements of F4
f4 :: [F4]
f4 = L.sort $ 0 : powers a4

powers x | x /= 0 = 1 : takeWhile (/=1) (iterate (*x) x)


-- |F8 is a type for the finite field with 8 elements.
-- F8 is represented as the extension of F2 by an element a8 satisfying x^3+x+1 = 0
newtype F8 = F8 Int deriving (Eq,Ord)

instance Show F8 where
    show (F8 0x0) = "0"
    show (F8 0x1) = "1"
    show (F8 0x10) = "a8"
    show (F8 0x11) = "a8+1"
    show (F8 0x100) = "a8^2"
    show (F8 0x101) = "a8^2+1"
    show (F8 0x110) = "a8^2+a8"
    show (F8 0x111) = "a8^2+a8+1"

-- |a8 is a primitive element for F8 as an extension over F2. a8 satisfies x^3+x+1 = 0.
a8 :: F8
a8 = F8 0x10

instance Num F8 where
    F8 x + F8 y = F8 $ (x+y) .&. 0x111
    negate x = x
    F8 x * F8 y = F8 $ ((z43 `shiftR` 8) + (z43 `shiftR` 12) + z) .&. 0x111
        where z = x*y; z43 = z .&. 0xff000; -- z210 = z .&. 0xfff
        -- Explanation: We are making the substitution x^3 = x+1, x^4 = x^2+x
    fromInteger n = F8 $ fromInteger n .&. 0x1
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F8 where
    recip (F8 0) = error "F8.recip 0"
    recip x = x^6
    fromRational _ = error "F8.fromRational: not well defined"

instance FinSet F8 where elts = f8

-- |f8 is a list of the elements of F8
f8 :: [F8]
f8 = L.sort $ 0 : powers a8


-- |F9 is a type for the finite field with 9 elements.
-- F9 is represented as the extension of F3 by an element a9 satisfying x^2+2x+2 = 0
newtype F9 = F9 Int deriving (Eq,Ord)

instance Show F9 where
    show (F9 0x00) = "0"
    show (F9 0x01) = "1"
    show (F9 0x02) = "2"
    show (F9 0x100) = "a9"
    show (F9 0x101) = "a9+1"
    show (F9 0x102) = "a9+2"
    show (F9 0x200) = "2a9"
    show (F9 0x201) = "2a9+1"
    show (F9 0x202) = "2a9+2"

-- |a9 is a primitive element for F9 as an extension over F3. a9 satisfies x^2+2x+2 = 0.
a9 :: F9
a9 = F9 0x100

instance Num F9 where
    F9 x + F9 y = F9 $ z1 + z0
        where z = x+y; z1 = (z .&. 0xff00) `rem` 0x300; z0 = (z .&. 0xff) `rem` 3
    negate (F9 x) = F9 $ z1 + z0
        where z = 0x303 - x; z1 = (z .&. 0xff00) `rem` 0x300; z0 = (z .&. 0xff) `rem` 3
    F9 x * F9 y = F9 $ ((z2 + z1) `rem` 0x300) + ((z2 + z0) `rem` 3)
        where z = x*y; z2 = z .&. 0xff0000; z1 = z .&. 0xff00; z0 = z .&. 0xff
        -- Explanation: We are substituting x^2 = x+1.
        -- We could do z2 `shiftR` 8 and z2 `shiftR` 16
        -- However, because 0x100 `mod` 3 == 1, we don't need to 
    fromInteger n = F9 $ fromInteger n `mod` 3
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F9 where
    recip (F9 0) = error "F9.recip 0"
    recip x = x^7
    fromRational _ = error "F9.fromRational: not well defined"

instance FinSet F9 where elts = f9

-- |f9 is a list of the elements of F9
f9 :: [F9]
f9 = L.sort $ 0 : powers a9


-- |F16 is a type for the finite field with 16 elements.
-- F16 is represented as the extension of F2 by an element a16 satisfying x^4+x+1 = 0
newtype F16 = F16 Int deriving (Eq,Ord)

instance Show F16 where
    show (F16 0x0) = "0"
    show (F16 0x1) = "1"
    show (F16 0x10) = "a16"
    show (F16 0x11) = "a16+1"
    show (F16 0x100) = "a16^2"
    show (F16 0x101) = "a16^2+1"
    show (F16 0x110) = "a16^2+a16"
    show (F16 0x111) = "a16^2+a16+1"
    show (F16 0x1000) = "a16^3"
    show (F16 0x1001) = "a16^3+1"
    show (F16 0x1010) = "a16^3+a16"
    show (F16 0x1011) = "a16^3+a16+1"
    show (F16 0x1100) = "a16^3+a16^2"
    show (F16 0x1101) = "a16^3+a16^2+1"
    show (F16 0x1110) = "a16^3+a16^2+a16"
    show (F16 0x1111) = "a16^3+a16^2+a16+1"

-- |a16 is a primitive element for F16 as an extension over F2. a16 satisfies x^4+x+1 = 0.
a16 :: F16
a16 = F16 0x10

instance Num F16 where
    F16 x + F16 y = F16 $ (x+y) .&. 0x1111
    negate x = x
    F16 x * F16 y = F16 $ ((z654 `shiftR` 12) + (z654 `shiftR` 16) + z) .&. 0x1111
        where z = x*y; z654 = z .&. 0xfff0000; -- z3210 = z .&. 0xffff
        -- Explanation: We are making the substitution x^4 = x+1 (and also for x^5, x^6)
    fromInteger n = F16 $ fromInteger n .&. 0x1
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F16 where
    recip (F16 0) = error "F16.recip 0"
    recip x = x^14
    fromRational _ = error "F16.fromRational: not well defined"

instance FinSet F16 where elts = f16

-- |f16 is a list of the elements of F16
f16 :: [F16]
f16 = L.sort $ 0 : powers a16


-- |F25 is a type for the finite field with 25 elements.
-- F25 is represented as the extension of F5 by an element a25 satisfying x^2+4x+2 = 0
newtype F25 = F25 Int deriving (Eq,Ord)

instance Show F25 where
    show (F25 x) = case ( (x .&. 0xff00) `shiftR` 8, x .&. 0xff ) of
                   (0,x0) -> show x0
                   (1,0) -> "a25"
                   (1,x0) -> "a25+" ++ show x0
                   (x1,0) -> show x1 ++ "a25"
                   (x1,x0) -> show x1 ++ "a25+" ++ show x0

-- |a25 is a primitive element for F25 as an extension over F5. a25 satisfies x^2+4x+2 = 0.
a25 :: F25
a25 = F25 0x100

instance Num F25 where
    F25 x + F25 y = F25 $ z1 + z0
        where z = x+y; z1 = (z .&. 0xff00) `rem` 0x500; z0 = (z .&. 0xff) `rem` 5
    negate (F25 x) = F25 $ z1 + z0
        where z = 0x505 - x; z1 = (z .&. 0xff00) `rem` 0x500; z0 = (z .&. 0xff) `rem` 5
    F25 x * F25 y = F25 $ ((z2 + z1) `rem` 0x500) + ((3*z2 + z0) `rem` 5)
        where z = x*y; z2 = z .&. 0xff0000; z1 = z .&. 0xff00; z0 = z .&. 0xff
        -- Explanation: We are substituting x^2 = x+3.
        -- We could do z2 `shiftR` 8 and z2 `shiftR` 16
        -- However, because 0x100 `mod` 5 == 1, we don't need to 
    fromInteger n = F25 $ fromInteger n `mod` 5
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F25 where
    recip (F25 0) = error "F25.recip 0"
    recip x = x^23
    fromRational _ = error "F25.fromRational: not well defined"

instance FinSet F25 where elts = f25

-- |f25 is a list of the elements of F25
f25 :: [F25]
f25 = L.sort $ 0 : powers a25