galois-field 1.0.1 → 1.0.2
raw patch · 11 files changed
+421/−437 lines, 11 filesdep +QuickCheckdep +moddep ~MonadRandomdep ~bitvecdep ~criterionPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
Dependencies added: QuickCheck, mod
Dependency ranges changed: MonadRandom, bitvec, criterion, groups, integer-gmp, poly, protolude, semirings, tasty, tasty-quickcheck, vector, wl-pprint-text
API changes (from Hackage documentation)
- Data.Field.Galois: toP' :: KnownNat p => Integer -> Prime p
Files
- ChangeLog.md +8/−0
- README.md +0/−211
- README.notex.md +211/−0
- galois-field.cabal +152/−90
- src/Data/Field/Galois.hs +24/−17
- src/Data/Field/Galois/Base.hs +1/−1
- src/Data/Field/Galois/Binary.hs +1/−1
- src/Data/Field/Galois/Extension.hs +8/−6
- src/Data/Field/Galois/Prime.hs +14/−109
- src/Data/Field/Galois/Unity.hs +1/−1
- test/Test/Galois.hs +1/−1
ChangeLog.md view
@@ -1,5 +1,13 @@ # Change log for galois-field +## 1.0.2++* Add `Mod` dependency for prime fields.+* Add minor optimisations for prime fields.+* Remove unsafeCoerce for number coercions.+* Bump poly dependency to 0.4.+* Bump upper bound for protolude.+ ## 1.0.1 * Add `Bit` dependency for binary fields.
− README.md
@@ -1,211 +0,0 @@-<p align="center">- <a href="https://www.adjoint.io">- <img width="250" src="./.assets/adjoint.png" alt="Adjoint Logo" />- </a>-</p>--[](https://circleci.com/gh/adjoint-io/galois-field)-[](https://hackage.haskell.org/package/galois-field)--# Galois Field--An efficient implementation of Galois fields used in cryptography research.--## Technical background--A **Galois field** GF(p^q), for prime p and positive q, is a *field* (GF(p^q), +, \*, 0, 1) of finite *order*. Explicitly,-- (GF(p^q), +, 0) is an abelian group,-- (GF(p^q) \\ \{0\}, \*, 1) is an abelian group,-- \* is distributive over +, and-- \#GF(p^q) is finite.--### Prime fields--Any Galois field has a unique *characteristic* p, the minimum positive p such that p(1) = 1 + ... + 1 = 0, and p is prime. The smallest Galois field of characteristic p is a **prime field**, and any Galois field of characteristic p is a *finite-dimensional vector space* over its prime subfield.--For example, GF(4) is a Galois field of characteristic 2 that is a two-dimensional vector space over the prime subfield GF(2) = Z / 2Z.--### Extension fields--Any Galois field has order a prime power p^q for prime p and positive q, and there is a Galois field GF(p^q) of any prime power order p^q that is *unique up to non-unique isomorphism*. Any Galois field GF(p^q) can be constructed as an **extension field** over a smaller Galois subfield GF(p^r), through the identification GF(p^q) = GF(p^r)[X] / \<f(X)\> for an *irreducible monic polynomial* f(X) of degree q - r + 1 in the *polynomial ring* GF(p^r)[X].--For example, GF(4) has order 2^2 and can be constructed as an extension field GF(2)[X] / \<f(X)\> where f(X) = X^2 + X + 1 is an irreducible monic quadratic polynomial in GF(2)[X].--### Binary fields--A Galois field of the form GF(2^m) for big positive m is a sum of X^n for a non-empty set of 0 \< n \< m. For computational efficiency in cryptography, an element of a **binary field** can be represented by an integer that represents a bit string. It should always be used when the field characteristic is 2.--For example, X^8 + X^4 + X^3 + X + 1 can be represented as the integer 283 that represents the bit string 100011011.--## Example usage--Include the following required language extensions.-```haskell-{-# LANGUAGE DataKinds #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE OverloadedLists #-}-{-# LANGUAGE PatternSynonyms #-}-```-Import the following functions at minimum.-```haskell-import Data.Field.Galois (Prime, Extension, IrreducibleMonic(poly), Binary,- pattern X, pattern X2, pattern X3, pattern Y)-```--### Prime fields--The following type declaration creates a prime field of a given characteristic.-```haskell-type Fq = Prime 21888242871839275222246405745257275088696311157297823662689037894645226208583-```-Note that the characteristic given *must* be prime.--Galois field arithmetic can then be performed in this prime field.-```haskell-fq :: Fq-fq = 5216004179354450092383934373463611881445186046129513844852096383579774061693--fq' :: Fq-fq' = 10757805228921058098980668000791497318123219899766237205512608761387909753942--arithmeticFq :: (Fq, Fq, Fq, Fq)-arithmeticFq = (fq + fq', fq - fq', fq * fq', fq / fq')-```--### Extension fields--The following data type declaration creates a polynomial given an irreducible monic polynomial.-```haskell-data P2-instance IrreducibleMonic P2 Fq where- poly _ = X2 + 1-```-The following type declaration then creates an extension field with this polynomial.-```haskell-type Fq2 = Extension P2 Fq-```-Note that the polynomial given *must* be irreducible and monic in the prime field.--Similarly, further extension fields can be constructed iteratively as follows.-```haskell-data P6-instance IrreducibleMonic P6 Fq2 where- poly _ = X3 - (9 + Y X)--type Fq6 = Extension P6 Fq2--data P12-instance IrreducibleMonic P12 Fq6 where- poly _ = X2 - Y X--type Fq12 = Extension P12 Fq6-```-Note that `X, X2, X3` accesses the current indeterminate variables and `Y` descends the tower of indeterminate variables.--Galois field arithmetic can then be performed in this extension field.-```haskell-fq12 :: Fq12-fq12 =- [ [ [ 4025484419428246835913352650763180341703148406593523188761836807196412398582- , 5087667423921547416057913184603782240965080921431854177822601074227980319916- ]- , [ 8868355606921194740459469119392835913522089996670570126495590065213716724895- , 12102922015173003259571598121107256676524158824223867520503152166796819430680- ]- , [ 92336131326695228787620679552727214674825150151172467042221065081506740785- , 5482141053831906120660063289735740072497978400199436576451083698548025220729- ]- ]- , [ [ 7642691434343136168639899684817459509291669149586986497725240920715691142493- , 1211355239100959901694672926661748059183573115580181831221700974591509515378- ]- , [ 20725578899076721876257429467489710434807801418821512117896292558010284413176- , 17642016461759614884877567642064231230128683506116557502360384546280794322728- ]- , [ 17449282511578147452934743657918270744212677919657988500433959352763226500950- , 1205855382909824928004884982625565310515751070464736233368671939944606335817- ]- ]- ]--fq12' :: Fq12-fq12' =- [ [ [ 495492586688946756331205475947141303903957329539236899715542920513774223311- , 9283314577619389303419433707421707208215462819919253486023883680690371740600- ]- , [ 11142072730721162663710262820927009044232748085260948776285443777221023820448- , 1275691922864139043351956162286567343365697673070760209966772441869205291758- ]- , [ 20007029371545157738471875537558122753684185825574273033359718514421878893242- , 9839139739201376418106411333971304469387172772449235880774992683057627654905- ]- ]- , [ [ 9503058454919356208294350412959497499007919434690988218543143506584310390240- , 19236630380322614936323642336645412102299542253751028194541390082750834966816- ]- , [ 18019769232924676175188431592335242333439728011993142930089933693043738917983- , 11549213142100201239212924317641009159759841794532519457441596987622070613872- ]- , [ 9656683724785441232932664175488314398614795173462019188529258009817332577664- , 20666848762667934776817320505559846916719041700736383328805334359135638079015- ]- ]- ]--arithmeticFq12 :: (Fq12, Fq12, Fq12, Fq12)-arithmeticFq12 = (fq12 + fq12', fq12 - fq12', fq12 * fq12', fq12 / fq12')-```-Note that-```-a + bX + (c + dX)Y + (e + fX)Y^2 + (g + hX + (i + jX)Y + (k + lX)Y^2)Z-```-where `X, Y, Z` is a tower of indeterminate variables, is constructed by-```haskell-[ [ [a, b], [c, d], [e, f] ]-, [ [g, h], [i, j], [k, l] ] ] :: Fq12-```--### Binary fields--The following type declaration creates a binary field modulo a given irreducible binary polynomial.-```haskell-type F2m = Binary 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425-```-Note that the polynomial given *must* be irreducible in F2.--Galois field arithmetic can then be performed in this binary field.-```haskell-f2m :: F2m-f2m = 0x303001d34b856296c16c0d40d3cd7750a93d1d2955fa80aa5f40fc8db7b2abdbde53950f4c0d293cdd711a35b67fb1499ae60038614f1394abfa3b4c850d927e1e7769c8eec2d19--f2m' :: F2m-f2m' = 0x37bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b--arithmeticF2m :: (F2m, F2m, F2m, F2m)-arithmeticF2m = (f2m + f2m', f2m - f2m', f2m * f2m', f2m / f2m')-```--## License--```-Copyright (c) 2019 Adjoint Inc.--Permission is hereby granted, free of charge, to any person obtaining a copy-of this software and associated documentation files (the "Software"), to deal-in the Software without restriction, including without limitation the rights-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell-copies of the Software, and to permit persons to whom the Software is-furnished to do so, subject to the following conditions:--The above copyright notice and this permission notice shall be included in all-copies or substantial portions of the Software.--THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,-EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF-MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.-IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,-DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR-OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE-OR OTHER DEALINGS IN THE SOFTWARE.-```
+ README.notex.md view
@@ -0,0 +1,211 @@+<p align="center">+ <a href="https://www.adjoint.io">+ <img width="250" src="./.assets/adjoint.png" alt="Adjoint Logo" />+ </a>+</p>++[](https://circleci.com/gh/adjoint-io/galois-field)+[](https://hackage.haskell.org/package/galois-field)++# Galois Field++An efficient implementation of Galois fields used in cryptography research.++## Technical background++A **Galois field** GF(p^q), for prime p and positive q, is a *field* (GF(p^q), +, \*, 0, 1) of finite *order*. Explicitly,+- (GF(p^q), +, 0) is an abelian group,+- (GF(p^q) \\ \{0\}, \*, 1) is an abelian group,+- \* is distributive over +, and+- \#GF(p^q) is finite.++### Prime fields++Any Galois field has a unique *characteristic* p, the minimum positive p such that p(1) = 1 + ... + 1 = 0, and p is prime. The smallest Galois field of characteristic p is a **prime field**, and any Galois field of characteristic p is a *finite-dimensional vector space* over its prime subfield.++For example, GF(4) is a Galois field of characteristic 2 that is a two-dimensional vector space over the prime subfield GF(2) = Z / 2Z.++### Extension fields++Any Galois field has order a prime power p^q for prime p and positive q, and there is a Galois field GF(p^q) of any prime power order p^q that is *unique up to non-unique isomorphism*. Any Galois field GF(p^q) can be constructed as an **extension field** over a smaller Galois subfield GF(p^r), through the identification GF(p^q) = GF(p^r)[X] / \<f(X)\> for an *irreducible monic polynomial* f(X) of degree q - r + 1 in the *polynomial ring* GF(p^r)[X].++For example, GF(4) has order 2^2 and can be constructed as an extension field GF(2)[X] / \<f(X)\> where f(X) = X^2 + X + 1 is an irreducible monic quadratic polynomial in GF(2)[X].++### Binary fields++A Galois field of the form GF(2^m) for big positive m is a sum of X^n for a non-empty set of 0 \< n \< m. For computational efficiency in cryptography, an element of a **binary field** can be represented by an integer that represents a bit string. It should always be used when the field characteristic is 2.++For example, X^8 + X^4 + X^3 + X + 1 can be represented as the integer 283 that represents the bit string 100011011.++## Example usage++Include the following required language extensions.+```haskell+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE OverloadedLists #-}+{-# LANGUAGE PatternSynonyms #-}+```+Import the following functions at minimum.+```haskell+import Data.Field.Galois (Prime, Extension, IrreducibleMonic(poly), Binary,+ pattern X, pattern X2, pattern X3, pattern Y)+```++### Prime fields++The following type declaration creates a prime field of a given characteristic.+```haskell+type Fq = Prime 21888242871839275222246405745257275088696311157297823662689037894645226208583+```+Note that the characteristic given *must* be prime.++Galois field arithmetic can then be performed in this prime field.+```haskell+fq :: Fq+fq = 5216004179354450092383934373463611881445186046129513844852096383579774061693++fq' :: Fq+fq' = 10757805228921058098980668000791497318123219899766237205512608761387909753942++arithmeticFq :: (Fq, Fq, Fq, Fq)+arithmeticFq = (fq + fq', fq - fq', fq * fq', fq / fq')+```++### Extension fields++The following data type declaration creates a polynomial given an irreducible monic polynomial.+```haskell+data P2+instance IrreducibleMonic P2 Fq where+ poly _ = X2 + 1+```+The following type declaration then creates an extension field with this polynomial.+```haskell+type Fq2 = Extension P2 Fq+```+Note that the polynomial given *must* be irreducible and monic in the prime field.++Similarly, further extension fields can be constructed iteratively as follows.+```haskell+data P6+instance IrreducibleMonic P6 Fq2 where+ poly _ = X3 - (9 + Y X)++type Fq6 = Extension P6 Fq2++data P12+instance IrreducibleMonic P12 Fq6 where+ poly _ = X2 - Y X++type Fq12 = Extension P12 Fq6+```+Note that `X, X2, X3` accesses the current indeterminate variables and `Y` descends the tower of indeterminate variables.++Galois field arithmetic can then be performed in this extension field.+```haskell+fq12 :: Fq12+fq12 =+ [ [ [ 4025484419428246835913352650763180341703148406593523188761836807196412398582+ , 5087667423921547416057913184603782240965080921431854177822601074227980319916+ ]+ , [ 8868355606921194740459469119392835913522089996670570126495590065213716724895+ , 12102922015173003259571598121107256676524158824223867520503152166796819430680+ ]+ , [ 92336131326695228787620679552727214674825150151172467042221065081506740785+ , 5482141053831906120660063289735740072497978400199436576451083698548025220729+ ]+ ]+ , [ [ 7642691434343136168639899684817459509291669149586986497725240920715691142493+ , 1211355239100959901694672926661748059183573115580181831221700974591509515378+ ]+ , [ 20725578899076721876257429467489710434807801418821512117896292558010284413176+ , 17642016461759614884877567642064231230128683506116557502360384546280794322728+ ]+ , [ 17449282511578147452934743657918270744212677919657988500433959352763226500950+ , 1205855382909824928004884982625565310515751070464736233368671939944606335817+ ]+ ]+ ]++fq12' :: Fq12+fq12' =+ [ [ [ 495492586688946756331205475947141303903957329539236899715542920513774223311+ , 9283314577619389303419433707421707208215462819919253486023883680690371740600+ ]+ , [ 11142072730721162663710262820927009044232748085260948776285443777221023820448+ , 1275691922864139043351956162286567343365697673070760209966772441869205291758+ ]+ , [ 20007029371545157738471875537558122753684185825574273033359718514421878893242+ , 9839139739201376418106411333971304469387172772449235880774992683057627654905+ ]+ ]+ , [ [ 9503058454919356208294350412959497499007919434690988218543143506584310390240+ , 19236630380322614936323642336645412102299542253751028194541390082750834966816+ ]+ , [ 18019769232924676175188431592335242333439728011993142930089933693043738917983+ , 11549213142100201239212924317641009159759841794532519457441596987622070613872+ ]+ , [ 9656683724785441232932664175488314398614795173462019188529258009817332577664+ , 20666848762667934776817320505559846916719041700736383328805334359135638079015+ ]+ ]+ ]++arithmeticFq12 :: (Fq12, Fq12, Fq12, Fq12)+arithmeticFq12 = (fq12 + fq12', fq12 - fq12', fq12 * fq12', fq12 / fq12')+```+Note that+```+a + bX + (c + dX)Y + (e + fX)Y^2 + (g + hX + (i + jX)Y + (k + lX)Y^2)Z+```+where `X, Y, Z` is a tower of indeterminate variables, is constructed by+```haskell+[ [ [a, b], [c, d], [e, f] ]+, [ [g, h], [i, j], [k, l] ] ] :: Fq12+```++### Binary fields++The following type declaration creates a binary field modulo a given irreducible binary polynomial.+```haskell+type F2m = Binary 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425+```+Note that the polynomial given *must* be irreducible in F2.++Galois field arithmetic can then be performed in this binary field.+```haskell+f2m :: F2m+f2m = 0x303001d34b856296c16c0d40d3cd7750a93d1d2955fa80aa5f40fc8db7b2abdbde53950f4c0d293cdd711a35b67fb1499ae60038614f1394abfa3b4c850d927e1e7769c8eec2d19++f2m' :: F2m+f2m' = 0x37bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b++arithmeticF2m :: (F2m, F2m, F2m, F2m)+arithmeticF2m = (f2m + f2m', f2m - f2m', f2m * f2m', f2m / f2m')+```++## License++```+Copyright (c) 2019-2020 Adjoint Inc.++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,+DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR+OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE+OR OTHER DEALINGS IN THE SOFTWARE.+```
galois-field.cabal view
@@ -1,114 +1,176 @@-cabal-version: 1.12+cabal-version: 1.12 -- This file has been generated from package.yaml by hpack version 0.31.2. -- -- see: https://github.com/sol/hpack ----- hash: f4e2a6cce087c45e10262060054544b7596de8e4a173935c13f460d1bf83ddd3+-- hash: 4f1f517ac1812c3cb4f6bd4c78c3091393d6c7708ce11feb2729ac6f871f92c4 -name: galois-field-version: 1.0.1-synopsis: Galois field library-description: An efficient implementation of Galois fields used in cryptography research-category: Cryptography-homepage: https://github.com/adjoint-io/galois-field#readme-bug-reports: https://github.com/adjoint-io/galois-field/issues-maintainer: Adjoint Inc (info@adjoint.io)-license: MIT-license-file: LICENSE-build-type: Simple+name: galois-field+version: 1.0.2+synopsis: Galois field library+description:+ An efficient implementation of Galois fields used in cryptography research++category: Cryptography+homepage: https://github.com/adjoint-io/galois-field#readme+bug-reports: https://github.com/adjoint-io/galois-field/issues+maintainer: Adjoint Inc (info@adjoint.io)+license: MIT+license-file: LICENSE+build-type: Simple extra-source-files:- README.md- ChangeLog.md+ README.notex.md+ ChangeLog.md source-repository head- type: git+ type: git location: https://github.com/adjoint-io/galois-field library- exposed-modules:- Data.Field.Galois+ exposed-modules: Data.Field.Galois other-modules:- Data.Field.Galois.Base- Data.Field.Galois.Binary- Data.Field.Galois.Extension- Data.Field.Galois.Frobenius- Data.Field.Galois.Prime- Data.Field.Galois.Sqrt- Data.Field.Galois.Tower- Data.Field.Galois.Unity- hs-source-dirs:- src- default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveFunctor DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses OverloadedLists PatternSynonyms TypeFamilies- ghc-options: -freverse-errors -O2 -Wall+ Data.Field.Galois.Base+ Data.Field.Galois.Binary+ Data.Field.Galois.Extension+ Data.Field.Galois.Frobenius+ Data.Field.Galois.Prime+ Data.Field.Galois.Sqrt+ Data.Field.Galois.Tower+ Data.Field.Galois.Unity++ hs-source-dirs: src+ default-extensions:+ NoImplicitPrelude+ DataKinds+ DeriveFunctor+ DeriveGeneric+ FlexibleContexts+ FlexibleInstances+ GeneralizedNewtypeDeriving+ KindSignatures+ LambdaCase+ MultiParamTypeClasses+ OverloadedLists+ OverloadedStrings+ PatternSynonyms+ RankNTypes+ RecordWildCards+ ScopedTypeVariables+ TypeFamilies++ ghc-options: -freverse-errors -O2 -Wall build-depends:- MonadRandom- , base >=4.10 && <5- , bitvec >=1.0.2- , groups- , integer-gmp- , poly >=0.3.2- , protolude >=0.2 && <0.3- , semirings >=0.5- , tasty-quickcheck- , vector- , wl-pprint-text- default-language: Haskell2010+ base >=4.10 && <5+ , bitvec >=1.0.2 && <1.1+ , groups >=0.4.1 && <0.5+ , integer-gmp >=1.0.2 && <1.1+ , mod >=0.1.0 && <0.2+ , MonadRandom >=0.5.1 && <0.6+ , poly >=0.3.2 && <0.5+ , protolude >=0.2 && <0.4+ , QuickCheck >=2.13 && <2.14+ , semirings >=0.5 && <0.6+ , vector >=0.12.0 && <0.13+ , wl-pprint-text >=1.2.0 && <1.3 + default-language: Haskell2010+ test-suite galois-field-tests- type: exitcode-stdio-1.0- main-is: Main.hs+ type: exitcode-stdio-1.0+ main-is: Main.hs other-modules:- Test.Binary- Test.Extension- Test.Galois- Test.Prime- Paths_galois_field- hs-source-dirs:- test- default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveFunctor DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses OverloadedLists PatternSynonyms TypeFamilies- ghc-options: -freverse-errors -O2 -Wall -main-is Main+ Paths_galois_field+ Test.Binary+ Test.Extension+ Test.Galois+ Test.Prime++ hs-source-dirs: test+ default-extensions:+ NoImplicitPrelude+ DataKinds+ DeriveFunctor+ DeriveGeneric+ FlexibleContexts+ FlexibleInstances+ GeneralizedNewtypeDeriving+ KindSignatures+ LambdaCase+ MultiParamTypeClasses+ OverloadedLists+ OverloadedStrings+ PatternSynonyms+ RankNTypes+ RecordWildCards+ ScopedTypeVariables+ TypeFamilies++ ghc-options: -freverse-errors -O2 -Wall -main-is Main build-depends:- MonadRandom- , base >=4.10 && <5- , bitvec >=1.0.2+ base >=4.10 && <5+ , bitvec >=1.0.2 && <1.1 , galois-field- , groups- , integer-gmp- , poly >=0.3.2- , protolude >=0.2 && <0.3- , semirings >=0.5- , tasty- , tasty-quickcheck- , vector- , wl-pprint-text- default-language: Haskell2010+ , groups >=0.4.1 && <0.5+ , integer-gmp >=1.0.2 && <1.1+ , mod >=0.1.0 && <0.2+ , MonadRandom >=0.5.1 && <0.6+ , poly >=0.3.2 && <0.5+ , protolude >=0.2 && <0.4+ , QuickCheck >=2.13 && <2.14+ , semirings >=0.5 && <0.6+ , tasty >=1.2 && <1.3+ , tasty-quickcheck >=0.10 && <0.11+ , vector >=0.12.0 && <0.13+ , wl-pprint-text >=1.2.0 && <1.3 + default-language: Haskell2010+ benchmark galois-field-benchmarks- type: exitcode-stdio-1.0- main-is: Main.hs+ type: exitcode-stdio-1.0+ main-is: Main.hs other-modules:- Bench.Binary- Bench.Extension- Bench.Galois- Bench.Prime- Paths_galois_field- hs-source-dirs:- bench- default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveFunctor DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses OverloadedLists PatternSynonyms TypeFamilies- ghc-options: -freverse-errors -O2 -Wall -main-is Main+ Bench.Binary+ Bench.Extension+ Bench.Galois+ Bench.Prime+ Paths_galois_field++ hs-source-dirs: bench+ default-extensions:+ NoImplicitPrelude+ DataKinds+ DeriveFunctor+ DeriveGeneric+ FlexibleContexts+ FlexibleInstances+ GeneralizedNewtypeDeriving+ KindSignatures+ LambdaCase+ MultiParamTypeClasses+ OverloadedLists+ OverloadedStrings+ PatternSynonyms+ RankNTypes+ RecordWildCards+ ScopedTypeVariables+ TypeFamilies++ ghc-options: -freverse-errors -O2 -Wall -main-is Main build-depends:- MonadRandom- , base >=4.10 && <5- , bitvec >=1.0.2- , criterion+ base >=4.10 && <5+ , bitvec >=1.0.2 && <1.1+ , criterion >=1.5 && <1.6 , galois-field- , groups- , integer-gmp- , poly >=0.3.2- , protolude >=0.2 && <0.3- , semirings >=0.5- , tasty-quickcheck- , vector- , wl-pprint-text- default-language: Haskell2010+ , groups >=0.4.1 && <0.5+ , integer-gmp >=1.0.2 && <1.1+ , mod >=0.1.0 && <0.2+ , MonadRandom >=0.5.1 && <0.6+ , poly >=0.3.2 && <0.5+ , protolude >=0.2 && <0.4+ , QuickCheck >=2.13 && <2.14+ , semirings >=0.5 && <0.6+ , vector >=0.12.0 && <0.13+ , wl-pprint-text >=1.2.0 && <1.3++ default-language: Haskell2010
src/Data/Field/Galois.hs view
@@ -1,22 +1,29 @@+-- |+-- An efficient implementation of Galois fields used in cryptography research. module Data.Field.Galois- ( module Data.Field- -- * Galois fields- , module Data.Field.Galois.Base- -- ** Prime fields- , module Data.Field.Galois.Prime- -- ** Extension fields- , module Data.Field.Galois.Extension- -- ** Binary fields- , module Data.Field.Galois.Binary- -- ** Square roots- , module Data.Field.Galois.Sqrt- -- ** Towers of fields- , module Data.Field.Galois.Tower- -- ** Roots of unity- , module Data.Field.Galois.Unity- ) where+ ( -- * Galois fields+ module Data.Field.Galois.Base, -import Data.Field+ -- ** Prime fields+ module Data.Field.Galois.Prime,++ -- ** Extension fields+ module Data.Field.Galois.Extension,++ -- ** Binary fields+ module Data.Field.Galois.Binary,++ -- ** Square roots+ module Data.Field.Galois.Sqrt,++ -- ** Towers of fields+ module Data.Field.Galois.Tower,++ -- ** Roots of unity+ module Data.Field.Galois.Unity,+ )+where+ import Data.Field.Galois.Base import Data.Field.Galois.Binary import Data.Field.Galois.Extension
src/Data/Field/Galois/Base.hs view
@@ -8,7 +8,7 @@ import Data.Field (Field) import qualified Data.Group as G (Group(..)) import GHC.Natural (Natural)-import Test.Tasty.QuickCheck (Arbitrary)+import Test.QuickCheck (Arbitrary) import Text.PrettyPrint.Leijen.Text (Pretty) -------------------------------------------------------------------------------
src/Data/Field/Galois/Binary.hs view
@@ -18,7 +18,7 @@ import GHC.Exts (IsList(..)) import GHC.Natural (Natural) import GHC.TypeNats (natVal)-import Test.Tasty.QuickCheck (Arbitrary(..), choose)+import Test.QuickCheck (Arbitrary(..), choose) import Text.PrettyPrint.Leijen.Text (Pretty(..)) import Data.Field.Galois.Base (GaloisField(..))
src/Data/Field/Galois/Extension.hs view
@@ -19,13 +19,13 @@ import Protolude as P hiding (Semiring, rem, toList) import Control.Monad.Random (Random(..))-import Data.Euclidean (Euclidean(..), GcdDomain)+import Data.Euclidean (Euclidean(..), GcdDomain, gcdExt) import Data.Field (Field) import Data.Group (Group(..))-import Data.Poly (VPoly, gcdExt, monomial, toPoly, unPoly)+import Data.Poly (VPoly, monomial, toPoly, unPoly, scale, leading) import Data.Semiring (Ring(..), Semiring(..)) import GHC.Exts (IsList(..))-import Test.Tasty.QuickCheck (Arbitrary(..), vector)+import Test.QuickCheck (Arbitrary(..), vector) import Text.PrettyPrint.Leijen.Text (Pretty(..)) import Data.Field.Galois.Base (GaloisField(..))@@ -103,9 +103,11 @@ -- Extension fields are fractional. instance IrreducibleMonic p k => Fractional (Extension p k) where- recip (E x) = case gcdExt x $ poly (witness :: Extension p k) of- (1, y) -> E y- _ -> divZeroError+ recip (E x) = case leading g of+ Just (0, c) -> E $ scale 0 (recip c) y+ _ -> divZeroError+ where+ (g, y) = gcdExt x $ poly (witness :: Extension p k) {-# INLINABLE recip #-} fromRational (x:%y) = fromInteger x / fromInteger y {-# INLINABLE fromRational #-}
src/Data/Field/Galois/Prime.hs view
@@ -3,7 +3,6 @@ , PrimeField , fromP , toP- , toP' ) where import Protolude as P hiding (Semiring, natVal, rem)@@ -12,11 +11,11 @@ import Data.Euclidean as S (Euclidean(..), GcdDomain) import Data.Field (Field) import Data.Group (Group(..))+import Data.Mod (Mod, unMod, (^%)) import Data.Semiring (Ring(..), Semiring(..))-import GHC.Integer.GMP.Internals (recipModInteger)-import GHC.Natural (Natural, naturalFromInteger, naturalToInteger, powModNatural)+import GHC.Natural (naturalToInteger) import GHC.TypeNats (natVal)-import Test.Tasty.QuickCheck (Arbitrary(..), choose)+import Test.QuickCheck (Arbitrary(..), choose) import Text.PrettyPrint.Leijen.Text (Pretty(..)) import Data.Field.Galois.Base (GaloisField(..))@@ -32,12 +31,15 @@ fromP :: k -> Integer -- | Prime field elements.-newtype Prime (p :: Nat) = P Natural- deriving (Bits, Eq, Generic, Hashable, NFData, Ord, Show)+newtype Prime (p :: Nat) = P (Mod p)+ deriving (Eq, Ord, Show, Generic, Num, Fractional, Euclidean, Field, GcdDomain, Ring, Semiring, Bounded, Enum, NFData) +instance Hashable (Prime p) where+ hashWithSalt s (P x) = hashWithSalt s (unMod x)+ -- Prime fields are convertible. instance KnownNat p => PrimeField (Prime p) where- fromP (P x) = naturalToInteger x+ fromP (P x) = naturalToInteger (unMod x) {-# INLINABLE fromP #-} -- Prime fields are Galois fields.@@ -61,9 +63,7 @@ instance KnownNat p => Group (Prime p) where invert = recip {-# INLINE invert #-}- pow y@(P x) n- | n >= 0 = P $ powModNatural x (fromIntegral n) $ natVal (witness :: Prime p)- | otherwise = pow (recip y) $ P.negate n+ pow (P x) k = P (x ^% k) {-# INLINE pow #-} -- Prime fields are multiplicative monoids.@@ -79,94 +79,14 @@ {-# INLINE stimes #-} ---------------------------------------------------------------------------------- Numeric instances------------------------------------------------------------------------------------ Prime fields are fractional.-instance KnownNat p => Fractional (Prime p) where- recip (P 0) = divZeroError- recip (P x) = P $ recipModNatural x $ natVal (witness :: Prime p)- {-# INLINE recip #-}- fromRational (x:%y) = fromInteger x / fromInteger y- {-# INLINABLE fromRational #-}---- Prime fields are numeric.-instance KnownNat p => Num (Prime p) where- P x + P y = P $ if xy >= p then xy - p else xy- where- xy = x + y- p = natVal (witness :: Prime p)- {-# INLINE (+) #-}- P x * P y = P $ rem (x * y) $ natVal (witness :: Prime p)- {-# INLINE (*) #-}- P x - P y = P $ if x >= y then x - y else natVal (witness :: Prime p) + x - y- {-# INLINE (-) #-}- negate (P 0) = P 0- negate (P x) = P $ natVal (witness :: Prime p) - x- {-# INLINE negate #-}- fromInteger x = P $ naturalFromInteger $ mod x $ naturalToInteger $ natVal (witness :: Prime p)- {-# INLINABLE fromInteger #-}- abs = panic "Prime.abs: not implemented."- signum = panic "Prime.signum: not implemented."------------------------------------------------------------------------------------ Semiring instances------------------------------------------------------------------------------------ Prime fields are Euclidean domains.-instance KnownNat p => Euclidean (Prime p) where- degree = panic "Prime.degree: not implemented."- quotRem = (flip (,) 0 .) . (/)- {-# INLINE quotRem #-}---- Prime fields are fields.-instance KnownNat p => Field (Prime p)---- Prime fields are GCD domains.-instance KnownNat p => GcdDomain (Prime p)---- Prime fields are rings.-instance KnownNat p => Ring (Prime p) where- negate = P.negate- {-# INLINE negate #-}---- Prime fields are semirings.-instance KnownNat p => Semiring (Prime p) where- fromNatural = fromIntegral- {-# INLINABLE fromNatural #-}- one = P 1- {-# INLINE one #-}- plus = (+)- {-# INLINE plus #-}- times = (*)- {-# INLINE times #-}- zero = P 0- {-# INLINE zero #-}--------------------------------------------------------------------------------- -- Other instances ------------------------------------------------------------------------------- -- Prime fields are arbitrary. instance KnownNat p => Arbitrary (Prime p) where- arbitrary = P . naturalFromInteger <$>- choose (0, naturalToInteger $ natVal (witness :: Prime p) - 1)+ arbitrary = choose (minBound, maxBound) {-# INLINABLE arbitrary #-} --- Prime fields are bounded.-instance KnownNat p => Bounded (Prime p) where- maxBound = P $ natVal (witness :: Prime p) - 1- {-# INLINE maxBound #-}- minBound = P 0- {-# INLINE minBound #-}---- Prime fields are enumerable.-instance KnownNat p => Enum (Prime p) where- fromEnum = fromIntegral- {-# INLINABLE fromEnum #-}- toEnum = fromIntegral- {-# INLINABLE toEnum #-}- -- Prime fields are integral. instance KnownNat p => Integral (Prime p) where quotRem = S.quotRem@@ -176,13 +96,13 @@ -- Prime fields are pretty. instance KnownNat p => Pretty (Prime p) where- pretty (P x) = pretty $ naturalToInteger x+ pretty (P x) = pretty $ naturalToInteger $ unMod x -- Prime fields are random. instance KnownNat p => Random (Prime p) where- random = randomR (P 0, P $ natVal (witness :: Prime p) - 1)+ random = randomR (minBound, maxBound) {-# INLINABLE random #-}- randomR (a, b) = first (P . naturalFromInteger) . randomR (fromP a, fromP b)+ randomR (a, b) = first fromInteger . randomR (fromP a, fromP b) {-# INLINABLE randomR #-} -- Prime fields are real.@@ -198,18 +118,3 @@ toP :: KnownNat p => Integer -> Prime p toP = fromInteger {-# INLINABLE toP #-}---- | Unsafe convert from @Z@ to @GF(p)@.-toP' :: KnownNat p => Integer -> Prime p-toP' = P . naturalFromInteger-{-# INLINABLE toP' #-}------------------------------------------------------------------------------------ Prime arithmetic------------------------------------------------------------------------------------ Reciprocals modulo naturals.-recipModNatural :: Natural -> Natural -> Natural-recipModNatural x p = naturalFromInteger $- recipModInteger (naturalToInteger x) (naturalToInteger p)-{-# INLINE recipModNatural #-}
src/Data/Field/Galois/Unity.hs view
@@ -17,7 +17,7 @@ import Data.Group (Group(..)) import GHC.Natural (Natural, naturalToInteger) import GHC.TypeNats (natVal)-import Test.Tasty.QuickCheck (Arbitrary(..), choose)+import Test.QuickCheck (Arbitrary(..), choose) import Text.PrettyPrint.Leijen.Text (Pretty(..)) import Data.Field.Galois.Base (GaloisField(..))
test/Test/Galois.hs view
@@ -2,7 +2,7 @@ import Protolude -import Data.Field.Galois hiding (recip)+import Data.Field.Galois import Test.Tasty import Test.Tasty.QuickCheck