{-# 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
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)
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 :: 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
| 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
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)))
as :: [a]
as <+> :: [a] -> [a] -> [a]
<+> [] = [a]
as
[] <+> bs :: [a]
bs = [a]
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
[] <*> :: [a] -> [a] -> [a]
<*> _ = []
_ <*> [] = []
(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)
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
deg :: UPoly a -> Int
deg (UP as :: [a]
as) = [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as
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]
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 :: 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
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 :: 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)
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
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
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))
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)
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)]
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
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
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
data Sqrt a = Sqrt a
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
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