galois-field 0.1.0 → 0.2.0

raw patch · 12 files changed

+607/−401 lines, 12 filesdep +MonadRandomdep +wl-pprint-textPVP ok

version bump matches the API change (PVP)

Dependencies added: MonadRandom, wl-pprint-text

API changes (from Hackage documentation)

Files

• ChangeLog.md +15/−1
• README.md +2/−2
• benchmarks/Benchmarks.hs +0/−184
• benchmarks/Main.hs +194/−2
• galois-field.cabal +32/−31
• src/ExtensionField.hs +79/−19
• src/GaloisField.hs +22/−4
• src/PolynomialRing.hs +67/−60
• src/PrimeField.hs +35/−8
• tests/ExtensionFieldTests.hs +91/−54
• tests/PolynomialRingTests.hs +27/−20
• tests/PrimeFieldTests.hs +43/−16

@@ -1,4 +1,18 @@-# Changelog for galois-field+# Change log for galois-field++## 0.2.0++* Add `deg` for GaloisField+* Add `order` for GaloisField+* Add `pow` for GaloisField+* Add `rnd` for GaloisField++## 0.1.1++* Add `Arbitrary` instances to PrimeField, PolynomialRing, and ExtensionField.+* Add `Bits` instances to PrimeField.+* Add `Pretty` instances to PrimeField, PolynomialRing, and ExtensionField.+* Minor optimisations to multiplication and inversion with `INLINE`.  ## 0.1.0 

@@ -67,8 +67,8 @@ The following data type declaration creates a splitting polynomial given an irreducible monic polynomial. ```haskell data P2-instance IrreducibleMonic Fq P2-  where split _ = x^2 + 1+instance IrreducibleMonic Fq P2 where+  split _ = x^2 + 1 ``` The following type declaration then creates an extension field with this splitting polynomial. ```haskell

@@ -1,184 +0,0 @@-module Benchmarks where--import Protolude--import Criterion.Main--import ExtensionField-import PrimeField--type Fq = PrimeField 21888242871839275222246405745257275088696311157297823662689037894645226208583--fq :: Fq-fq = 5216004179354450092383934373463611881445186046129513844852096383579774061693--fq' :: Fq-fq' = 10757805228921058098980668000791497318123219899766237205512608761387909753942--data Pu-instance IrreducibleMonic Fq Pu where split _ = x^2 + 1-type Fq2 = ExtensionField Fq Pu--fq2 :: Fq2-fq2 = fromList-  [ 19908898611787582971615951530393785823319364696376311494770162270472288380562-  , 2444690988583914246674870181013910409542697083717824402984851238236041783759-  ]--fq2' :: Fq2-fq2' = fromList-  [ 176307305890807650390915550856467756101144733976249050387177647283239486934-  , 9913547941088878400547309488585076816688958962210000330808066250849942240036-  ]--data Pv-instance IrreducibleMonic Fq2 Pv where split _ = x^3 - (9 + t x)-type Fq6 = ExtensionField Fq2 Pv--fq6 :: Fq6-fq6 = fromList-  [ fromList-    [ 8727269669017421992537561450387212506711577304101544328736696625792447584819-    , 14548604791762199086915107662335514800873255588931510951007415299299859294564-    ]-  , fromList-    [ 12226353852518517213098257637254082040554292743096797524265221809863992104040-    , 12690801089710533803594523982915673248220237967492611523932652691226365708512-    ]-  , fromList-    [ 18336930404004840796680535059992401039831316705513753839479258873269709495858-    , 21634580953983557175729336703450663797341055784728343534694506874757389871868-    ]-  ]--fq6' :: Fq6-fq6' = fromList-  [ fromList-    [ 21427158918811764040959407626476119248515601360702754918240300689672054041331-    , 12750457256357562507331331307761996193149796736574153338180573114576232473092-    ]-  , fromList-    [ 19307896751125425658868292427117755307914453765471505616446813557567103424424-    , 11511704315039881938763578963465960361806962511008317843374696569679546862720-    ]-  , fromList-    [ 16856354813335682789816416666746807604324955216244680818919639213184967817815-    , 10563739714379631354612735346769824530666877338817980746884577737330686430079-    ]-  ]--data Pw-instance IrreducibleMonic Fq6 Pw where split _ = x^2 - t x-type Fq12 = ExtensionField Fq6 Pw--fq12 :: Fq12-fq12 = fromList-  [ fromList-    [ fromList-      [ 4025484419428246835913352650763180341703148406593523188761836807196412398582-      , 5087667423921547416057913184603782240965080921431854177822601074227980319916-      ]-    , fromList-      [ 8868355606921194740459469119392835913522089996670570126495590065213716724895-      , 12102922015173003259571598121107256676524158824223867520503152166796819430680-      ]-    , fromList-      [ 92336131326695228787620679552727214674825150151172467042221065081506740785-      , 5482141053831906120660063289735740072497978400199436576451083698548025220729-      ]-    ]-  , fromList-    [ fromList-      [ 7642691434343136168639899684817459509291669149586986497725240920715691142493-      , 1211355239100959901694672926661748059183573115580181831221700974591509515378-      ]-    , fromList-      [ 20725578899076721876257429467489710434807801418821512117896292558010284413176-      , 17642016461759614884877567642064231230128683506116557502360384546280794322728-      ]-    , fromList-      [ 17449282511578147452934743657918270744212677919657988500433959352763226500950-      , 1205855382909824928004884982625565310515751070464736233368671939944606335817-      ]-    ]-  ]--fq12' :: Fq12-fq12' = fromList-  [ fromList-    [ fromList-      [ 495492586688946756331205475947141303903957329539236899715542920513774223311-      , 9283314577619389303419433707421707208215462819919253486023883680690371740600-      ]-    , fromList-      [ 11142072730721162663710262820927009044232748085260948776285443777221023820448-      , 1275691922864139043351956162286567343365697673070760209966772441869205291758-      ]-    , fromList-      [ 20007029371545157738471875537558122753684185825574273033359718514421878893242-      , 9839139739201376418106411333971304469387172772449235880774992683057627654905-      ]-    ]-  , fromList-    [ fromList-      [ 9503058454919356208294350412959497499007919434690988218543143506584310390240-      , 19236630380322614936323642336645412102299542253751028194541390082750834966816-      ]-    , fromList-      [ 18019769232924676175188431592335242333439728011993142930089933693043738917983-      , 11549213142100201239212924317641009159759841794532519457441596987622070613872-      ]-    , fromList-      [ 9656683724785441232932664175488314398614795173462019188529258009817332577664-      , 20666848762667934776817320505559846916719041700736383328805334359135638079015-      ]-    ]-  ]--benchmarks :: Benchmark-benchmarks = bgroup "GaloisField"-  [ bgroup "PrimeField"-    [ bgroup "Fq"-      [ bench "Addition"-        $ whnf (uncurry (+)) (fq, fq')-      , bench "Subtraction"-        $ whnf (uncurry (-)) (fq, fq')-      , bench "Multiplication"-        $ whnf (uncurry (*)) (fq, fq')-      , bench "Division"-        $ whnf (uncurry (/)) (fq, fq')-      ]-    ]-  , bgroup "ExtensionField"-    [ bgroup "Fq2"-      [ bench "Addition"-        $ whnf (uncurry (+)) (fq2, fq2')-      , bench "Subtraction"-        $ whnf (uncurry (-)) (fq2, fq2')-      , bench "Multiplication"-        $ whnf (uncurry (*)) (fq2, fq2')-      , bench "Division"-        $ whnf (uncurry (/)) (fq2, fq2')-      ]-    , bgroup "Fq6"-      [ bench "Addition"-        $ whnf (uncurry (+)) (fq6, fq6')-      , bench "Subtraction"-        $ whnf (uncurry (-)) (fq6, fq6')-      , bench "Multiplication"-        $ whnf (uncurry (*)) (fq6, fq6')-      , bench "Division"-        $ whnf (uncurry (/)) (fq6, fq6')-      ]-    , bgroup "Fq12"-      [ bench "Addition"-        $ whnf (uncurry (+)) (fq12, fq12')-      , bench "Subtraction"-        $ whnf (uncurry (-)) (fq12, fq12')-      , bench "Multiplication"-        $ whnf (uncurry (*)) (fq12, fq12')-      , bench "Division"-        $ whnf (uncurry (/)) (fq12, fq12')-      ]-    ]-  ]

@@ -3,8 +3,200 @@ import Protolude  import Criterion.Main+import ExtensionField+import PrimeField -import Benchmarks+type Fq = PrimeField 21888242871839275222246405745257275088696311157297823662689037894645226208583 +fq :: Fq+fq = 5216004179354450092383934373463611881445186046129513844852096383579774061693++fq' :: Fq+fq' = 10757805228921058098980668000791497318123219899766237205512608761387909753942++data Pu+instance IrreducibleMonic Fq Pu where+  split _ = x^2 + 1+type Fq2 = ExtensionField Fq Pu++fq2 :: Fq2+fq2 = fromList+  [ 19908898611787582971615951530393785823319364696376311494770162270472288380562+  , 2444690988583914246674870181013910409542697083717824402984851238236041783759+  ]++fq2' :: Fq2+fq2' = fromList+  [ 176307305890807650390915550856467756101144733976249050387177647283239486934+  , 9913547941088878400547309488585076816688958962210000330808066250849942240036+  ]++data Pv+instance IrreducibleMonic Fq2 Pv where+  split _ = x^3 - (9 + t x)+type Fq6 = ExtensionField Fq2 Pv++fq6 :: Fq6+fq6 = fromList+  [ fromList+    [ 8727269669017421992537561450387212506711577304101544328736696625792447584819+    , 14548604791762199086915107662335514800873255588931510951007415299299859294564+    ]+  , fromList+    [ 12226353852518517213098257637254082040554292743096797524265221809863992104040+    , 12690801089710533803594523982915673248220237967492611523932652691226365708512+    ]+  , fromList+    [ 18336930404004840796680535059992401039831316705513753839479258873269709495858+    , 21634580953983557175729336703450663797341055784728343534694506874757389871868+    ]+  ]++fq6' :: Fq6+fq6' = fromList+  [ fromList+    [ 21427158918811764040959407626476119248515601360702754918240300689672054041331+    , 12750457256357562507331331307761996193149796736574153338180573114576232473092+    ]+  , fromList+    [ 19307896751125425658868292427117755307914453765471505616446813557567103424424+    , 11511704315039881938763578963465960361806962511008317843374696569679546862720+    ]+  , fromList+    [ 16856354813335682789816416666746807604324955216244680818919639213184967817815+    , 10563739714379631354612735346769824530666877338817980746884577737330686430079+    ]+  ]++data Pw+instance IrreducibleMonic Fq6 Pw where+  split _ = x^2 - t x+type Fq12 = ExtensionField Fq6 Pw++fq12 :: Fq12+fq12 = fromList+  [ fromList+    [ fromList+      [ 4025484419428246835913352650763180341703148406593523188761836807196412398582+      , 5087667423921547416057913184603782240965080921431854177822601074227980319916+      ]+    , fromList+      [ 8868355606921194740459469119392835913522089996670570126495590065213716724895+      , 12102922015173003259571598121107256676524158824223867520503152166796819430680+      ]+    , fromList+      [ 92336131326695228787620679552727214674825150151172467042221065081506740785+      , 5482141053831906120660063289735740072497978400199436576451083698548025220729+      ]+    ]+  , fromList+    [ fromList+      [ 7642691434343136168639899684817459509291669149586986497725240920715691142493+      , 1211355239100959901694672926661748059183573115580181831221700974591509515378+      ]+    , fromList+      [ 20725578899076721876257429467489710434807801418821512117896292558010284413176+      , 17642016461759614884877567642064231230128683506116557502360384546280794322728+      ]+    , fromList+      [ 17449282511578147452934743657918270744212677919657988500433959352763226500950+      , 1205855382909824928004884982625565310515751070464736233368671939944606335817+      ]+    ]+  ]++fq12' :: Fq12+fq12' = fromList+  [ fromList+    [ fromList+      [ 495492586688946756331205475947141303903957329539236899715542920513774223311+      , 9283314577619389303419433707421707208215462819919253486023883680690371740600+      ]+    , fromList+      [ 11142072730721162663710262820927009044232748085260948776285443777221023820448+      , 1275691922864139043351956162286567343365697673070760209966772441869205291758+      ]+    , fromList+      [ 20007029371545157738471875537558122753684185825574273033359718514421878893242+      , 9839139739201376418106411333971304469387172772449235880774992683057627654905+      ]+    ]+  , fromList+    [ fromList+      [ 9503058454919356208294350412959497499007919434690988218543143506584310390240+      , 19236630380322614936323642336645412102299542253751028194541390082750834966816+      ]+    , fromList+      [ 18019769232924676175188431592335242333439728011993142930089933693043738917983+      , 11549213142100201239212924317641009159759841794532519457441596987622070613872+      ]+    , fromList+      [ 9656683724785441232932664175488314398614795173462019188529258009817332577664+      , 20666848762667934776817320505559846916719041700736383328805334359135638079015+      ]+    ]+  ]+ main :: IO ()-main = defaultMain [benchmarks]+main = defaultMain+  [ bgroup "PrimeField"+    [ bgroup "Fq"+      [ bench "Addition"+        $ whnf (uncurry (+)) (fq, fq')+      , bench "Multiplication"+        $ whnf (uncurry (*)) (fq, fq')+      , bench "Negation"+        $ whnf negate fq+      , bench "Subtraction"+        $ whnf (uncurry (-)) (fq, fq')+      , bench "Inversion"+        $ whnf recip fq+      , bench "Division"+        $ whnf (uncurry (/)) (fq, fq')+      ]+    ]+  , bgroup "ExtensionField"+    [ bgroup "Fq2"+      [ bench "Addition"+        $ whnf (uncurry (+)) (fq2, fq2')+      , bench "Multiplication"+        $ whnf (uncurry (*)) (fq2, fq2')+      , bench "Negation"+        $ whnf negate fq2+      , bench "Subtraction"+        $ whnf (uncurry (-)) (fq2, fq2')+      , bench "Inversion"+        $ whnf recip fq2+      , bench "Division"+        $ whnf (uncurry (/)) (fq2, fq2')+      ]+    , bgroup "Fq6"+      [ bench "Addition"+        $ whnf (uncurry (+)) (fq6, fq6')+      , bench "Multiplication"+        $ whnf (uncurry (*)) (fq6, fq6')+      , bench "Negation"+        $ whnf negate fq6+      , bench "Subtraction"+        $ whnf (uncurry (-)) (fq6, fq6')+      , bench "Inversion"+        $ whnf recip fq6+      , bench "Division"+        $ whnf (uncurry (/)) (fq6, fq6')+      ]+    , bgroup "Fq12"+      [ bench "Addition"+        $ whnf (uncurry (+)) (fq12, fq12')+      , bench "Multiplication"+        $ whnf (uncurry (*)) (fq12, fq12')+      , bench "Negation"+        $ whnf negate fq12+      , bench "Subtraction"+        $ whnf (uncurry (-)) (fq12, fq12')+      , bench "Inversion"+        $ whnf recip fq12+      , bench "Division"+        $ whnf (uncurry (/)) (fq12, fq12')+      ]+    ]+  ]

@@ -2,12 +2,12 @@ -- -- see: https://github.com/sol/hpack ----- hash: 86cbd60c516785b91dbc82303018451a9a632edd09640a077a30faab5d3b4991+-- hash: f66dcf977899a69f9f8785c75595dada58f68cbc1cb35faa4acb24b494fe26fe  name:           galois-field-version:        0.1.0-synopsis:       Galois field-description:    Finite field library+version:        0.2.0+synopsis:       Galois field library+description:    Galois field library for cryptography research category:       Cryptography homepage:       https://github.com/adjoint-io/galois-field#readme bug-reports:    https://github.com/adjoint-io/galois-field/issues@@ -24,16 +24,6 @@   type: git   location: https://github.com/adjoint-io/galois-field -flag optimized-  description: Perform compiler optimizations-  manual: False-  default: False--flag static-  description: Emit statically-linked binary-  manual: False-  default: False- library   exposed-modules:       GaloisField@@ -44,54 +34,65 @@   hs-source-dirs:       src   default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses-  ghc-options: -Wall+  ghc-options: -O2 -Wall   build-depends:-      base >=4.7 && <5+      MonadRandom+    , base >=4.7 && <5     , integer-gmp     , protolude >=0.2+    , tasty-quickcheck+    , wl-pprint-text   default-language: Haskell2010 -test-suite tests+test-suite galois-field-tests   type: exitcode-stdio-1.0   main-is: Main.hs   other-modules:-      GaloisField-      PrimeField-      PolynomialRing-      ExtensionField+      ExtensionFieldTests       GaloisFieldTests-      PrimeFieldTests       PolynomialRingTests-      ExtensionFieldTests+      PrimeFieldTests+      ExtensionField+      GaloisField+      PolynomialRing+      PrimeField+      Paths_galois_field   hs-source-dirs:-      src       tests+      src   default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses+  ghc-options: -O2 -main-is Main   build-depends:-      base >=4.7 && <5+      MonadRandom+    , base >=4.7 && <5     , integer-gmp     , protolude >=0.2     , tasty     , tasty-discover     , tasty-quickcheck+    , wl-pprint-text   default-language: Haskell2010 -benchmark benchmarks+benchmark galois-field-benchmarks   type: exitcode-stdio-1.0   main-is: Main.hs   other-modules:+      ExtensionField       GaloisField-      PrimeField       PolynomialRing-      ExtensionField-      Benchmarks+      PrimeField+      Paths_galois_field   hs-source-dirs:-      src       benchmarks+      src   default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses+  ghc-options: -O2 -main-is Main   build-depends:-      base >=4.7 && <5+      MonadRandom+    , base >=4.7 && <5     , criterion     , integer-gmp     , protolude >=0.2+    , tasty-quickcheck+    , wl-pprint-text   default-language: Haskell2010

@@ -9,53 +9,113 @@  import Protolude +import Control.Monad.Random (Random(..), getRandom)+import Test.Tasty.QuickCheck (Arbitrary(..), choose, sized)+import Text.PrettyPrint.Leijen.Text (Pretty(..))+ import GaloisField (GaloisField(..))-import PolynomialRing (Polynomial(..), polyDiv, polyInv, toPoly)+import PolynomialRing (Polynomial(..), cut, polyInv, polyMul, polyQR) +-- | Irreducible monic splitting polynomial of extension field+class IrreducibleMonic k im where+  {-# MINIMAL split #-}+  split :: ExtensionField k im -> Polynomial k -- ^ Splitting polynomial+ -- | Extension fields @GF(p^q)[X]/<f(X)>@ for @p@ prime, @q@ positive, and -- @f(X)@ irreducible monic in @GF(p^q)[X]@ newtype ExtensionField k im = EF (Polynomial k)   deriving (Eq, Generic, NFData, Show) --- | Irreducible monic splitting polynomial of extension field-class IrreducibleMonic k im where-  split :: (k, im) -> Polynomial k+-- | Extension fields are arbitrary+instance (Arbitrary k, GaloisField k, IrreducibleMonic k im)+  => Arbitrary (ExtensionField k im) where+  arbitrary = fromList <$> sized (const poly)+    where+      poly = choose (1, length xs - 1) >>= mapM (const arbitrary) . enumFromTo 1+        where+          X xs = split (witness :: ExtensionField k im)  -- | Extension fields are fields instance (GaloisField k, IrreducibleMonic k im)   => Fractional (ExtensionField k im) where-  recip (EF y)        = case polyInv y (split (witness :: (k, im))) of-    Just z -> EF z-    _      -> panic "no multiplicative inverse."+  recip (EF (X ys))   = case polyInv ys xs of+    Just zs -> EF (X zs)+    _       -> panic "no multiplicative inverse."+    where+      X xs = split (witness :: ExtensionField k im)   {-# INLINE recip #-}   fromRational (y:%z) = fromInteger y / fromInteger z+  {-# INLINABLE fromRational #-}  -- | Extension fields are Galois fields instance (GaloisField k, IrreducibleMonic k im)   => GaloisField (ExtensionField k im) where-  char = const (char (witness :: k))+  char          = const (char (witness :: k))+  {-# INLINE char #-}+  deg           = const (deg (witness :: k) * length xs - 1)+    where+      X xs = split (witness :: ExtensionField k im)+  {-# INLINE deg #-}+  pow y@(EF (X ys)) n+    | n < 0     = pow (recip y) (-n)+    | otherwise = EF (X (pow' [1] ys n))+    where+      X xs = split (witness :: ExtensionField k im)+      mul = (.) (snd . flip polyQR xs) . polyMul+      pow' ws zs m+        | m == 0    = ws+        | m == 1    = mul ws zs+        | even m    = pow' ws (mul zs zs) (div m 2)+        | otherwise = pow' (mul ws zs) (mul zs zs) (div m 2)+  {-# INLINE pow #-}+  rnd           = getRandom+  {-# INLINE rnd #-}  -- | Extension fields are rings instance (GaloisField k, IrreducibleMonic k im)   => Num (ExtensionField k im) where-  EF y + EF z   = EF (y + z)-  EF y * EF z   = EF (snd (polyDiv (y * z) (split (witness :: (k, im)))))-  EF y - EF z   = EF (y - z)-  negate (EF y) = EF (-y)-  fromInteger   = EF . fromInteger-  abs           = panic "not implemented."-  signum        = panic "not implemented."+  EF y + EF z           = EF (y + z)+  {-# INLINE (+) #-}+  EF (X ys) * EF (X zs) = EF (X (snd (polyQR (polyMul ys zs) xs)))+    where+      X xs = split (witness :: ExtensionField k im)+  {-# INLINE (*) #-}+  EF y - EF z           = EF (y - z)+  {-# INLINE (-) #-}+  negate (EF y)         = EF (-y)+  {-# INLINE negate #-}+  fromInteger           = EF . fromInteger+  {-# INLINABLE fromInteger #-}+  abs                   = panic "not implemented."+  signum                = panic "not implemented." +-- | Extension fields are pretty+instance (GaloisField k, IrreducibleMonic k im)+  => Pretty (ExtensionField k im) where+  pretty (EF y) = pretty y++-- | Extension fields are random+instance (GaloisField k, IrreducibleMonic k im)+  => Random (ExtensionField k im) where+  random  = first (EF . X . cut) . unfold (length xs - 1) []+    where+      X xs = split (witness :: ExtensionField k im)+      unfold n ys g = if n <= 0 then (ys, g) else+        let (y, g') = random g in unfold (n - 1) (y : ys) g'+  randomR = panic "not implemented."+ -- | List from field fromField :: ExtensionField k im -> [k]-fromField (EF (X ks)) = ks-{-# INLINE fromField #-}+fromField (EF (X xs)) = xs+{-# INLINABLE fromField #-}  -- | Field from list fromList :: forall k im . (GaloisField k, IrreducibleMonic k im)   => [k] -> ExtensionField k im-fromList = EF . snd . flip polyDiv (split (witness :: (k, im))) . toPoly-{-# INLINE fromList #-}+fromList = EF . X . snd . flip polyQR xs . cut+  where+    X xs = split (witness :: ExtensionField k im)+{-# INLINABLE fromList #-}  -- | Current indeterminate variable x :: GaloisField k => Polynomial k

@@ -4,8 +4,26 @@  import Protolude +import Control.Monad.Random (MonadRandom, Random)+import Test.Tasty.QuickCheck (Arbitrary)+import Text.PrettyPrint.Leijen.Text (Pretty)+ -- | Galois fields @GF(p^q)@ for @p@ prime and @q@ non-negative-class (Eq k, Fractional k, Show k) => GaloisField k where-  {-# MINIMAL char #-}-  -- | Characteristic of field-  char :: k -> Integer+class (Arbitrary k, Eq k, Fractional k, Pretty k, Random k, Show k)+  => GaloisField k where+  {-# MINIMAL char, deg, pow, rnd #-}++  -- Characteristics+  char :: k -> Integer  -- ^ Characteristic @q@ of field++  deg :: k -> Int       -- ^ Degree @q@ of field++  order :: k -> Integer -- ^ Order @p^q@ of field+  order = (^) <$> char <*> deg+  {-# INLINE order #-}++  -- Functions+  pow :: k -> Integer -> k -- @x@ to the power of @y@++  -- Randomisation+  rnd :: MonadRandom m => m k -- ^ Random element of field

@@ -1,97 +1,104 @@ module PolynomialRing   ( Polynomial(..)-  , degree-  , last-  , polyDiv+  , cut   , polyInv+  , polyMul+  , polyQR   , toPoly   ) where  import Protolude +import Test.Tasty.QuickCheck (Arbitrary(..))+import Text.PrettyPrint.Leijen.Text (Pretty(..))+ import GaloisField (GaloisField(..)) --- | Polynomial rings newtype Polynomial k = X [k]   deriving (Eq, Generic, NFData, Show) --- | Polynomial rings are rings+instance (Arbitrary k, GaloisField k) => Arbitrary (Polynomial k) where+  arbitrary = toPoly <$> arbitrary+ instance GaloisField k => Num (Polynomial k) where   X xs + X ys   = X (polyAdd xs ys)+  {-# INLINE (+) #-}   X xs * X ys   = X (polyMul xs ys)+  {-# INLINE (*) #-}+  X xs - X ys   = X (polySub xs ys)+  {-# INLINE (-) #-}   negate (X xs) = X (map negate xs)-  fromInteger   = fromInt+  {-# INLINE negate #-}+  fromInteger n = X (let m = fromInteger n in if m == 0 then [] else [m])+  {-# INLINABLE fromInteger #-}   abs           = panic "not implemented."   signum        = panic "not implemented." --- | Polynomial addition+instance GaloisField k => Pretty (Polynomial k) where+  pretty (X xs) = pretty xs+ polyAdd :: GaloisField k => [k] -> [k] -> [k]-polyAdd []     xs     = xs polyAdd xs     []     = xs-polyAdd (x:xs) (y:ys) = if z == 0 && null zs then [] else z : zs-  where-    z  = x + y-    zs = polyAdd xs ys+polyAdd []     ys     = ys+polyAdd (x:xs) (y:ys) = let z  = x + y+                            zs = polyAdd xs ys+                        in if z == 0 && null zs then [] else z : zs {-# INLINE polyAdd #-} --- | Polynomial multiplication polyMul :: GaloisField k => [k] -> [k] -> [k]-polyMul []     _  = [] polyMul _      [] = []-polyMul (x:xs) ys = if null xs then ws else polyAdd ws (0 : zs)-  where-    ws = map (* x) ys-    zs = polyMul xs ys+polyMul []     _  = []+polyMul (x:xs) ys = let ws = map (* x) ys+                        zs = polyMul xs ys+                    in if null xs then ws else polyAdd ws (0 : zs) {-# INLINE polyMul #-} --- | Polynomial from integer-fromInt :: GaloisField k => Integer -> Polynomial k-fromInt n = X (let m = fromInteger n in if m == 0 then [] else [m])-{-# INLINE fromInt #-}---- | Polynomial degree-degree :: Polynomial k -> Int-degree (X xs) = length xs-{-# INLINE degree #-}---- | Polynomial leading coefficient-last :: GaloisField k => Polynomial k -> k-last (X [])     = 0-last (X [x])    = x-last (X (_:xs)) = last (X xs)-{-# INLINE last #-}+polySub :: GaloisField k => [k] -> [k] -> [k]+polySub xs     []     = xs+polySub []     ys     = map negate ys+polySub (x:xs) (y:ys) = let z  = x - y+                            zs = polySub xs ys+                        in if z == 0 && null zs then [] else z : zs+{-# INLINE polySub #-} --- | Polynomial division-polyDiv :: forall k . GaloisField k-  => Polynomial k -> Polynomial k -> (Polynomial k, Polynomial k)-polyDiv ns ds = polyQR (0, ns)+polyQR :: forall k . GaloisField k => [k] -> [k] -> ([k], [k])+polyQR xs ys = polyGCD ([], xs)   where-    polyQR :: (Polynomial k, Polynomial k) -> (Polynomial k, Polynomial k)-    polyQR qr@(qs, rs)-      | degree rs < degree ds = qr-      | otherwise             = polyQR (qs + ts, rs - ts * ds)+    m :: Int+    m = length ys+    polyGCD :: ([k], [k]) -> ([k], [k])+    polyGCD qr@(qs, rs)+      | n < 0     = qr+      | otherwise = polyGCD (polyAdd qs ts, polySub rs (polyMul ts ys))       where-        ts = X (replicate (degree rs - degree ds) 0 ++ [last rs / last ds])-{-# INLINE polyDiv #-}+        n :: Int+        n = length rs - m+        ts :: [k]+        ts = replicate n 0 ++ [last rs / last ys]+        last :: [k] -> k+        last []     = 0+        last [z]    = z+        last (_:zs) = last zs+{-# INLINE polyQR #-} --- | Polynomial inversion-polyInv :: forall k . GaloisField k-  => Polynomial k -> Polynomial k -> Maybe (Polynomial k)-polyInv (X [x]) _ = Just (X [recip x])-polyInv xs ps     = case extGCD ps xs of-  (X [y], (X ys, _)) -> Just (X (map (/ y) ys))-  _                  -> Nothing+polyInv :: forall k . GaloisField k => [k] -> [k] -> Maybe [k]+polyInv [x] _ = Just [recip x]+polyInv xs ps = case extGCD (ps, xs) of+  ([y], (ys, _)) -> Just (map (/ y) ys)+  _              -> Nothing   where-    extGCD :: Polynomial k -> Polynomial k-      -> (Polynomial k, (Polynomial k, Polynomial k))-    extGCD y 0 = (y, (0, 1))-    extGCD y x = (g, (t - s * q, s))+    extGCD :: ([k], [k]) -> ([k], ([k], [k]))+    extGCD (y, []) = (y, ([], [1]))+    extGCD (y, x)  = (g, (polySub t (polyMul s q), s))       where-        (q, r)      = polyDiv y x-        (g, (s, t)) = extGCD x r+        (q, r)      = polyQR y x+        (g, (s, t)) = extGCD (x, r) {-# INLINE polyInv #-} --- | List to polynomial+cut :: GaloisField k => [k] -> [k]+cut = reverse . dropWhile (== 0) . reverse+{-# INLINABLE cut #-}+ toPoly :: GaloisField k => [k] -> Polynomial k-toPoly = X . reverse . dropWhile (== 0) . reverse-{-# INLINE toPoly #-}+toPoly = X . cut+{-# INLINABLE toPoly #-}

@@ -5,45 +5,72 @@  import Protolude -import GHC.Integer.GMP.Internals (recipModInteger)+import Control.Monad.Random (Random(..), getRandom)+import GHC.Integer.GMP.Internals (powModInteger, recipModInteger)+import Test.Tasty.QuickCheck (Arbitrary(..))+import Text.PrettyPrint.Leijen.Text (Pretty(..))  import GaloisField (GaloisField(..))  -- | Prime fields @GF(p)@ for @p@ prime newtype PrimeField (p :: Nat) = PF Integer-  deriving (Eq, Generic, NFData, Show)+  deriving (Bits, Eq, Generic, NFData, Show) +-- | Prime fields are arbitrary+instance KnownNat p => Arbitrary (PrimeField p) where+  arbitrary = fromInteger <$> arbitrary+ -- | Prime fields are fields instance KnownNat p => Fractional (PrimeField p) where   recip y@(PF x)      = PF (recipModInteger x (natVal y))+  {-# INLINE recip #-}   fromRational (x:%y) = fromInteger x / fromInteger y+  {-# INLINABLE fromRational #-}  -- | Prime fields are Galois fields instance KnownNat p => GaloisField (PrimeField p) where-  char = natVal+  char           = natVal+  {-# INLINE char #-}+  deg            = const 1+  {-# INLINE deg #-}+  pow y@(PF x) n = PF (powModInteger x n (natVal y))+  {-# INLINE pow #-}+  rnd            = getRandom+  {-# INLINE rnd #-}  -- | Prime fields are rings instance KnownNat p => Num (PrimeField p) where-  z@(PF x) + PF y = PF (if xy >= p then xy - p else xy)+  z@(PF x) + PF y = PF (if xyp >= 0 then xyp else xy)     where-      xy = x + y-      p  = natVal z+      xy  = x + y+      xyp = xy - natVal z   {-# INLINE (+) #-}   z@(PF x) * PF y = PF (rem (x * y) (natVal z))+  {-# INLINE (*) #-}   z@(PF x) - PF y = PF (if xy >= 0 then xy else xy + natVal z)     where       xy = x - y   {-# INLINE (-) #-}   negate y@(PF x) = PF (if x == 0 then 0 else -x + natVal y)+  {-# INLINE negate #-}   fromInteger x   = PF (if y >= 0 then y else y + p)     where       y = rem x p       p = natVal (witness :: PrimeField p)-  {-# INLINE fromInteger #-}+  {-# INLINABLE fromInteger #-}   abs             = panic "not implemented."   signum          = panic "not implemented." +-- | Prime fields are pretty+instance KnownNat p => Pretty (PrimeField p) where+  pretty (PF x) = pretty [x]++-- | Prime fields are random+instance KnownNat p => Random (PrimeField p) where+  random  = first PF . randomR (0, natVal (witness :: PrimeField p) - 1)+  randomR = panic "not implemented."+ -- | Embed to integers toInt :: PrimeField p -> Integer toInt (PF x) = x-{-# INLINE toInt #-}+{-# INLINABLE toInt #-}

@@ -2,82 +2,119 @@  import Protolude +import ExtensionField import Test.Tasty-import Test.Tasty.QuickCheck -import ExtensionField-import GaloisField import GaloisFieldTests-import PolynomialRing-import PolynomialRingTests-import PrimeField import PrimeFieldTests -instance (Arbitrary k, GaloisField k, IrreducibleMonic k ps)-  => Arbitrary (ExtensionField k ps) where-  arbitrary = fromList <$> sized (const poly)-    where-      poly = choose (1, degree (split (witness :: (k, ps))) - 1)-        >>= mapM (const arbitrary) . enumFromTo 1+data P11+instance IrreducibleMonic FS2 P11 where+  split _ = x^2 + x + 1+type FS4 = ExtensionField FS2 P11+test_S4 :: TestTree+test_S4 = fieldAxioms (Proxy :: Proxy FS4) "FS4" -type F2 = PrimeField 2-data P11; instance IrreducibleMonic F2 P11 where split _ = x^2 + x + 1-test_4 = fieldAxioms (Proxy :: Proxy (ExtensionField F2 P11)) "F4"-data P110; instance IrreducibleMonic F2 P110 where split _ = x^3 + x + 1-test_8 = fieldAxioms (Proxy :: Proxy (ExtensionField F2 P110)) "F8"-data P101; instance IrreducibleMonic F2 P101 where split _ = x^3 + x^2 + 1-test_8' = fieldAxioms (Proxy :: Proxy (ExtensionField F2 P110)) "F8'"+data P110+instance IrreducibleMonic FS2 P110 where+  split _ = x^3 + x + 1+type FS8 = ExtensionField FS2 P110+test_S8 :: TestTree+test_S8 = fieldAxioms (Proxy :: Proxy FS8) "FS8" -type F3 = PrimeField 3-data P10; instance IrreducibleMonic F3 P10 where split _ = x^2 + 1-test_9 = fieldAxioms (Proxy :: Proxy (ExtensionField F3 P10)) "F9"-data P21; instance IrreducibleMonic F3 P21 where split _ = x^2 + x - 1-test_9' = fieldAxioms (Proxy :: Proxy (ExtensionField F3 P21)) "F9'"-data P22; instance IrreducibleMonic F3 P22 where split _ = x^2 - x - 1-test_9'' = fieldAxioms (Proxy :: Proxy (ExtensionField F3 P22)) "F9''"+data P101+instance IrreducibleMonic FS2 P101 where+  split _ = x^3 + x^2 + 1+type FS8' = ExtensionField FS2 P101+test_S8' :: TestTree+test_S8' = fieldAxioms (Proxy :: Proxy FS8') "FS8'" -type FA = PrimeField 2147483647-instance IrreducibleMonic FA P10 where split _ = x^2 + 1-test_A = fieldAxioms (Proxy :: Proxy (ExtensionField FA P10)) "FA2"+data P10+instance IrreducibleMonic FS3 P10 where+  split _ = x^2 + 1+type FS9 = ExtensionField FS3 P10+test_S9 :: TestTree+test_S9 = fieldAxioms (Proxy :: Proxy FS9) "FS9" -type FB = PrimeField 2305843009213693951-instance IrreducibleMonic FB P10 where split _ = x^2 + 1-test_B = fieldAxioms (Proxy :: Proxy (ExtensionField FB P10)) "FB2"+data P21+instance IrreducibleMonic FS3 P21 where+  split _ = x^2 + x - 1+type FS9' = ExtensionField FS3 P21+test_S9' :: TestTree+test_S9' = fieldAxioms (Proxy :: Proxy FS9') "FS9'" -type FC = PrimeField 618970019642690137449562111-instance IrreducibleMonic FC P10 where split _ = x^2 + 1-test_C = fieldAxioms (Proxy :: Proxy (ExtensionField FC P10)) "FC2"+data P22+instance IrreducibleMonic FS3 P22 where+  split _ = x^2 - x - 1+type FS9'' = ExtensionField FS3 P22+test_S9'' :: TestTree+test_S9'' = fieldAxioms (Proxy :: Proxy FS9'') "FS9''" -type FD = PrimeField 162259276829213363391578010288127-instance IrreducibleMonic FD P10 where split _ = x^2 + 1-test_D = fieldAxioms (Proxy :: Proxy (ExtensionField FD P10)) "FD2"+instance IrreducibleMonic FM0 P10 where+  split _ = x^2 + 1+type FL0 = ExtensionField FM0 P10+test_L0 :: TestTree+test_L0 = fieldAxioms (Proxy :: Proxy FL0) "FL0" -type FE = PrimeField 170141183460469231731687303715884105727-instance IrreducibleMonic FE P10 where split _ = x^2 + 1-test_E = fieldAxioms (Proxy :: Proxy (ExtensionField FE P10)) "FE2"+instance IrreducibleMonic FM1 P10 where+  split _ = x^2 + 1+type FL1 = ExtensionField FM1 P10+test_L1 :: TestTree+test_L1 = fieldAxioms (Proxy :: Proxy FL1) "FL1" -type FV = PrimeField 20988936657440586486151264256610222593863921-instance IrreducibleMonic FV P10 where split _ = x^2 + 1-test_V = fieldAxioms (Proxy :: Proxy (ExtensionField FV P10)) "FV2"+instance IrreducibleMonic FM2 P10 where+  split _ = x^2 + 1+type FL2 = ExtensionField FM2 P10+test_L2 :: TestTree+test_L2 = fieldAxioms (Proxy :: Proxy FL2) "FL2" -type FX = PrimeField 5210644015679228794060694325390955853335898483908056458352183851018372555735221-instance IrreducibleMonic FX P10 where split _ = x^2 + 1-test_X = fieldAxioms (Proxy :: Proxy (ExtensionField FX P10)) "FX2"+instance IrreducibleMonic FM3 P10 where+  split _ = x^2 + 1+type FL3 = ExtensionField FM3 P10+test_L3 :: TestTree+test_L3 = fieldAxioms (Proxy :: Proxy FL3) "FL3" -type FZ = PrimeField 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737-instance IrreducibleMonic FZ P10 where split _ = x^2 + 1-test_Z = fieldAxioms (Proxy :: Proxy (ExtensionField FZ P10)) "FZ2"+instance IrreducibleMonic FM4 P10 where+  split _ = x^2 + 1+type FL4 = ExtensionField FM4 P10+test_L4 :: TestTree+test_L4 = fieldAxioms (Proxy :: Proxy FL4) "FL4" -type Fq = PrimeField 21888242871839275222246405745257275088696311157297823662689037894645226208583+instance IrreducibleMonic FVL P10 where+  split _ = x^2 + 1+type FV2 = ExtensionField FVL P10+test_V2 :: TestTree+test_V2 = fieldAxioms (Proxy :: Proxy FV2) "FV2"++instance IrreducibleMonic FXL P10 where+  split _ = x^2 + 1+type FX2 = ExtensionField FXL P10+test_X2 :: TestTree+test_X2 = fieldAxioms (Proxy :: Proxy FX2) "FX2"++instance IrreducibleMonic FZL P10 where+  split _ = x^2 + 1+type FZ2 = ExtensionField FZL P10+test_Z2 :: TestTree+test_Z2 = fieldAxioms (Proxy :: Proxy FZ2) "FZ2"+ data Pu-instance IrreducibleMonic Fq Pu where split _ = x^2 + 1+instance IrreducibleMonic Fq Pu where+  split _ = x^2 + 1 type Fq2 = ExtensionField Fq Pu+test_Fq2 :: TestTree test_Fq2 = fieldAxioms (Proxy :: Proxy Fq2) "Fq2"+ data Pv-instance IrreducibleMonic Fq2 Pv where split _ = x^3 - (9 + t x)+instance IrreducibleMonic Fq2 Pv where+  split _ = x^3 - (9 + t x) type Fq6 = ExtensionField Fq2 Pv+test_Fq6 :: TestTree test_Fq6 = fieldAxioms (Proxy :: Proxy Fq6) "Fq6"+ data Pw-instance IrreducibleMonic Fq6 Pw where split _ = x^2 - t x+instance IrreducibleMonic Fq6 Pw where+  split _ = x^2 - t x type Fq12 = ExtensionField Fq6 Pw+test_Fq12 :: TestTree test_Fq12 = fieldAxioms (Proxy :: Proxy Fq12) "Fq12"

@@ -2,37 +2,44 @@  import Protolude -import Test.Tasty.QuickCheck--import GaloisField-import GaloisFieldTests import PolynomialRing-import PrimeField-import PrimeFieldTests+import Test.Tasty -instance (Arbitrary k, GaloisField k) => Arbitrary (Polynomial k) where-  arbitrary = toPoly <$> arbitrary+import PrimeFieldTests+import GaloisFieldTests -test_S2X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 2))) "FS2[X]"+test_S2X :: TestTree+test_S2X = ringAxioms (Proxy :: Proxy (Polynomial FS2)) "FS2[X]" -test_S3X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 3))) "FS3[X]"+test_S3X :: TestTree+test_S3X = ringAxioms (Proxy :: Proxy (Polynomial FS3)) "FS3[X]" -test_S5X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 5))) "FS5[X]"+test_S5X :: TestTree+test_S5X = ringAxioms (Proxy :: Proxy (Polynomial FS5)) "FS5[X]" -test_S7X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 7))) "FS7[X]"+test_S7X :: TestTree+test_S7X = ringAxioms (Proxy :: Proxy (Polynomial FS7)) "FS7[X]" -test_M0X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 2147483647))) "FM0[X]"+test_M0X :: TestTree+test_M0X = ringAxioms (Proxy :: Proxy (Polynomial FM0)) "FM0[X]" -test_M1X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 2305843009213693951))) "FM1[X]"+test_M1X :: TestTree+test_M1X = ringAxioms (Proxy :: Proxy (Polynomial FM1)) "FM1[X]" -test_M2X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 618970019642690137449562111))) "FM2[X]"+test_M2X :: TestTree+test_M2X = ringAxioms (Proxy :: Proxy (Polynomial FM2)) "FM2[X]" -test_M3X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 162259276829213363391578010288127))) "FM3[X]"+test_M3X :: TestTree+test_M3X = ringAxioms (Proxy :: Proxy (Polynomial FM3)) "FM3[X]" -test_M4X = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 170141183460469231731687303715884105727))) "FM4[X]"+test_M4X :: TestTree+test_M4X = ringAxioms (Proxy :: Proxy (Polynomial FM4)) "FM4[X]" -test_VLX = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 20988936657440586486151264256610222593863921))) "FVL[X]"+test_VLX :: TestTree+test_VLX = ringAxioms (Proxy :: Proxy (Polynomial FVL)) "FVL[X]" -test_XLX = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 5210644015679228794060694325390955853335898483908056458352183851018372555735221))) "FXL[X]"+test_XLX :: TestTree+test_XLX = ringAxioms (Proxy :: Proxy (Polynomial FXL)) "FXL[X]" -test_ZLX = ringAxioms (Proxy :: Proxy (Polynomial (PrimeField 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737))) "FZL[X]"+test_ZLX :: TestTree+test_ZLX = ringAxioms (Proxy :: Proxy (Polynomial FZL)) "FZL[X]"

@@ -2,34 +2,61 @@  import Protolude -import Test.Tasty.QuickCheck- import PrimeField+import Test.Tasty+ import GaloisFieldTests -instance KnownNat p => Arbitrary (PrimeField p) where-  arbitrary = fromInteger <$> arbitrary+type FS2 = PrimeField 2+type FS3 = PrimeField 3+type FS5 = PrimeField 5+type FS7 = PrimeField 7 -test_S2 = fieldAxioms (Proxy :: Proxy (PrimeField 2)) "FS2"+type FM0 = PrimeField 2147483647+type FM1 = PrimeField 2305843009213693951+type FM2 = PrimeField 618970019642690137449562111+type FM3 = PrimeField 162259276829213363391578010288127+type FM4 = PrimeField 170141183460469231731687303715884105727 -test_S3 = fieldAxioms (Proxy :: Proxy (PrimeField 3)) "FS3"+type FVL = PrimeField 20988936657440586486151264256610222593863921+type FXL = PrimeField 5210644015679228794060694325390955853335898483908056458352183851018372555735221+type FZL = PrimeField 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737 -test_S5 = fieldAxioms (Proxy :: Proxy (PrimeField 5)) "FS5"+type Fq = PrimeField 21888242871839275222246405745257275088696311157297823662689037894645226208583 -test_S7 = fieldAxioms (Proxy :: Proxy (PrimeField 7)) "FS7" -test_M0 = fieldAxioms (Proxy :: Proxy (PrimeField 2147483647)) "FM0"+test_S2 :: TestTree+test_S2 = fieldAxioms (Proxy :: Proxy FS2) "FS2" -test_M1 = fieldAxioms (Proxy :: Proxy (PrimeField 2305843009213693951)) "FM1"+test_S3 :: TestTree+test_S3 = fieldAxioms (Proxy :: Proxy FS3) "FS3" -test_M2 = fieldAxioms (Proxy :: Proxy (PrimeField 618970019642690137449562111)) "FM2"+test_S5 :: TestTree+test_S5 = fieldAxioms (Proxy :: Proxy FS5) "FS5" -test_M3 = fieldAxioms (Proxy :: Proxy (PrimeField 162259276829213363391578010288127)) "FM3"+test_S7 :: TestTree+test_S7 = fieldAxioms (Proxy :: Proxy FS7) "FS7" -test_M4 = fieldAxioms (Proxy :: Proxy (PrimeField 170141183460469231731687303715884105727)) "FM4"+test_M0 :: TestTree+test_M0 = fieldAxioms (Proxy :: Proxy FM0) "FM0" -test_VL = fieldAxioms (Proxy :: Proxy (PrimeField 20988936657440586486151264256610222593863921)) "FVL"+test_M1 :: TestTree+test_M1 = fieldAxioms (Proxy :: Proxy FM1) "FM1" -test_XL = fieldAxioms (Proxy :: Proxy (PrimeField 5210644015679228794060694325390955853335898483908056458352183851018372555735221)) "FXL"+test_M2 :: TestTree+test_M2 = fieldAxioms (Proxy :: Proxy FM2) "FM2" -test_ZL = fieldAxioms (Proxy :: Proxy (PrimeField 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737)) "FZL"+test_M3 :: TestTree+test_M3 = fieldAxioms (Proxy :: Proxy FM3) "FM3"++test_M4 :: TestTree+test_M4 = fieldAxioms (Proxy :: Proxy FM4) "FM4"++test_VL :: TestTree+test_VL = fieldAxioms (Proxy :: Proxy FVL) "FVL"++test_XL :: TestTree+test_XL = fieldAxioms (Proxy :: Proxy FXL) "FXL"++test_ZL :: TestTree+test_ZL = fieldAxioms (Proxy :: Proxy FZL) "FZL"