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