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


-- 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 (F2 -> F2 -> Bool
(F2 -> F2 -> Bool) -> (F2 -> F2 -> Bool) -> Eq F2
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F2 -> F2 -> Bool
$c/= :: F2 -> F2 -> Bool
== :: F2 -> F2 -> Bool
$c== :: F2 -> F2 -> Bool
Eq,Eq F2
Eq F2 =>
(F2 -> F2 -> Ordering)
-> (F2 -> F2 -> Bool)
-> (F2 -> F2 -> Bool)
-> (F2 -> F2 -> Bool)
-> (F2 -> F2 -> Bool)
-> (F2 -> F2 -> F2)
-> (F2 -> F2 -> F2)
-> Ord F2
F2 -> F2 -> Bool
F2 -> F2 -> Ordering
F2 -> F2 -> F2
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 :: F2 -> F2 -> F2
$cmin :: F2 -> F2 -> F2
max :: F2 -> F2 -> F2
$cmax :: F2 -> F2 -> F2
>= :: F2 -> F2 -> Bool
$c>= :: F2 -> F2 -> Bool
> :: F2 -> F2 -> Bool
$c> :: F2 -> F2 -> Bool
<= :: F2 -> F2 -> Bool
$c<= :: F2 -> F2 -> Bool
< :: F2 -> F2 -> Bool
$c< :: F2 -> F2 -> Bool
compare :: F2 -> F2 -> Ordering
$ccompare :: F2 -> F2 -> Ordering
$cp1Ord :: Eq F2
Ord)

instance Show F2 where
    show :: F2 -> String
show (F2 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F2 where
    F2 x :: Int
x + :: F2 -> F2 -> F2
+ F2 y :: Int
y = Int -> F2
F2 (Int -> F2) -> Int -> F2
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 1 -- `mod` 2
    negate :: F2 -> F2
negate x :: F2
x = F2
x
    F2 x :: Int
x * :: F2 -> F2 -> F2
* F2 y :: Int
y = Int -> F2
F2 (Int -> F2) -> Int -> F2
forall a b. (a -> b) -> a -> b
$ Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y
    fromInteger :: Integer -> F2
fromInteger n :: Integer
n = Int -> F2
F2 (Int -> F2) -> Int -> F2
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 2
    abs :: F2 -> F2
abs _ = String -> F2
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F2 -> F2
signum _ = String -> F2
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F2 where
    recip :: F2 -> F2
recip (F2 0) = String -> F2
forall a. HasCallStack => String -> a
error "F2.recip 0"
    recip (F2 1) = Int -> F2
F2 1
    fromRational :: Rational -> F2
fromRational _ = String -> F2
forall a. HasCallStack => String -> a
error "F2.fromRational: not well defined"

instance FinSet F2 where elts :: [F2]
elts = [F2]
f2

-- |f2 is a list of 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
newtype F3 = F3 Int deriving (F3 -> F3 -> Bool
(F3 -> F3 -> Bool) -> (F3 -> F3 -> Bool) -> Eq F3
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F3 -> F3 -> Bool
$c/= :: F3 -> F3 -> Bool
== :: F3 -> F3 -> Bool
$c== :: F3 -> F3 -> Bool
Eq,Eq F3
Eq F3 =>
(F3 -> F3 -> Ordering)
-> (F3 -> F3 -> Bool)
-> (F3 -> F3 -> Bool)
-> (F3 -> F3 -> Bool)
-> (F3 -> F3 -> Bool)
-> (F3 -> F3 -> F3)
-> (F3 -> F3 -> F3)
-> Ord F3
F3 -> F3 -> Bool
F3 -> F3 -> Ordering
F3 -> F3 -> F3
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 :: F3 -> F3 -> F3
$cmin :: F3 -> F3 -> F3
max :: F3 -> F3 -> F3
$cmax :: F3 -> F3 -> F3
>= :: F3 -> F3 -> Bool
$c>= :: F3 -> F3 -> Bool
> :: F3 -> F3 -> Bool
$c> :: F3 -> F3 -> Bool
<= :: F3 -> F3 -> Bool
$c<= :: F3 -> F3 -> Bool
< :: F3 -> F3 -> Bool
$c< :: F3 -> F3 -> Bool
compare :: F3 -> F3 -> Ordering
$ccompare :: F3 -> F3 -> Ordering
$cp1Ord :: Eq F3
Ord)

instance Show F3 where
    show :: F3 -> String
show (F3 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F3 where
    F3 x :: Int
x + :: F3 -> F3 -> F3
+ F3 y :: Int
y = Int -> F3
F3 (Int -> F3) -> Int -> F3
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 3
    negate :: F3 -> F3
negate (F3 0) = Int -> F3
F3 0
    negate (F3 x :: Int
x) = Int -> F3
F3 (Int -> F3) -> Int -> F3
forall a b. (a -> b) -> a -> b
$ 3 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F3 x :: Int
x * :: F3 -> F3 -> F3
* F3 y :: Int
y = Int -> F3
F3 (Int -> F3) -> Int -> F3
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 3
    fromInteger :: Integer -> F3
fromInteger n :: Integer
n = Int -> F3
F3 (Int -> F3) -> Int -> F3
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 3
    abs :: F3 -> F3
abs _ = String -> F3
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F3 -> F3
signum _ = String -> F3
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F3 where
    recip :: F3 -> F3
recip (F3 0) = String -> F3
forall a. HasCallStack => String -> a
error "F3.recip 0"
    recip (F3 x :: Int
x) = Int -> F3
F3 Int
x
    fromRational :: Rational -> F3
fromRational _ = String -> F3
forall a. HasCallStack => String -> a
error "F3.fromRational: not well defined"

instance FinSet F3 where elts :: [F3]
elts = [F3]
f3

-- |f3 is a list of 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
newtype F5 = F5 Int deriving (F5 -> F5 -> Bool
(F5 -> F5 -> Bool) -> (F5 -> F5 -> Bool) -> Eq F5
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F5 -> F5 -> Bool
$c/= :: F5 -> F5 -> Bool
== :: F5 -> F5 -> Bool
$c== :: F5 -> F5 -> Bool
Eq,Eq F5
Eq F5 =>
(F5 -> F5 -> Ordering)
-> (F5 -> F5 -> Bool)
-> (F5 -> F5 -> Bool)
-> (F5 -> F5 -> Bool)
-> (F5 -> F5 -> Bool)
-> (F5 -> F5 -> F5)
-> (F5 -> F5 -> F5)
-> Ord F5
F5 -> F5 -> Bool
F5 -> F5 -> Ordering
F5 -> F5 -> F5
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 :: F5 -> F5 -> F5
$cmin :: F5 -> F5 -> F5
max :: F5 -> F5 -> F5
$cmax :: F5 -> F5 -> F5
>= :: F5 -> F5 -> Bool
$c>= :: F5 -> F5 -> Bool
> :: F5 -> F5 -> Bool
$c> :: F5 -> F5 -> Bool
<= :: F5 -> F5 -> Bool
$c<= :: F5 -> F5 -> Bool
< :: F5 -> F5 -> Bool
$c< :: F5 -> F5 -> Bool
compare :: F5 -> F5 -> Ordering
$ccompare :: F5 -> F5 -> Ordering
$cp1Ord :: Eq F5
Ord)

instance Show F5 where
    show :: F5 -> String
show (F5 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F5 where
    F5 x :: Int
x + :: F5 -> F5 -> F5
+ F5 y :: Int
y = Int -> F5
F5 (Int -> F5) -> Int -> F5
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 5
    negate :: F5 -> F5
negate (F5 0) = Int -> F5
F5 0
    negate (F5 x :: Int
x) = Int -> F5
F5 (Int -> F5) -> Int -> F5
forall a b. (a -> b) -> a -> b
$ 5 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F5 x :: Int
x * :: F5 -> F5 -> F5
* F5 y :: Int
y = Int -> F5
F5 (Int -> F5) -> Int -> F5
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 5
    fromInteger :: Integer -> F5
fromInteger n :: Integer
n = Int -> F5
F5 (Int -> F5) -> Int -> F5
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 5
    abs :: F5 -> F5
abs _ = String -> F5
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F5 -> F5
signum _ = String -> F5
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F5 where
    recip :: F5 -> F5
recip (F5 0) = String -> F5
forall a. HasCallStack => String -> a
error "F5.recip 0"
    recip (F5 x :: Int
x) = Int -> F5
F5 (Int -> F5) -> Int -> F5
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^3) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 5
    fromRational :: Rational -> F5
fromRational _ = String -> F5
forall a. HasCallStack => String -> a
error "F5.fromRational: not well defined"

instance FinSet F5 where elts :: [F5]
elts = [F5]
f5

-- |f5 is a list of 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]


-- |F7 is a type for the finite field with 7 elements
newtype F7 = F7 Int deriving (F7 -> F7 -> Bool
(F7 -> F7 -> Bool) -> (F7 -> F7 -> Bool) -> Eq F7
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F7 -> F7 -> Bool
$c/= :: F7 -> F7 -> Bool
== :: F7 -> F7 -> Bool
$c== :: F7 -> F7 -> Bool
Eq,Eq F7
Eq F7 =>
(F7 -> F7 -> Ordering)
-> (F7 -> F7 -> Bool)
-> (F7 -> F7 -> Bool)
-> (F7 -> F7 -> Bool)
-> (F7 -> F7 -> Bool)
-> (F7 -> F7 -> F7)
-> (F7 -> F7 -> F7)
-> Ord F7
F7 -> F7 -> Bool
F7 -> F7 -> Ordering
F7 -> F7 -> F7
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 :: F7 -> F7 -> F7
$cmin :: F7 -> F7 -> F7
max :: F7 -> F7 -> F7
$cmax :: F7 -> F7 -> F7
>= :: F7 -> F7 -> Bool
$c>= :: F7 -> F7 -> Bool
> :: F7 -> F7 -> Bool
$c> :: F7 -> F7 -> Bool
<= :: F7 -> F7 -> Bool
$c<= :: F7 -> F7 -> Bool
< :: F7 -> F7 -> Bool
$c< :: F7 -> F7 -> Bool
compare :: F7 -> F7 -> Ordering
$ccompare :: F7 -> F7 -> Ordering
$cp1Ord :: Eq F7
Ord)

instance Show F7 where
    show :: F7 -> String
show (F7 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F7 where
    F7 x :: Int
x + :: F7 -> F7 -> F7
+ F7 y :: Int
y = Int -> F7
F7 (Int -> F7) -> Int -> F7
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 7
    negate :: F7 -> F7
negate (F7 0) = Int -> F7
F7 0
    negate (F7 x :: Int
x) = Int -> F7
F7 (Int -> F7) -> Int -> F7
forall a b. (a -> b) -> a -> b
$ 7 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F7 x :: Int
x * :: F7 -> F7 -> F7
* F7 y :: Int
y = Int -> F7
F7 (Int -> F7) -> Int -> F7
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 7
    fromInteger :: Integer -> F7
fromInteger n :: Integer
n = Int -> F7
F7 (Int -> F7) -> Int -> F7
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 7
    abs :: F7 -> F7
abs _ = String -> F7
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F7 -> F7
signum _ = String -> F7
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F7 where
    recip :: F7 -> F7
recip (F7 0) = String -> F7
forall a. HasCallStack => String -> a
error "F7.recip 0"
    recip (F7 x :: Int
x) = Int -> F7
F7 (Int -> F7) -> Int -> F7
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^5) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 7
    fromRational :: Rational -> F7
fromRational _ = String -> F7
forall a. HasCallStack => String -> a
error "F7.fromRational: not well defined"

instance FinSet F7 where elts :: [F7]
elts = [F7]
f7

-- |f7 is a list of 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]


-- |F11 is a type for the finite field with 11 elements
newtype F11 = F11 Int deriving (F11 -> F11 -> Bool
(F11 -> F11 -> Bool) -> (F11 -> F11 -> Bool) -> Eq F11
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F11 -> F11 -> Bool
$c/= :: F11 -> F11 -> Bool
== :: F11 -> F11 -> Bool
$c== :: F11 -> F11 -> Bool
Eq,Eq F11
Eq F11 =>
(F11 -> F11 -> Ordering)
-> (F11 -> F11 -> Bool)
-> (F11 -> F11 -> Bool)
-> (F11 -> F11 -> Bool)
-> (F11 -> F11 -> Bool)
-> (F11 -> F11 -> F11)
-> (F11 -> F11 -> F11)
-> Ord F11
F11 -> F11 -> Bool
F11 -> F11 -> Ordering
F11 -> F11 -> F11
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 :: F11 -> F11 -> F11
$cmin :: F11 -> F11 -> F11
max :: F11 -> F11 -> F11
$cmax :: F11 -> F11 -> F11
>= :: F11 -> F11 -> Bool
$c>= :: F11 -> F11 -> Bool
> :: F11 -> F11 -> Bool
$c> :: F11 -> F11 -> Bool
<= :: F11 -> F11 -> Bool
$c<= :: F11 -> F11 -> Bool
< :: F11 -> F11 -> Bool
$c< :: F11 -> F11 -> Bool
compare :: F11 -> F11 -> Ordering
$ccompare :: F11 -> F11 -> Ordering
$cp1Ord :: Eq F11
Ord)

instance Show F11 where
    show :: F11 -> String
show (F11 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F11 where
    F11 x :: Int
x + :: F11 -> F11 -> F11
+ F11 y :: Int
y = Int -> F11
F11 (Int -> F11) -> Int -> F11
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 11
    negate :: F11 -> F11
negate (F11 0) = Int -> F11
F11 0
    negate (F11 x :: Int
x) = Int -> F11
F11 (Int -> F11) -> Int -> F11
forall a b. (a -> b) -> a -> b
$ 11 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F11 x :: Int
x * :: F11 -> F11 -> F11
* F11 y :: Int
y = Int -> F11
F11 (Int -> F11) -> Int -> F11
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 11
    fromInteger :: Integer -> F11
fromInteger n :: Integer
n = Int -> F11
F11 (Int -> F11) -> Int -> F11
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 11
    abs :: F11 -> F11
abs _ = String -> F11
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F11 -> F11
signum _ = String -> F11
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F11 where
    recip :: F11 -> F11
recip (F11 0) = String -> F11
forall a. HasCallStack => String -> a
error "F11.recip 0"
    recip (F11 x :: Int
x) = Int -> F11
F11 (Int -> F11) -> Int -> F11
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^9) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 11
    fromRational :: Rational -> F11
fromRational _ = String -> F11
forall a. HasCallStack => String -> a
error "F11.fromRational: not well defined"

instance FinSet F11 where elts :: [F11]
elts = [F11]
f11

-- |f11 is a list of the elements of F11
f11 :: [F11]
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]


-- |F13 is a type for the finite field with 13 elements
newtype F13 = F13 Int deriving (F13 -> F13 -> Bool
(F13 -> F13 -> Bool) -> (F13 -> F13 -> Bool) -> Eq F13
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F13 -> F13 -> Bool
$c/= :: F13 -> F13 -> Bool
== :: F13 -> F13 -> Bool
$c== :: F13 -> F13 -> Bool
Eq,Eq F13
Eq F13 =>
(F13 -> F13 -> Ordering)
-> (F13 -> F13 -> Bool)
-> (F13 -> F13 -> Bool)
-> (F13 -> F13 -> Bool)
-> (F13 -> F13 -> Bool)
-> (F13 -> F13 -> F13)
-> (F13 -> F13 -> F13)
-> Ord F13
F13 -> F13 -> Bool
F13 -> F13 -> Ordering
F13 -> F13 -> F13
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 :: F13 -> F13 -> F13
$cmin :: F13 -> F13 -> F13
max :: F13 -> F13 -> F13
$cmax :: F13 -> F13 -> F13
>= :: F13 -> F13 -> Bool
$c>= :: F13 -> F13 -> Bool
> :: F13 -> F13 -> Bool
$c> :: F13 -> F13 -> Bool
<= :: F13 -> F13 -> Bool
$c<= :: F13 -> F13 -> Bool
< :: F13 -> F13 -> Bool
$c< :: F13 -> F13 -> Bool
compare :: F13 -> F13 -> Ordering
$ccompare :: F13 -> F13 -> Ordering
$cp1Ord :: Eq F13
Ord)

instance Show F13 where
    show :: F13 -> String
show (F13 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F13 where
    F13 x :: Int
x + :: F13 -> F13 -> F13
+ F13 y :: Int
y = Int -> F13
F13 (Int -> F13) -> Int -> F13
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 13
    negate :: F13 -> F13
negate (F13 0) = Int -> F13
F13 0
    negate (F13 x :: Int
x) = Int -> F13
F13 (Int -> F13) -> Int -> F13
forall a b. (a -> b) -> a -> b
$ 13 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F13 x :: Int
x * :: F13 -> F13 -> F13
* F13 y :: Int
y = Int -> F13
F13 (Int -> F13) -> Int -> F13
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 13
    fromInteger :: Integer -> F13
fromInteger n :: Integer
n = Int -> F13
F13 (Int -> F13) -> Int -> F13
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 13
    abs :: F13 -> F13
abs _ = String -> F13
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F13 -> F13
signum _ = String -> F13
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F13 where
    recip :: F13 -> F13
recip (F13 0) = String -> F13
forall a. HasCallStack => String -> a
error "F13.recip 0"
    recip (F13 x :: Int
x) = Int -> F13
F13 (Int -> F13) -> Int -> F13
forall a b. (a -> b) -> a -> b
$ (Int
x5Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
x5Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
x) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 13 where x5 :: Int
x5 = Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^5 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 13 -- 12^11 would overflow Int
    fromRational :: Rational -> F13
fromRational _ = String -> F13
forall a. HasCallStack => String -> a
error "F13.fromRational: not well defined"

instance FinSet F13 where elts :: [F13]
elts = [F13]
f13

-- |f13 is a list of the elements of F13
f13 :: [F13]
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]


-- |F17 is a type for the finite field with 17 elements
newtype F17 = F17 Int deriving (F17 -> F17 -> Bool
(F17 -> F17 -> Bool) -> (F17 -> F17 -> Bool) -> Eq F17
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F17 -> F17 -> Bool
$c/= :: F17 -> F17 -> Bool
== :: F17 -> F17 -> Bool
$c== :: F17 -> F17 -> Bool
Eq,Eq F17
Eq F17 =>
(F17 -> F17 -> Ordering)
-> (F17 -> F17 -> Bool)
-> (F17 -> F17 -> Bool)
-> (F17 -> F17 -> Bool)
-> (F17 -> F17 -> Bool)
-> (F17 -> F17 -> F17)
-> (F17 -> F17 -> F17)
-> Ord F17
F17 -> F17 -> Bool
F17 -> F17 -> Ordering
F17 -> F17 -> F17
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 :: F17 -> F17 -> F17
$cmin :: F17 -> F17 -> F17
max :: F17 -> F17 -> F17
$cmax :: F17 -> F17 -> F17
>= :: F17 -> F17 -> Bool
$c>= :: F17 -> F17 -> Bool
> :: F17 -> F17 -> Bool
$c> :: F17 -> F17 -> Bool
<= :: F17 -> F17 -> Bool
$c<= :: F17 -> F17 -> Bool
< :: F17 -> F17 -> Bool
$c< :: F17 -> F17 -> Bool
compare :: F17 -> F17 -> Ordering
$ccompare :: F17 -> F17 -> Ordering
$cp1Ord :: Eq F17
Ord)

instance Show F17 where
    show :: F17 -> String
show (F17 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F17 where
    F17 x :: Int
x + :: F17 -> F17 -> F17
+ F17 y :: Int
y = Int -> F17
F17 (Int -> F17) -> Int -> F17
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 17
    negate :: F17 -> F17
negate (F17 0) = Int -> F17
F17 0
    negate (F17 x :: Int
x) = Int -> F17
F17 (Int -> F17) -> Int -> F17
forall a b. (a -> b) -> a -> b
$ 17 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F17 x :: Int
x * :: F17 -> F17 -> F17
* F17 y :: Int
y = Int -> F17
F17 (Int -> F17) -> Int -> F17
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 17
    fromInteger :: Integer -> F17
fromInteger n :: Integer
n = Int -> F17
F17 (Int -> F17) -> Int -> F17
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 17
    abs :: F17 -> F17
abs _ = String -> F17
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F17 -> F17
signum _ = String -> F17
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F17 where
    recip :: F17 -> F17
recip (F17 0) = String -> F17
forall a. HasCallStack => String -> a
error "F17.recip 0"
    recip (F17 x :: Int
x) = Int -> F17
F17 (Int -> F17) -> Int -> F17
forall a b. (a -> b) -> a -> b
$ (Int
x5Int -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^3) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 17 where x5 :: Int
x5 = Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^5 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 17 -- 16^15 would overflow Int
    fromRational :: Rational -> F17
fromRational _ = String -> F17
forall a. HasCallStack => String -> a
error "F17.fromRational: not well defined"

instance FinSet F17 where elts :: [F17]
elts = [F17]
f17

-- |f17 is a list of the elements of F17
f17 :: [F17]
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]


-- |F19 is a type for the finite field with 19 elements
newtype F19 = F19 Int deriving (F19 -> F19 -> Bool
(F19 -> F19 -> Bool) -> (F19 -> F19 -> Bool) -> Eq F19
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F19 -> F19 -> Bool
$c/= :: F19 -> F19 -> Bool
== :: F19 -> F19 -> Bool
$c== :: F19 -> F19 -> Bool
Eq,Eq F19
Eq F19 =>
(F19 -> F19 -> Ordering)
-> (F19 -> F19 -> Bool)
-> (F19 -> F19 -> Bool)
-> (F19 -> F19 -> Bool)
-> (F19 -> F19 -> Bool)
-> (F19 -> F19 -> F19)
-> (F19 -> F19 -> F19)
-> Ord F19
F19 -> F19 -> Bool
F19 -> F19 -> Ordering
F19 -> F19 -> F19
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 :: F19 -> F19 -> F19
$cmin :: F19 -> F19 -> F19
max :: F19 -> F19 -> F19
$cmax :: F19 -> F19 -> F19
>= :: F19 -> F19 -> Bool
$c>= :: F19 -> F19 -> Bool
> :: F19 -> F19 -> Bool
$c> :: F19 -> F19 -> Bool
<= :: F19 -> F19 -> Bool
$c<= :: F19 -> F19 -> Bool
< :: F19 -> F19 -> Bool
$c< :: F19 -> F19 -> Bool
compare :: F19 -> F19 -> Ordering
$ccompare :: F19 -> F19 -> Ordering
$cp1Ord :: Eq F19
Ord)

instance Show F19 where
    show :: F19 -> String
show (F19 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F19 where
    F19 x :: Int
x + :: F19 -> F19 -> F19
+ F19 y :: Int
y = Int -> F19
F19 (Int -> F19) -> Int -> F19
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 19
    negate :: F19 -> F19
negate (F19 0) = Int -> F19
F19 0
    negate (F19 x :: Int
x) = Int -> F19
F19 (Int -> F19) -> Int -> F19
forall a b. (a -> b) -> a -> b
$ 19 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F19 x :: Int
x * :: F19 -> F19 -> F19
* F19 y :: Int
y = Int -> F19
F19 (Int -> F19) -> Int -> F19
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 19
    fromInteger :: Integer -> F19
fromInteger n :: Integer
n = Int -> F19
F19 (Int -> F19) -> Int -> F19
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 19
    abs :: F19 -> F19
abs _ = String -> F19
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F19 -> F19
signum _ = String -> F19
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F19 where
    recip :: F19 -> F19
recip (F19 0) = String -> F19
forall a. HasCallStack => String -> a
error "F17.recip 0"
    recip (F19 x :: Int
x) = Int -> F19
F19 (Int -> F19) -> Int -> F19
forall a b. (a -> b) -> a -> b
$ (Int
x4Int -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^4Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
x) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 19 where x4 :: Int
x4 = Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^4 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 19 -- 18^17 would overflow Int
    fromRational :: Rational -> F19
fromRational _ = String -> F19
forall a. HasCallStack => String -> a
error "F19.fromRational: not well defined"

instance FinSet F19 where elts :: [F19]
elts = [F19]
f19

-- |f19 is a list of the elements of F19
f19 :: [F19]
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]


-- |F23 is a type for the finite field with 23 elements
newtype F23 = F23 Int deriving (F23 -> F23 -> Bool
(F23 -> F23 -> Bool) -> (F23 -> F23 -> Bool) -> Eq F23
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F23 -> F23 -> Bool
$c/= :: F23 -> F23 -> Bool
== :: F23 -> F23 -> Bool
$c== :: F23 -> F23 -> Bool
Eq,Eq F23
Eq F23 =>
(F23 -> F23 -> Ordering)
-> (F23 -> F23 -> Bool)
-> (F23 -> F23 -> Bool)
-> (F23 -> F23 -> Bool)
-> (F23 -> F23 -> Bool)
-> (F23 -> F23 -> F23)
-> (F23 -> F23 -> F23)
-> Ord F23
F23 -> F23 -> Bool
F23 -> F23 -> Ordering
F23 -> F23 -> F23
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 :: F23 -> F23 -> F23
$cmin :: F23 -> F23 -> F23
max :: F23 -> F23 -> F23
$cmax :: F23 -> F23 -> F23
>= :: F23 -> F23 -> Bool
$c>= :: F23 -> F23 -> Bool
> :: F23 -> F23 -> Bool
$c> :: F23 -> F23 -> Bool
<= :: F23 -> F23 -> Bool
$c<= :: F23 -> F23 -> Bool
< :: F23 -> F23 -> Bool
$c< :: F23 -> F23 -> Bool
compare :: F23 -> F23 -> Ordering
$ccompare :: F23 -> F23 -> Ordering
$cp1Ord :: Eq F23
Ord)

instance Show F23 where
    show :: F23 -> String
show (F23 x :: Int
x) = Int -> String
forall a. Show a => a -> String
show Int
x

instance Num F23 where
    F23 x :: Int
x + :: F23 -> F23 -> F23
+ F23 y :: Int
y = Int -> F23
F23 (Int -> F23) -> Int -> F23
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 23
    negate :: F23 -> F23
negate (F23 0) = Int -> F23
F23 0
    negate (F23 x :: Int
x) = Int -> F23
F23 (Int -> F23) -> Int -> F23
forall a b. (a -> b) -> a -> b
$ 23 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x
    F23 x :: Int
x * :: F23 -> F23 -> F23
* F23 y :: Int
y = Int -> F23
F23 (Int -> F23) -> Int -> F23
forall a b. (a -> b) -> a -> b
$ (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 23
    fromInteger :: Integer -> F23
fromInteger n :: Integer
n = Int -> F23
F23 (Int -> F23) -> Int -> F23
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 23
    abs :: F23 -> F23
abs _ = String -> F23
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F23 -> F23
signum _ = String -> F23
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F23 where
    recip :: F23 -> F23
recip (F23 0) = String -> F23
forall a. HasCallStack => String -> a
error "F23.recip 0"
    recip (F23 x :: Int
x) = Int -> F23
F23 (Int -> F23) -> Int -> F23
forall a b. (a -> b) -> a -> b
$ (Int
x5Int -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^4Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
x) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 23 where x5 :: Int
x5 = Int
xInt -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^5 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 23 -- 22^21 would overflow Int
    fromRational :: Rational -> F23
fromRational _ = String -> F23
forall a. HasCallStack => String -> a
error "F23.fromRational: not well defined"

instance FinSet F23 where elts :: [F23]
elts = [F23]
f23

-- |f23 is a list of the elements of F23
f23 :: [F23]
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]


-- 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 (F4 -> F4 -> Bool
(F4 -> F4 -> Bool) -> (F4 -> F4 -> Bool) -> Eq F4
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F4 -> F4 -> Bool
$c/= :: F4 -> F4 -> Bool
== :: F4 -> F4 -> Bool
$c== :: F4 -> F4 -> Bool
Eq,Eq F4
Eq F4 =>
(F4 -> F4 -> Ordering)
-> (F4 -> F4 -> Bool)
-> (F4 -> F4 -> Bool)
-> (F4 -> F4 -> Bool)
-> (F4 -> F4 -> Bool)
-> (F4 -> F4 -> F4)
-> (F4 -> F4 -> F4)
-> Ord F4
F4 -> F4 -> Bool
F4 -> F4 -> Ordering
F4 -> F4 -> F4
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 :: F4 -> F4 -> F4
$cmin :: F4 -> F4 -> F4
max :: F4 -> F4 -> F4
$cmax :: F4 -> F4 -> F4
>= :: F4 -> F4 -> Bool
$c>= :: F4 -> F4 -> Bool
> :: F4 -> F4 -> Bool
$c> :: F4 -> F4 -> Bool
<= :: F4 -> F4 -> Bool
$c<= :: F4 -> F4 -> Bool
< :: F4 -> F4 -> Bool
$c< :: F4 -> F4 -> Bool
compare :: F4 -> F4 -> Ordering
$ccompare :: F4 -> F4 -> Ordering
$cp1Ord :: Eq F4
Ord)

instance Show F4 where
    show :: F4 -> String
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
a4 = Int -> F4
F4 0x10

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

instance Fractional F4 where
    recip :: F4 -> F4
recip (F4 0) = String -> F4
forall a. HasCallStack => String -> a
error "F4.recip 0"
    recip (F4 1) = Int -> F4
F4 1
    recip (F4 x :: Int
x) = Int -> F4
F4 (Int
x Int -> Int -> Int
forall a. Bits a => a -> a -> a
`xor` 1)
    fromRational :: Rational -> F4
fromRational _ = String -> F4
forall a. HasCallStack => String -> a
error "F4.fromRational: not well defined"

instance FinSet F4 where elts :: [F4]
elts = [F4]
f4

-- |f4 is a list of the elements of F4
f4 :: [F4]
f4 :: [F4]
f4 = [F4] -> [F4]
forall a. Ord a => [a] -> [a]
L.sort ([F4] -> [F4]) -> [F4] -> [F4]
forall a b. (a -> b) -> a -> b
$ 0 F4 -> [F4] -> [F4]
forall a. a -> [a] -> [a]
: F4 -> [F4]
forall a. (Eq a, Num a) => a -> [a]
powers F4
a4

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)


-- |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 (F8 -> F8 -> Bool
(F8 -> F8 -> Bool) -> (F8 -> F8 -> Bool) -> Eq F8
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F8 -> F8 -> Bool
$c/= :: F8 -> F8 -> Bool
== :: F8 -> F8 -> Bool
$c== :: F8 -> F8 -> Bool
Eq,Eq F8
Eq F8 =>
(F8 -> F8 -> Ordering)
-> (F8 -> F8 -> Bool)
-> (F8 -> F8 -> Bool)
-> (F8 -> F8 -> Bool)
-> (F8 -> F8 -> Bool)
-> (F8 -> F8 -> F8)
-> (F8 -> F8 -> F8)
-> Ord F8
F8 -> F8 -> Bool
F8 -> F8 -> Ordering
F8 -> F8 -> F8
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 :: F8 -> F8 -> F8
$cmin :: F8 -> F8 -> F8
max :: F8 -> F8 -> F8
$cmax :: F8 -> F8 -> F8
>= :: F8 -> F8 -> Bool
$c>= :: F8 -> F8 -> Bool
> :: F8 -> F8 -> Bool
$c> :: F8 -> F8 -> Bool
<= :: F8 -> F8 -> Bool
$c<= :: F8 -> F8 -> Bool
< :: F8 -> F8 -> Bool
$c< :: F8 -> F8 -> Bool
compare :: F8 -> F8 -> Ordering
$ccompare :: F8 -> F8 -> Ordering
$cp1Ord :: Eq F8
Ord)

instance Show F8 where
    show :: F8 -> String
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
a8 = Int -> F8
F8 0x10

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

instance Fractional F8 where
    recip :: F8 -> F8
recip (F8 0) = String -> F8
forall a. HasCallStack => String -> a
error "F8.recip 0"
    recip x :: F8
x = F8
xF8 -> Integer -> F8
forall a b. (Num a, Integral b) => a -> b -> a
^6
    fromRational :: Rational -> F8
fromRational _ = String -> F8
forall a. HasCallStack => String -> a
error "F8.fromRational: not well defined"

instance FinSet F8 where elts :: [F8]
elts = [F8]
f8

-- |f8 is a list of the elements of F8
f8 :: [F8]
f8 :: [F8]
f8 = [F8] -> [F8]
forall a. Ord a => [a] -> [a]
L.sort ([F8] -> [F8]) -> [F8] -> [F8]
forall a b. (a -> b) -> a -> b
$ 0 F8 -> [F8] -> [F8]
forall a. a -> [a] -> [a]
: F8 -> [F8]
forall a. (Eq a, Num a) => a -> [a]
powers F8
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 (F9 -> F9 -> Bool
(F9 -> F9 -> Bool) -> (F9 -> F9 -> Bool) -> Eq F9
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F9 -> F9 -> Bool
$c/= :: F9 -> F9 -> Bool
== :: F9 -> F9 -> Bool
$c== :: F9 -> F9 -> Bool
Eq,Eq F9
Eq F9 =>
(F9 -> F9 -> Ordering)
-> (F9 -> F9 -> Bool)
-> (F9 -> F9 -> Bool)
-> (F9 -> F9 -> Bool)
-> (F9 -> F9 -> Bool)
-> (F9 -> F9 -> F9)
-> (F9 -> F9 -> F9)
-> Ord F9
F9 -> F9 -> Bool
F9 -> F9 -> Ordering
F9 -> F9 -> F9
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 :: F9 -> F9 -> F9
$cmin :: F9 -> F9 -> F9
max :: F9 -> F9 -> F9
$cmax :: F9 -> F9 -> F9
>= :: F9 -> F9 -> Bool
$c>= :: F9 -> F9 -> Bool
> :: F9 -> F9 -> Bool
$c> :: F9 -> F9 -> Bool
<= :: F9 -> F9 -> Bool
$c<= :: F9 -> F9 -> Bool
< :: F9 -> F9 -> Bool
$c< :: F9 -> F9 -> Bool
compare :: F9 -> F9 -> Ordering
$ccompare :: F9 -> F9 -> Ordering
$cp1Ord :: Eq F9
Ord)

instance Show F9 where
    show :: F9 -> String
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
a9 = Int -> F9
F9 0x100

instance Num F9 where
    F9 x :: Int
x + :: F9 -> F9 -> F9
+ F9 y :: Int
y = Int -> F9
F9 (Int -> F9) -> Int -> F9
forall a b. (a -> b) -> a -> b
$ Int
z1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z0
        where z :: Int
z = Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y; z1 :: Int
z1 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 0x300; z0 :: Int
z0 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 3
    negate :: F9 -> F9
negate (F9 x :: Int
x) = Int -> F9
F9 (Int -> F9) -> Int -> F9
forall a b. (a -> b) -> a -> b
$ Int
z1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z0
        where z :: Int
z = 0x303 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x; z1 :: Int
z1 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 0x300; z0 :: Int
z0 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 3
    F9 x :: Int
x * :: F9 -> F9 -> F9
* F9 y :: Int
y = Int -> F9
F9 (Int -> F9) -> Int -> F9
forall a b. (a -> b) -> a -> b
$ ((Int
z2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 0x300) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ ((Int
z2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z0) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 3) 
        where z :: Int
z = Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y; z2 :: Int
z2 = Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff0000; z1 :: Int
z1 = Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00; z0 :: Int
z0 = Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 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 :: Integer -> F9
fromInteger n :: Integer
n = Int -> F9
F9 (Int -> F9) -> Int -> F9
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 3
    abs :: F9 -> F9
abs _ = String -> F9
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F9 -> F9
signum _ = String -> F9
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F9 where
    recip :: F9 -> F9
recip (F9 0) = String -> F9
forall a. HasCallStack => String -> a
error "F9.recip 0"
    recip x :: F9
x = F9
xF9 -> Integer -> F9
forall a b. (Num a, Integral b) => a -> b -> a
^7
    fromRational :: Rational -> F9
fromRational _ = String -> F9
forall a. HasCallStack => String -> a
error "F9.fromRational: not well defined"

instance FinSet F9 where elts :: [F9]
elts = [F9]
f9

-- |f9 is a list of the elements of F9
f9 :: [F9]
f9 :: [F9]
f9 = [F9] -> [F9]
forall a. Ord a => [a] -> [a]
L.sort ([F9] -> [F9]) -> [F9] -> [F9]
forall a b. (a -> b) -> a -> b
$ 0 F9 -> [F9] -> [F9]
forall a. a -> [a] -> [a]
: F9 -> [F9]
forall a. (Eq a, Num a) => a -> [a]
powers F9
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 (F16 -> F16 -> Bool
(F16 -> F16 -> Bool) -> (F16 -> F16 -> Bool) -> Eq F16
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F16 -> F16 -> Bool
$c/= :: F16 -> F16 -> Bool
== :: F16 -> F16 -> Bool
$c== :: F16 -> F16 -> Bool
Eq,Eq F16
Eq F16 =>
(F16 -> F16 -> Ordering)
-> (F16 -> F16 -> Bool)
-> (F16 -> F16 -> Bool)
-> (F16 -> F16 -> Bool)
-> (F16 -> F16 -> Bool)
-> (F16 -> F16 -> F16)
-> (F16 -> F16 -> F16)
-> Ord F16
F16 -> F16 -> Bool
F16 -> F16 -> Ordering
F16 -> F16 -> F16
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 :: F16 -> F16 -> F16
$cmin :: F16 -> F16 -> F16
max :: F16 -> F16 -> F16
$cmax :: F16 -> F16 -> F16
>= :: F16 -> F16 -> Bool
$c>= :: F16 -> F16 -> Bool
> :: F16 -> F16 -> Bool
$c> :: F16 -> F16 -> Bool
<= :: F16 -> F16 -> Bool
$c<= :: F16 -> F16 -> Bool
< :: F16 -> F16 -> Bool
$c< :: F16 -> F16 -> Bool
compare :: F16 -> F16 -> Ordering
$ccompare :: F16 -> F16 -> Ordering
$cp1Ord :: Eq F16
Ord)

instance Show F16 where
    show :: F16 -> String
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
a16 = Int -> F16
F16 0x10

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

instance Fractional F16 where
    recip :: F16 -> F16
recip (F16 0) = String -> F16
forall a. HasCallStack => String -> a
error "F16.recip 0"
    recip x :: F16
x = F16
xF16 -> Integer -> F16
forall a b. (Num a, Integral b) => a -> b -> a
^14
    fromRational :: Rational -> F16
fromRational _ = String -> F16
forall a. HasCallStack => String -> a
error "F16.fromRational: not well defined"

instance FinSet F16 where elts :: [F16]
elts = [F16]
f16

-- |f16 is a list of the elements of F16
f16 :: [F16]
f16 :: [F16]
f16 = [F16] -> [F16]
forall a. Ord a => [a] -> [a]
L.sort ([F16] -> [F16]) -> [F16] -> [F16]
forall a b. (a -> b) -> a -> b
$ 0 F16 -> [F16] -> [F16]
forall a. a -> [a] -> [a]
: F16 -> [F16]
forall a. (Eq a, Num a) => a -> [a]
powers F16
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 (F25 -> F25 -> Bool
(F25 -> F25 -> Bool) -> (F25 -> F25 -> Bool) -> Eq F25
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: F25 -> F25 -> Bool
$c/= :: F25 -> F25 -> Bool
== :: F25 -> F25 -> Bool
$c== :: F25 -> F25 -> Bool
Eq,Eq F25
Eq F25 =>
(F25 -> F25 -> Ordering)
-> (F25 -> F25 -> Bool)
-> (F25 -> F25 -> Bool)
-> (F25 -> F25 -> Bool)
-> (F25 -> F25 -> Bool)
-> (F25 -> F25 -> F25)
-> (F25 -> F25 -> F25)
-> Ord F25
F25 -> F25 -> Bool
F25 -> F25 -> Ordering
F25 -> F25 -> F25
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 :: F25 -> F25 -> F25
$cmin :: F25 -> F25 -> F25
max :: F25 -> F25 -> F25
$cmax :: F25 -> F25 -> F25
>= :: F25 -> F25 -> Bool
$c>= :: F25 -> F25 -> Bool
> :: F25 -> F25 -> Bool
$c> :: F25 -> F25 -> Bool
<= :: F25 -> F25 -> Bool
$c<= :: F25 -> F25 -> Bool
< :: F25 -> F25 -> Bool
$c< :: F25 -> F25 -> Bool
compare :: F25 -> F25 -> Ordering
$ccompare :: F25 -> F25 -> Ordering
$cp1Ord :: Eq F25
Ord)

instance Show F25 where
    show :: F25 -> String
show (F25 x :: Int
x) = case ( (Int
x Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00) Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftR` 8, Int
x Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff ) of
                   (0,x0 :: Int
x0) -> Int -> String
forall a. Show a => a -> String
show Int
x0
                   (1,0) -> "a25"
                   (1,x0 :: Int
x0) -> "a25+" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
x0
                   (x1 :: Int
x1,0) -> Int -> String
forall a. Show a => a -> String
show Int
x1 String -> ShowS
forall a. [a] -> [a] -> [a]
++ "a25"
                   (x1 :: Int
x1,x0 :: Int
x0) -> Int -> String
forall a. Show a => a -> String
show Int
x1 String -> ShowS
forall a. [a] -> [a] -> [a]
++ "a25+" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
x0

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

instance Num F25 where
    F25 x :: Int
x + :: F25 -> F25 -> F25
+ F25 y :: Int
y = Int -> F25
F25 (Int -> F25) -> Int -> F25
forall a b. (a -> b) -> a -> b
$ Int
z1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z0
        where z :: Int
z = Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
y; z1 :: Int
z1 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 0x500; z0 :: Int
z0 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 5
    negate :: F25 -> F25
negate (F25 x :: Int
x) = Int -> F25
F25 (Int -> F25) -> Int -> F25
forall a b. (a -> b) -> a -> b
$ Int
z1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z0
        where z :: Int
z = 0x505 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x; z1 :: Int
z1 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 0x500; z0 :: Int
z0 = (Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 5
    F25 x :: Int
x * :: F25 -> F25 -> F25
* F25 y :: Int
y = Int -> F25
F25 (Int -> F25) -> Int -> F25
forall a b. (a -> b) -> a -> b
$ ((Int
z2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 0x500) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ ((3Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
z2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
z0) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` 5) 
        where z :: Int
z = Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
y; z2 :: Int
z2 = Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff0000; z1 :: Int
z1 = Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 0xff00; z0 :: Int
z0 = Int
z Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. 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 :: Integer -> F25
fromInteger n :: Integer
n = Int -> F25
F25 (Int -> F25) -> Int -> F25
forall a b. (a -> b) -> a -> b
$ Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` 5
    abs :: F25 -> F25
abs _ = String -> F25
forall a. HasCallStack => String -> a
error "Prelude.Num.abs: inappropriate abstraction"
    signum :: F25 -> F25
signum _ = String -> F25
forall a. HasCallStack => String -> a
error "Prelude.Num.signum: inappropriate abstraction"

instance Fractional F25 where
    recip :: F25 -> F25
recip (F25 0) = String -> F25
forall a. HasCallStack => String -> a
error "F25.recip 0"
    recip x :: F25
x = F25
xF25 -> Integer -> F25
forall a b. (Num a, Integral b) => a -> b -> a
^23
    fromRational :: Rational -> F25
fromRational _ = String -> F25
forall a. HasCallStack => String -> a
error "F25.fromRational: not well defined"

instance FinSet F25 where elts :: [F25]
elts = [F25]
f25

-- |f25 is a list of the elements of F25
f25 :: [F25]
f25 :: [F25]
f25 = [F25] -> [F25]
forall a. Ord a => [a] -> [a]
L.sort ([F25] -> [F25]) -> [F25] -> [F25]
forall a b. (a -> b) -> a -> b
$ 0 F25 -> [F25] -> [F25]
forall a. a -> [a] -> [a]
: F25 -> [F25]
forall a. (Eq a, Num a) => a -> [a]
powers F25
a25