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

    {-# LANGUAGE MultiParamTypeClasses, TypeSynonymInstances, ScopedTypeVariables, EmptyDataDecls, FlexibleInstances #-}

    module Math.Algebra.Field.Extension where

    import Prelude hiding ( (<*>) )

    import Data.Ratio
    import Data.List as L (elemIndex)

    import Math.Common.IntegerAsType
    import Math.Core.Utils
    import Math.Algebra.Field.Base

    -- UNIVARIATE POLYNOMIALS

    newtype UPoly a = UP [a] deriving (UPoly a -> UPoly a -> Bool
    (UPoly a -> UPoly a -> Bool)
    -> (UPoly a -> UPoly a -> Bool) -> Eq (UPoly a)
    forall a. Eq a => UPoly a -> UPoly a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    /= :: UPoly a -> UPoly a -> Bool
    $c/= :: forall a. Eq a => UPoly a -> UPoly a -> Bool
    == :: UPoly a -> UPoly a -> Bool
    $c== :: forall a. Eq a => UPoly a -> UPoly a -> Bool
    Eq,Eq (UPoly a)
    Eq (UPoly a) =>
    (UPoly a -> UPoly a -> Ordering)
    -> (UPoly a -> UPoly a -> Bool)
    -> (UPoly a -> UPoly a -> Bool)
    -> (UPoly a -> UPoly a -> Bool)
    -> (UPoly a -> UPoly a -> Bool)
    -> (UPoly a -> UPoly a -> UPoly a)
    -> (UPoly a -> UPoly a -> UPoly a)
    -> Ord (UPoly a)
    UPoly a -> UPoly a -> Bool
    UPoly a -> UPoly a -> Ordering
    UPoly a -> UPoly a -> UPoly a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall a. Ord a => Eq (UPoly a)
    forall a. Ord a => UPoly a -> UPoly a -> Bool
    forall a. Ord a => UPoly a -> UPoly a -> Ordering
    forall a. Ord a => UPoly a -> UPoly a -> UPoly a
    min :: UPoly a -> UPoly a -> UPoly a
    $cmin :: forall a. Ord a => UPoly a -> UPoly a -> UPoly a
    max :: UPoly a -> UPoly a -> UPoly a
    $cmax :: forall a. Ord a => UPoly a -> UPoly a -> UPoly a
    >= :: UPoly a -> UPoly a -> Bool
    $c>= :: forall a. Ord a => UPoly a -> UPoly a -> Bool
    > :: UPoly a -> UPoly a -> Bool
    $c> :: forall a. Ord a => UPoly a -> UPoly a -> Bool
    <= :: UPoly a -> UPoly a -> Bool
    $c<= :: forall a. Ord a => UPoly a -> UPoly a -> Bool
    < :: UPoly a -> UPoly a -> Bool
    $c< :: forall a. Ord a => UPoly a -> UPoly a -> Bool
    compare :: UPoly a -> UPoly a -> Ordering
    $ccompare :: forall a. Ord a => UPoly a -> UPoly a -> Ordering
    $cp1Ord :: forall a. Ord a => Eq (UPoly a)
    Ord)
    -- the list [a_0, a_1, ..., a_n] represents the polynomial a_0 + a_1 x + ... + a_n x^n

    x :: UPoly Integer
    x = [Integer] -> UPoly Integer
    forall a. [a] -> UPoly a
    UP [0,1] :: UPoly Integer

    instance (Eq a, Show a, Num a) => Show (UPoly a) where
        -- show (UP []) = "0"

        show :: UPoly a -> String
    show (UP as :: [a]
    as) = String -> [a] -> String
    forall a. (Eq a, Num a, Show a) => String -> [a] -> String
    showUP "x" [a]
    as

    showUP :: String -> [a] -> String
    showUP _ [] = "0"
    showUP v :: String
    v as :: [a]
    as = let powers :: [(a, Integer)]
    powers = ((a, Integer) -> Bool) -> [(a, Integer)] -> [(a, Integer)]
    forall a. (a -> Bool) -> [a] -> [a]
    filter ( (a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    /=0) (a -> Bool) -> ((a, Integer) -> a) -> (a, Integer) -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a, Integer) -> a
    forall a b. (a, b) -> a
    fst ) ([(a, Integer)] -> [(a, Integer)])
    -> [(a, Integer)] -> [(a, Integer)]
    forall a b. (a -> b) -> a -> b
    $ [a] -> [Integer] -> [(a, Integer)]
    forall a b. [a] -> [b] -> [(a, b)]
    zip [a]
    as [0..]
                      c :: Char
    c:cs :: String
    cs = ((a, Integer) -> String) -> [(a, Integer)] -> String
    forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
    concatMap (a, Integer) -> String
    forall a a. (Num a, Ord a, Show a, Show a) => (a, a) -> String
    showTerm [(a, Integer)]
    powers
                  in if Char
    c Char -> Char -> Bool
    forall a. Eq a => a -> a -> Bool
    == '+' then String
    cs else Char
    cChar -> ShowS
    forall a. a -> [a] -> [a]
    :String
    cs
        where showTerm :: (a, a) -> String
    showTerm (a :: a
    a,i :: a
    i) = a -> String
    forall a. Show a => a -> String
    showCoeff a
    a String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ a -> a -> String
    forall a a. (Num a, Ord a, Show a, Show a) => a -> a -> String
    showPower a
    a a
    i
              showCoeff :: a -> String
    showCoeff a :: a
    a = case a -> String
    forall a. Show a => a -> String
    show a
    a of
                            "1" -> "+"
                            "-1" -> "-"
                            '-':cs :: String
    cs -> '-'Char -> ShowS
    forall a. a -> [a] -> [a]
    :String
    cs
                            cs :: String
    cs -> '+'Char -> ShowS
    forall a. a -> [a] -> [a]
    :String
    cs
              showPower :: a -> a -> String
    showPower a :: a
    a i :: a
    i | a
    i a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0 = case a -> String
    forall a. Show a => a -> String
    show a
    a of
                                       "1" -> "1"
                                       "-1" -> "1"
                                       otherwise :: String
    otherwise -> ""
                            | a
    i a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1 = String
    v -- "x"

                            | a
    i a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    > 1  = String
    v String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ "^" String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ a -> String
    forall a. Show a => a -> String
    show a
    i -- "x^" ++ show i

    instance (Eq a, Num a) => Num (UPoly a) where
        UP as :: [a]
    as + :: UPoly a -> UPoly a -> UPoly a
    + UP bs :: [a]
    bs = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP ([a] -> UPoly a) -> [a] -> UPoly a
    forall a b. (a -> b) -> a -> b
    $ [a]
    as [a] -> [a] -> [a]
    forall a. (Eq a, Num a) => [a] -> [a] -> [a]
    <+> [a]
    bs
        negate :: UPoly a -> UPoly a
    negate (UP as :: [a]
    as) = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP ([a] -> UPoly a) -> [a] -> UPoly a
    forall a b. (a -> b) -> a -> b
    $ (a -> a) -> [a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map a -> a
    forall a. Num a => a -> a
    negate [a]
    as
        UP as :: [a]
    as * :: UPoly a -> UPoly a -> UPoly a
    * UP bs :: [a]
    bs = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP ([a] -> UPoly a) -> [a] -> UPoly a
    forall a b. (a -> b) -> a -> b
    $ [a]
    as [a] -> [a] -> [a]
    forall a. (Num a, Eq a) => [a] -> [a] -> [a]
    <*> [a]
    bs
        fromInteger :: Integer -> UPoly a
    fromInteger 0 = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP []
        fromInteger a :: Integer
    a = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP [Integer -> a
    forall a. Num a => Integer -> a
    fromInteger Integer
    a]
        abs :: UPoly a -> UPoly a
    abs _ = String -> UPoly a
    forall a. HasCallStack => String -> a
    error "Prelude.Num.abs: inappropriate abstraction"
        signum :: UPoly a -> UPoly a
    signum _ = String -> UPoly a
    forall a. HasCallStack => String -> a
    error "Prelude.Num.signum: inappropriate abstraction"

    toUPoly :: [a] -> UPoly a
    toUPoly as :: [a]
    as = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP ([a] -> [a]
    forall a. [a] -> [a]
    reverse ((a -> Bool) -> [a] -> [a]
    forall a. (a -> Bool) -> [a] -> [a]
    dropWhile (a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0) ([a] -> [a]
    forall a. [a] -> [a]
    reverse [a]
    as)))

    -- The fussiness of the code is to avoid adding trailing zeroes, eg [3] <+> [-3]

    -- Otherwise we would have to normalise after every addition

    as :: [a]
    as <+> :: [a] -> [a] -> [a]
    <+> [] = [a]
    as
    [] <+> bs :: [a]
    bs = [a]
    bs
    -- (a:as) <+> (b:bs) = (a+b) : (as <+> bs)

    (a :: a
    a:as :: [a]
    as) <+> (b :: a
    b:bs :: [a]
    bs) = let c :: a
    c = a
    aa -> a -> a
    forall a. Num a => a -> a -> a
    +a
    b
                            cs :: [a]
    cs = [a]
    as [a] -> [a] -> [a]
    <+> [a]
    bs
                        in if a
    c a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0 Bool -> Bool -> Bool
    && [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [a]
    cs then [] else a
    ca -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    cs

    -- The fussiness of the code is to avoid adding trailing zeroes.

    -- Note that since we call <+>, we rely on it having similar properties.

    [] <*> :: [a] -> [a] -> [a]
    <*> _ = []
    _ <*> [] = [] -- to avoid [0,1] <*> [] -> [0]

    (a :: a
    a:as :: [a]
    as) <*> bs :: [a]
    bs = if [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    null [a]
    as then (a -> a) -> [a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (a
    aa -> a -> a
    forall a. Num a => a -> a -> a
    *) [a]
    bs else (a -> a) -> [a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (a
    aa -> a -> a
    forall a. Num a => a -> a -> a
    *) [a]
    bs [a] -> [a] -> [a]
    forall a. (Eq a, Num a) => [a] -> [a] -> [a]
    <+> (0 a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    as [a] -> [a] -> [a]
    <*> [a]
    bs)

    -- > let valid xs = null xs || last xs /= 0

    -- > quickCheck (\as bs -> not (valid as) || not (valid bs) || valid (as <*> bs))

    {-
    -- The following definition introduces unnecessary trailing zeroes, eg [3] <*> [2] -> [6,0]
    [] <*> _ = []
    _ <*> [] = []
    (a:as) <*> (b:bs) = [a*b] <+> (0 : map (a*) bs) <+> (0 : map (*b) as) <+> (0 : 0 : as <*> bs)
    -}

    convert :: UPoly Integer -> UPoly a
    convert (UP as :: [Integer]
    as) = [a] -> UPoly a
    forall a. (Eq a, Num a) => [a] -> UPoly a
    toUPoly ([a] -> UPoly a) -> [a] -> UPoly a
    forall a b. (a -> b) -> a -> b
    $ (Integer -> a) -> [Integer] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map Integer -> a
    forall a. Num a => Integer -> a
    fromInteger [Integer]
    as
    -- Can be used with type annotations to construct polynomials over other types, eg

    -- > convert (x^2+3*x+2) :: UPoly F2

    -- x^2+x

    -- > convert (x^2+3*x+2) :: UPoly F3

    -- x^2+2

    -- DIVISION ALGORITHM

    -- degree

    deg :: UPoly a -> Int
    deg (UP as :: [a]
    as) = [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [a]
    as

    -- leading term

    lt :: UPoly a -> a
    lt (UP as :: [a]
    as) = [a] -> a
    forall a. [a] -> a
    last [a]
    as

    monomial :: a -> Int -> UPoly a
    monomial a :: a
    a i :: Int
    i = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP ([a] -> UPoly a) -> [a] -> UPoly a
    forall a b. (a -> b) -> a -> b
    $ Int -> a -> [a]
    forall a. Int -> a -> [a]
    replicate Int
    i 0 [a] -> [a] -> [a]
    forall a. [a] -> [a] -> [a]
    ++ [a
    a]

    -- quotRem for UPolys over a field

    quotRemUP :: (Eq k, Fractional k) => UPoly k -> UPoly k -> (UPoly k, UPoly k)
    quotRemUP :: UPoly k -> UPoly k -> (UPoly k, UPoly k)
    quotRemUP f :: UPoly k
    f g :: UPoly k
    g = UPoly k -> UPoly k -> (UPoly k, UPoly k)
    qr 0 UPoly k
    f where
        qr :: UPoly k -> UPoly k -> (UPoly k, UPoly k)
    qr q :: UPoly k
    q r :: UPoly k
    r = if UPoly k -> Int
    forall a. UPoly a -> Int
    deg UPoly k
    r Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    deg_g
                 then (UPoly k
    q,UPoly k
    r)
                 else let s :: UPoly k
    s = k -> Int -> UPoly k
    forall a. Num a => a -> Int -> UPoly a
    monomial (UPoly k -> k
    forall a. UPoly a -> a
    lt UPoly k
    r k -> k -> k
    forall a. Fractional a => a -> a -> a
    / k
    lt_g) (UPoly k -> Int
    forall a. UPoly a -> Int
    deg UPoly k
    r Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    deg_g)
                      in UPoly k -> UPoly k -> (UPoly k, UPoly k)
    qr (UPoly k
    qUPoly k -> UPoly k -> UPoly k
    forall a. Num a => a -> a -> a
    +UPoly k
    s) (UPoly k
    rUPoly k -> UPoly k -> UPoly k
    forall a. Num a => a -> a -> a
    -UPoly k
    sUPoly k -> UPoly k -> UPoly k
    forall a. Num a => a -> a -> a
    *UPoly k
    g)
        deg_g :: Int
    deg_g = UPoly k -> Int
    forall a. UPoly a -> Int
    deg UPoly k
    g
        lt_g :: k
    lt_g = UPoly k -> k
    forall a. UPoly a -> a
    lt UPoly k
    g

    modUP :: UPoly k -> UPoly k -> UPoly k
    modUP f :: UPoly k
    f g :: UPoly k
    g = (UPoly k, UPoly k) -> UPoly k
    forall a b. (a, b) -> b
    snd ((UPoly k, UPoly k) -> UPoly k) -> (UPoly k, UPoly k) -> UPoly k
    forall a b. (a -> b) -> a -> b
    $ UPoly k -> UPoly k -> (UPoly k, UPoly k)
    forall k.
    (Eq k, Fractional k) =>
    UPoly k -> UPoly k -> (UPoly k, UPoly k)
    quotRemUP UPoly k
    f UPoly k
    g

    -- extendedEuclidUP f g returns (u,v,d) such that u*f + v*g = d

    extendedEuclidUP :: UPoly k -> UPoly k -> (UPoly k, UPoly k, UPoly k)
    extendedEuclidUP f :: UPoly k
    f g :: UPoly k
    g = UPoly k -> UPoly k -> [UPoly k] -> (UPoly k, UPoly k, UPoly k)
    forall k.
    (Eq k, Fractional k) =>
    UPoly k -> UPoly k -> [UPoly k] -> (UPoly k, UPoly k, UPoly k)
    extendedEuclidUP' UPoly k
    f UPoly k
    g [] where
        extendedEuclidUP' :: UPoly k -> UPoly k -> [UPoly k] -> (UPoly k, UPoly k, UPoly k)
    extendedEuclidUP' d :: UPoly k
    d 0 qs :: [UPoly k]
    qs = let (u :: UPoly k
    u,v :: UPoly k
    v) = UPoly k -> UPoly k -> [UPoly k] -> (UPoly k, UPoly k)
    forall t. Num t => t -> t -> [t] -> (t, t)
    unwind 1 0 [UPoly k]
    qs in (UPoly k
    u,UPoly k
    v,UPoly k
    d)
        extendedEuclidUP' f :: UPoly k
    f g :: UPoly k
    g qs :: [UPoly k]
    qs = let (q :: UPoly k
    q,r :: UPoly k
    r) = UPoly k -> UPoly k -> (UPoly k, UPoly k)
    forall k.
    (Eq k, Fractional k) =>
    UPoly k -> UPoly k -> (UPoly k, UPoly k)
    quotRemUP UPoly k
    f UPoly k
    g in UPoly k -> UPoly k -> [UPoly k] -> (UPoly k, UPoly k, UPoly k)
    extendedEuclidUP' UPoly k
    g UPoly k
    r (UPoly k
    qUPoly k -> [UPoly k] -> [UPoly k]
    forall a. a -> [a] -> [a]
    :[UPoly k]
    qs)
        unwind :: t -> t -> [t] -> (t, t)
    unwind u :: t
    u v :: t
    v [] = (t
    u,t
    v)
        unwind u :: t
    u v :: t
    v (q :: t
    q:qs :: [t]
    qs) = t -> t -> [t] -> (t, t)
    unwind t
    v (t
    ut -> t -> t
    forall a. Num a => a -> a -> a
    -t
    vt -> t -> t
    forall a. Num a => a -> a -> a
    *t
    q) [t]
    qs

    -- EXTENSION FIELDS

    class PolynomialAsType k poly where
        pvalue :: (k,poly) -> UPoly k

    data ExtensionField k poly = Ext (UPoly k) deriving (ExtensionField k poly -> ExtensionField k poly -> Bool
    (ExtensionField k poly -> ExtensionField k poly -> Bool)
    -> (ExtensionField k poly -> ExtensionField k poly -> Bool)
    -> Eq (ExtensionField k poly)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall k poly.
    Eq k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    /= :: ExtensionField k poly -> ExtensionField k poly -> Bool
    $c/= :: forall k poly.
    Eq k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    == :: ExtensionField k poly -> ExtensionField k poly -> Bool
    $c== :: forall k poly.
    Eq k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    Eq,Eq (ExtensionField k poly)
    Eq (ExtensionField k poly) =>
    (ExtensionField k poly -> ExtensionField k poly -> Ordering)
    -> (ExtensionField k poly -> ExtensionField k poly -> Bool)
    -> (ExtensionField k poly -> ExtensionField k poly -> Bool)
    -> (ExtensionField k poly -> ExtensionField k poly -> Bool)
    -> (ExtensionField k poly -> ExtensionField k poly -> Bool)
    -> (ExtensionField k poly
        -> ExtensionField k poly -> ExtensionField k poly)
    -> (ExtensionField k poly
        -> ExtensionField k poly -> ExtensionField k poly)
    -> Ord (ExtensionField k poly)
    ExtensionField k poly -> ExtensionField k poly -> Bool
    ExtensionField k poly -> ExtensionField k poly -> Ordering
    ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall k poly. Ord k => Eq (ExtensionField k poly)
    forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Ordering
    forall k poly.
    Ord k =>
    ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    min :: ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    $cmin :: forall k poly.
    Ord k =>
    ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    max :: ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    $cmax :: forall k poly.
    Ord k =>
    ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    >= :: ExtensionField k poly -> ExtensionField k poly -> Bool
    $c>= :: forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    > :: ExtensionField k poly -> ExtensionField k poly -> Bool
    $c> :: forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    <= :: ExtensionField k poly -> ExtensionField k poly -> Bool
    $c<= :: forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    < :: ExtensionField k poly -> ExtensionField k poly -> Bool
    $c< :: forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Bool
    compare :: ExtensionField k poly -> ExtensionField k poly -> Ordering
    $ccompare :: forall k poly.
    Ord k =>
    ExtensionField k poly -> ExtensionField k poly -> Ordering
    $cp1Ord :: forall k poly. Ord k => Eq (ExtensionField k poly)
    Ord)

    instance (Eq k, Show k, Num k) => Show (ExtensionField k poly) where
        -- show (Ext f) = show f

        -- show (Ext (UP [])) = "0"

        show :: ExtensionField k poly -> String
    show (Ext (UP as :: [k]
    as)) = String -> [k] -> String
    forall a. (Eq a, Num a, Show a) => String -> [a] -> String
    showUP "a" [k]
    as

    instance (Eq k, Fractional k, PolynomialAsType k poly) => Num (ExtensionField k poly) where
        Ext x :: UPoly k
    x + :: ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    + Ext y :: UPoly k
    y = UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (UPoly k -> ExtensionField k poly)
    -> UPoly k -> ExtensionField k poly
    forall a b. (a -> b) -> a -> b
    $ (UPoly k
    xUPoly k -> UPoly k -> UPoly k
    forall a. Num a => a -> a -> a
    +UPoly k
    y) -- `modUP` pvalue (undefined :: (k,poly))

        Ext x :: UPoly k
    x * :: ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    * Ext y :: UPoly k
    y = UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (UPoly k -> ExtensionField k poly)
    -> UPoly k -> ExtensionField k poly
    forall a b. (a -> b) -> a -> b
    $ (UPoly k
    xUPoly k -> UPoly k -> UPoly k
    forall a. Num a => a -> a -> a
    *UPoly k
    y) UPoly k -> UPoly k -> UPoly k
    forall k. (Eq k, Fractional k) => UPoly k -> UPoly k -> UPoly k
    `modUP` (k, poly) -> UPoly k
    forall k poly. PolynomialAsType k poly => (k, poly) -> UPoly k
    pvalue ((k, poly)
    forall a. HasCallStack => a
    undefined :: (k,poly))
        negate :: ExtensionField k poly -> ExtensionField k poly
    negate (Ext x :: UPoly k
    x) = UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (UPoly k -> ExtensionField k poly)
    -> UPoly k -> ExtensionField k poly
    forall a b. (a -> b) -> a -> b
    $ UPoly k -> UPoly k
    forall a. Num a => a -> a
    negate UPoly k
    x
        fromInteger :: Integer -> ExtensionField k poly
    fromInteger x :: Integer
    x = UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (UPoly k -> ExtensionField k poly)
    -> UPoly k -> ExtensionField k poly
    forall a b. (a -> b) -> a -> b
    $ Integer -> UPoly k
    forall a. Num a => Integer -> a
    fromInteger Integer
    x
        abs :: ExtensionField k poly -> ExtensionField k poly
    abs _ = String -> ExtensionField k poly
    forall a. HasCallStack => String -> a
    error "Prelude.Num.abs: inappropriate abstraction"
        signum :: ExtensionField k poly -> ExtensionField k poly
    signum _ = String -> ExtensionField k poly
    forall a. HasCallStack => String -> a
    error "Prelude.Num.signum: inappropriate abstraction"

    instance (Eq k, Fractional k, PolynomialAsType k poly) => Fractional (ExtensionField k poly) where
        recip :: ExtensionField k poly -> ExtensionField k poly
    recip 0 = String -> ExtensionField k poly
    forall a. HasCallStack => String -> a
    error "ExtensionField.recip 0"
        recip (Ext f :: UPoly k
    f) = let g :: UPoly k
    g = (k, poly) -> UPoly k
    forall k poly. PolynomialAsType k poly => (k, poly) -> UPoly k
    pvalue ((k, poly)
    forall a. HasCallStack => a
    undefined :: (k,poly))
                            (u :: UPoly k
    u,v :: UPoly k
    v,d :: UPoly k
    d@(UP [c :: k
    c])) = UPoly k -> UPoly k -> (UPoly k, UPoly k, UPoly k)
    forall k.
    (Eq k, Fractional k) =>
    UPoly k -> UPoly k -> (UPoly k, UPoly k, UPoly k)
    extendedEuclidUP UPoly k
    f UPoly k
    g
                            -- so u*f + v*g == d. We know the d is a unit, ie field element, since g is irreducible

                        in UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (UPoly k -> ExtensionField k poly)
    -> UPoly k -> ExtensionField k poly
    forall a b. (a -> b) -> a -> b
    $ (k
    c k -> UPoly k -> UPoly k
    forall a. (Eq a, Fractional a) => a -> UPoly a -> UPoly a
    /> UPoly k
    u) UPoly k -> UPoly k -> UPoly k
    forall k. (Eq k, Fractional k) => UPoly k -> UPoly k -> UPoly k
    `modUP` UPoly k
    g
        fromRational :: Rational -> ExtensionField k poly
    fromRational q :: Rational
    q = Integer -> ExtensionField k poly
    forall a. Num a => Integer -> a
    fromInteger Integer
    a ExtensionField k poly
    -> ExtensionField k poly -> ExtensionField k poly
    forall a. Fractional a => a -> a -> a
    / Integer -> ExtensionField k poly
    forall a. Num a => Integer -> a
    fromInteger Integer
    b where a :: Integer
    a = Rational -> Integer
    forall a. Ratio a -> a
    numerator Rational
    q; b :: Integer
    b = Rational -> Integer
    forall a. Ratio a -> a
    denominator Rational
    q

    -- divide through

    c :: a
    c /> :: a -> UPoly a -> UPoly a
    /> f :: UPoly a
    f@(UP as :: [a]
    as) | a
    c a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1 = UPoly a
    f
                   | a
    c a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    /= 0 = [a] -> UPoly a
    forall a. [a] -> UPoly a
    UP ((a -> a) -> [a] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (a
    c' a -> a -> a
    forall a. Num a => a -> a -> a
    *) [a]
    as) where c' :: a
    c' = a -> a
    forall a. Fractional a => a -> a
    recip a
    c

    instance (FiniteField k, PolynomialAsType k poly) => FiniteField (ExtensionField k poly) where
        eltsFq :: ExtensionField k poly -> [ExtensionField k poly]
    eltsFq _ = (UPoly k -> ExtensionField k poly)
    -> [UPoly k] -> [ExtensionField k poly]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Int -> [k] -> [UPoly k]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys (Int
    dInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -1) [k]
    fp) where
            fp :: [k]
    fp = k -> [k]
    forall fq. FiniteField fq => fq -> [fq]
    eltsFq (k
    forall a. HasCallStack => a
    undefined :: k)
            d :: Int
    d = UPoly k -> Int
    forall a. UPoly a -> Int
    deg (UPoly k -> Int) -> UPoly k -> Int
    forall a b. (a -> b) -> a -> b
    $ (k, poly) -> UPoly k
    forall k poly. PolynomialAsType k poly => (k, poly) -> UPoly k
    pvalue ((k, poly)
    forall a. HasCallStack => a
    undefined :: (k,poly))
        basisFq :: ExtensionField k poly -> [ExtensionField k poly]
    basisFq _ = (UPoly Integer -> ExtensionField k poly)
    -> [UPoly Integer] -> [ExtensionField k poly]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly Integer -> ExtensionField k poly
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed ([UPoly Integer] -> [ExtensionField k poly])
    -> [UPoly Integer] -> [ExtensionField k poly]
    forall a b. (a -> b) -> a -> b
    $ Int -> [UPoly Integer] -> [UPoly Integer]
    forall a. Int -> [a] -> [a]
    take (Int
    dInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -1) ([UPoly Integer] -> [UPoly Integer])
    -> [UPoly Integer] -> [UPoly Integer]
    forall a b. (a -> b) -> a -> b
    $ (UPoly Integer -> UPoly Integer)
    -> UPoly Integer -> [UPoly Integer]
    forall a. (a -> a) -> a -> [a]
    iterate (UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    *UPoly Integer
    x) 1 where
            d :: Int
    d = UPoly k -> Int
    forall a. UPoly a -> Int
    deg (UPoly k -> Int) -> UPoly k -> Int
    forall a b. (a -> b) -> a -> b
    $ (k, poly) -> UPoly k
    forall k poly. PolynomialAsType k poly => (k, poly) -> UPoly k
    pvalue ((k, poly)
    forall a. HasCallStack => a
    undefined :: (k,poly))

    -- Not sure if Eq fp is required, need to check with ghc >= 7.4.1

    instance (FinSet fp, Eq fp, Num fp, PolynomialAsType fp poly) => FinSet (ExtensionField fp poly) where
        elts :: [ExtensionField fp poly]
    elts = (UPoly fp -> ExtensionField fp poly)
    -> [UPoly fp] -> [ExtensionField fp poly]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly fp -> ExtensionField fp poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Int -> [fp] -> [UPoly fp]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys (Int
    dInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -1) [fp]
    fp') where
            fp' :: [fp]
    fp' = [fp]
    forall x. FinSet x => [x]
    elts
            d :: Int
    d = UPoly fp -> Int
    forall a. UPoly a -> Int
    deg (UPoly fp -> Int) -> UPoly fp -> Int
    forall a b. (a -> b) -> a -> b
    $ (fp, poly) -> UPoly fp
    forall k poly. PolynomialAsType k poly => (k, poly) -> UPoly k
    pvalue ((fp, poly)
    forall a. HasCallStack => a
    undefined :: (fp,poly))

    embed :: UPoly Integer -> ExtensionField k poly
    embed f :: UPoly Integer
    f = UPoly k -> ExtensionField k poly
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (UPoly Integer -> UPoly k
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert UPoly Integer
    f)

    -- PRIME POWER FINITE FIELDS

    polys :: t -> [a] -> [UPoly a]
    polys d :: t
    d fp :: [a]
    fp = ([a] -> UPoly a) -> [[a]] -> [UPoly a]
    forall a b. (a -> b) -> [a] -> [b]
    map [a] -> UPoly a
    forall a. (Eq a, Num a) => [a] -> UPoly a
    toUPoly ([[a]] -> [UPoly a]) -> [[a]] -> [UPoly a]
    forall a b. (a -> b) -> a -> b
    $ t -> [[a]]
    forall t. (Eq t, Num t) => t -> [[a]]
    polys' t
    d where
        polys' :: t -> [[a]]
    polys' 0 = [[]]
        polys' d :: t
    d = [a
    xa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    xs | a
    x <- [a]
    fp, [a]
    xs <- t -> [[a]]
    polys' (t
    dt -> t -> t
    forall a. Num a => a -> a -> a
    -1)] -- return in ascending order

        -- polys' d = [x:xs | xs <- polys' (d-1), x <- fp] -- return with elts of fp first

    -- Conway polynomials from Holt, Handbook of Computational Group Theory, p60

    data ConwayF4
    instance PolynomialAsType F2 ConwayF4 where pvalue :: (F2, ConwayF4) -> UPoly F2
    pvalue _ = UPoly Integer -> UPoly F2
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F2) -> UPoly Integer -> UPoly F2
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^2UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +UPoly Integer
    xUPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +1
    type F4 = ExtensionField F2 ConwayF4
    f4 :: [F4]
    f4 = (UPoly F2 -> F4) -> [UPoly F2] -> [F4]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F2 -> F4
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F2] -> [UPoly F2]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 2 [F2]
    f2) :: [F4]
    a4 :: F4
    a4 = UPoly Integer -> F4
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F4

    data ConwayF8
    instance PolynomialAsType F2 ConwayF8 where pvalue :: (F2, ConwayF8) -> UPoly F2
    pvalue _ = UPoly Integer -> UPoly F2
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F2) -> UPoly Integer -> UPoly F2
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^3UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +UPoly Integer
    xUPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +1
    type F8 = ExtensionField F2 ConwayF8
    f8 :: [F8]
    f8 = (UPoly F2 -> F8) -> [UPoly F2] -> [F8]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F2 -> F8
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F2] -> [UPoly F2]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 3 [F2]
    f2) :: [F8]
    a8 :: F8
    a8 = UPoly Integer -> F8
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F8

    data ConwayF9
    instance PolynomialAsType F3 ConwayF9 where pvalue :: (F3, ConwayF9) -> UPoly F3
    pvalue _ = UPoly Integer -> UPoly F3
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F3) -> UPoly Integer -> UPoly F3
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^2UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +2UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    *UPoly Integer
    xUPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +2
    type F9 = ExtensionField F3 ConwayF9
    f9 :: [F9]
    f9 = (UPoly F3 -> F9) -> [UPoly F3] -> [F9]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F3 -> F9
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F3] -> [UPoly F3]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 2 [F3]
    f3) :: [F9]
    a9 :: F9
    a9 = UPoly Integer -> F9
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F9

    data ConwayF16
    instance PolynomialAsType F2 ConwayF16 where pvalue :: (F2, ConwayF16) -> UPoly F2
    pvalue _ = UPoly Integer -> UPoly F2
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F2) -> UPoly Integer -> UPoly F2
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^4UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +UPoly Integer
    xUPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +1
    type F16 = ExtensionField F2 ConwayF16
    f16 :: [F16]
    f16 = (UPoly F2 -> F16) -> [UPoly F2] -> [F16]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F2 -> F16
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F2] -> [UPoly F2]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 4 [F2]
    f2) :: [F16]
    a16 :: F16
    a16 = UPoly Integer -> F16
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F16

    data ConwayF25
    instance PolynomialAsType F5 ConwayF25 where pvalue :: (F5, ConwayF25) -> UPoly F5
    pvalue _ = UPoly Integer -> UPoly F5
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F5) -> UPoly Integer -> UPoly F5
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^2UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +4UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    *UPoly Integer
    xUPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +2
    type F25 = ExtensionField F5 ConwayF25
    f25 :: [F25]
    f25 = (UPoly F5 -> F25) -> [UPoly F5] -> [F25]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F5 -> F25
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F5] -> [UPoly F5]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 2 [F5]
    f5) :: [F25]
    a25 :: F25
    a25 = UPoly Integer -> F25
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F25

    data ConwayF27
    instance PolynomialAsType F3 ConwayF27 where pvalue :: (F3, ConwayF27) -> UPoly F3
    pvalue _ = UPoly Integer -> UPoly F3
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F3) -> UPoly Integer -> UPoly F3
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^3UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +2UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    *UPoly Integer
    xUPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +1
    type F27 = ExtensionField F3 ConwayF27
    f27 :: [F27]
    f27 = (UPoly F3 -> F27) -> [UPoly F3] -> [F27]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F3 -> F27
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F3] -> [UPoly F3]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 3 [F3]
    f3) :: [F27]
    a27 :: F27
    a27 = UPoly Integer -> F27
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F27

    data ConwayF32
    instance PolynomialAsType F2 ConwayF32 where pvalue :: (F2, ConwayF32) -> UPoly F2
    pvalue _ = UPoly Integer -> UPoly F2
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly F2) -> UPoly Integer -> UPoly F2
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^5UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^2UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    +1
    type F32 = ExtensionField F2 ConwayF32
    f32 :: [F32]
    f32 = (UPoly F2 -> F32) -> [UPoly F2] -> [F32]
    forall a b. (a -> b) -> [a] -> [b]
    map UPoly F2 -> F32
    forall k poly. UPoly k -> ExtensionField k poly
    Ext (Integer -> [F2] -> [UPoly F2]
    forall a t. (Eq a, Eq t, Num a, Num t) => t -> [a] -> [UPoly a]
    polys 5 [F2]
    f2) :: [F32]
    a32 :: F32
    a32 = UPoly Integer -> F32
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: F32

    -- generator for the automorphism group of fq, as applied to an element of fq

    frobeniusAut :: a -> a
    frobeniusAut x :: a
    x = a
    x a -> Int -> a
    forall a b. (Num a, Integral b) => a -> b -> a
    ^ Int
    p where
        p :: Int
    p = [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    char ([a] -> Int) -> [a] -> Int
    forall a b. (a -> b) -> a -> b
    $ a -> [a]
    forall fq. FiniteField fq => fq -> [fq]
    eltsFq a
    x

    -- the degree of fq as an extension over fp

    -- (hence also, the order of the automorphism group of fq)

    degree :: t a -> Int
    degree fq :: t a
    fq = Int
    n where
        q :: Int
    q = t a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length t a
    fq
        p :: Int
    p = t a -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    char t a
    fq
        Just n :: Int
    n = Int -> [Int] -> Maybe Int
    forall a. Eq a => a -> [a] -> Maybe Int
    L.elemIndex Int
    q ([Int] -> Maybe Int) -> [Int] -> Maybe Int
    forall a b. (a -> b) -> a -> b
    $ (Int -> Int) -> Int -> [Int]
    forall a. (a -> a) -> a -> [a]
    iterate (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    p) 1

    -- QUADRATIC EXTENSIONS OF Q

    data Sqrt a = Sqrt a

    -- n should be square-free

    instance IntegerAsType n => PolynomialAsType Q (Sqrt n) where
        pvalue :: (Q, Sqrt n) -> UPoly Q
    pvalue _ = UPoly Integer -> UPoly Q
    forall a. (Eq a, Num a) => UPoly Integer -> UPoly a
    convert (UPoly Integer -> UPoly Q) -> UPoly Integer -> UPoly Q
    forall a b. (a -> b) -> a -> b
    $ UPoly Integer
    xUPoly Integer -> Integer -> UPoly Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^2 UPoly Integer -> UPoly Integer -> UPoly Integer
    forall a. Num a => a -> a -> a
    - Integer -> UPoly Integer
    forall a. Num a => Integer -> a
    fromInteger (n -> Integer
    forall a. IntegerAsType a => a -> Integer
    value (n
    forall a. HasCallStack => a
    undefined :: n))

    type QSqrt2 = ExtensionField Q (Sqrt T2)
    sqrt2 :: QSqrt2
    sqrt2 = UPoly Integer -> QSqrt2
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrt2

    type QSqrt3 = ExtensionField Q (Sqrt T3)
    sqrt3 :: QSqrt3
    sqrt3 = UPoly Integer -> QSqrt3
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrt3

    type QSqrt5 = ExtensionField Q (Sqrt T5)
    sqrt5 :: QSqrt5
    sqrt5 = UPoly Integer -> QSqrt5
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrt5

    type QSqrt7 = ExtensionField Q (Sqrt T7)
    sqrt7 :: QSqrt7
    sqrt7 = UPoly Integer -> QSqrt7
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrt7

    type QSqrtMinus1 = ExtensionField Q (Sqrt TMinus1)
    i :: QSqrtMinus1
    i = UPoly Integer -> QSqrtMinus1
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrtMinus1

    type QSqrtMinus2 = ExtensionField Q (Sqrt (M TMinus1 T2))
    sqrtminus2 :: QSqrtMinus2
    sqrtminus2 = UPoly Integer -> QSqrtMinus2
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrtMinus2

    type QSqrtMinus3 = ExtensionField Q (Sqrt (M TMinus1 T3))
    sqrtminus3 :: QSqrtMinus3
    sqrtminus3 = UPoly Integer -> QSqrtMinus3
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrtMinus3

    type QSqrtMinus5 = ExtensionField Q (Sqrt (M TMinus1 T5))
    sqrtminus5 :: QSqrtMinus5
    sqrtminus5 = UPoly Integer -> QSqrtMinus5
    forall k poly.
    (Eq k, Num k) =>
    UPoly Integer -> ExtensionField k poly
    embed UPoly Integer
    x :: QSqrtMinus5

    -- conjugation automorphism of quadratic field

    -- conjugate of a + b sqrt d is a - b sqrt d

    conjugate :: ExtensionField Q (Sqrt d) -> ExtensionField Q (Sqrt d)
    conjugate :: ExtensionField Q (Sqrt d) -> ExtensionField Q (Sqrt d)
    conjugate (Ext (UP [a :: Q
    a,b :: Q
    b])) = UPoly Q -> ExtensionField Q (Sqrt d)
    forall k poly. UPoly k -> ExtensionField k poly
    Ext ([Q] -> UPoly Q
    forall a. [a] -> UPoly a
    UP [Q
    a,-Q
    b])
    conjugate x :: ExtensionField Q (Sqrt d)
    x = ExtensionField Q (Sqrt d)
    x -- the zero or constant cases