-- 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 (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


-- PRIME FIELDS

-- extendedEuclid a b returns (u,v,d) such that u*a + v*b = d
extendedEuclid a b | a >= 0 && b >= 0 = extendedEuclid' a b [] where
    extendedEuclid' d 0 qs = let (u,v) = unwind 1 0 qs in (u,v,d)
    extendedEuclid' a b qs = let (q,r) = quotRem a b in extendedEuclid' b r (q:qs)
    unwind u v [] = (u,v)
    unwind u v (q:qs) = unwind v (u-v*q) qs


newtype Fp n = Fp Integer deriving (Eq,Ord)

instance Show (Fp n) where
    show (Fp x) = show x

instance IntegerAsType n => Num (Fp n) where
    Fp x + Fp y = Fp $ (x+y) `mod` p where p = value (undefined :: n)
    negate (Fp 0) = Fp 0
    negate (Fp x) = Fp $ p - x where p = value (undefined :: n)
    Fp x * Fp y = Fp $ (x*y) `mod` p where p = value (undefined :: n)
    fromInteger m = Fp $ m `mod` p where p = value (undefined :: n)
    abs _ = error "Prelude.Num.abs: inappropriate abstraction"
    signum _ = 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 0 = error "Fp.recip 0"
    recip (Fp x) = let (u,v,1) = extendedEuclid x p -- so ux+vp = 1. (We know the gcd is 1 as p prime)
                   in Fp $ u `mod` p
                   where p = value (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 _ = map fromInteger [0..p'-1] where p' = value (undefined :: p)
    basisFq _ = [fromInteger 1]

instance IntegerAsType p => FinSet (Fp p) where
    elts = map fromInteger [0..p'-1] where p' = value (undefined :: p)

primitiveElt fq = head [x | x <- tail fq, length (powers x) == q-1] where
    q = length fq

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


-- characteristic of a finite field
char fq = head [p | p <- [2..], length fq `mod` p == 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 = map 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 = map 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 = map 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 = map fromInteger [0..6] -- :: [F7]

type F11 = Fp T11
f11 = map fromInteger [0..10] :: [F11]

type F13 = Fp T13
f13 = map fromInteger [0..12] :: [F13]

type F17 = Fp T17
f17 = map fromInteger [0..16] :: [F17]

type F19 = Fp T19
f19 = map fromInteger [0..18] :: [F19]

type F23 = Fp T23
f23 = map fromInteger [0..22] :: [F23]

type F29 = Fp T29
f29 = map fromInteger [0..28] :: [F29]

type F31 = Fp T31
f31 = map fromInteger [0..30] :: [F31]

type F37 = Fp T37
f37 = map fromInteger [0..36] :: [F37]

type F41 = Fp T41
f41 = map fromInteger [0..40] :: [F41]

type F43 = Fp T43
f43 = map fromInteger [0..42] :: [F43]

type F47 = Fp T47
f47 = map fromInteger [0..46] :: [F47]

type F53 = Fp T53
f53 = map fromInteger [0..52] :: [F53]

type F59 = Fp T59
f59 = map fromInteger [0..58] :: [F59]

type F61 = Fp T61
f61 = map fromInteger [0..60] :: [F61]

type F67 = Fp T67
f67 = map fromInteger [0..66] :: [F67]

type F71 = Fp T71
f71 = map fromInteger [0..70] :: [F71]

type F73 = Fp T73
f73 = map fromInteger [0..72] :: [F73]

type F79 = Fp T79
f79 = map fromInteger [0..78] :: [F79]

type F83 = Fp T83
f83 = map fromInteger [0..82] :: [F83]

type F89 = Fp T89
f89 = map fromInteger [0..88] :: [F89]

type F97 = Fp T97
f97 = map fromInteger [0..96] :: [F97]