galois-field 0.4.0 → 0.4.1
raw patch · 6 files changed
+59/−53 lines, 6 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- ChangeLog.md +4/−0
- galois-field.cabal +9/−8
- src/BinaryField.hs +9/−9
- src/ExtensionField.hs +15/−14
- src/GaloisField.hs +16/−16
- src/PrimeField.hs +6/−6
ChangeLog.md view
@@ -1,5 +1,9 @@ # Change log for galois-field +## 0.4.1++* Add compilation optimisations with `INLINABLE`.+ ## 0.4.0 * Add `Vector` implementation of extension fields.
galois-field.cabal view
@@ -1,11 +1,13 @@--- This file has been generated from package.yaml by hpack version 0.28.2.+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: 033214ea0f37604de3c3e831efac36ce0278f2f57df82216bf93635ec31dc830+-- hash: 4e436d9365d8254a628fd2f0a1ce476eb6073af326050f22b8aac993adf97375 name: galois-field-version: 0.4.0+version: 0.4.1 synopsis: Galois field library description: An efficient implementation of Galois fields used in cryptography research category: Cryptography@@ -15,10 +17,9 @@ license: MIT license-file: LICENSE build-type: Simple-cabal-version: >= 1.10 extra-source-files:- ChangeLog.md README.md+ ChangeLog.md source-repository head type: git@@ -35,7 +36,7 @@ hs-source-dirs: src default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses PatternSynonyms- ghc-options: -O2 -Wall+ ghc-options: -Wall build-depends: MonadRandom , base >=4.10 && <5@@ -65,7 +66,7 @@ tests src default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses PatternSynonyms- ghc-options: -O2 -Wall -main-is Main+ ghc-options: -Wall -main-is Main build-depends: MonadRandom , base >=4.10 && <5@@ -96,7 +97,7 @@ benchmarks src default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances FlexibleContexts ScopedTypeVariables RankNTypes DataKinds DeriveGeneric GeneralizedNewtypeDeriving KindSignatures MultiParamTypeClasses PatternSynonyms- ghc-options: -O2 -Wall -main-is Main+ ghc-options: -Wall -main-is Main build-depends: MonadRandom , base >=4.10 && <5
src/BinaryField.hs view
@@ -23,12 +23,12 @@ -- Binary fields are Galois fields. instance KnownNat im => GaloisField (BinaryField im) where- char = const 2- {-# INLINE char #-}- deg = binLog . natVal- {-# INLINE deg #-}- frob = flip pow 2- {-# INLINE frob #-}+ char = const 2+ {-# INLINABLE char #-}+ deg = binLog . natVal+ {-# INLINABLE deg #-}+ frob = flip pow 2+ {-# INLINABLE frob #-} {-# RULES "BinaryField/pow" forall (k :: KnownNat im => BinaryField im) n . (^) k n = pow k n@@ -69,7 +69,6 @@ quotRem = (flip (,) 0 .) . (/) {-# INLINE quotRem #-} degree = panic "not implemented."- {-# INLINE degree #-} -- Binary fields are fields. instance KnownNat im => Field (BinaryField im) where@@ -97,7 +96,7 @@ times = (*) {-# INLINE times #-} fromNatural = fromIntegral- {-# INLINE fromNatural #-}+ {-# INLINABLE fromNatural #-} ------------------------------------------------------------------------------- -- Other instances@@ -106,6 +105,7 @@ -- Binary fields are arbitrary. instance KnownNat im => Arbitrary (BinaryField im) where arbitrary = BF <$> choose (0, order (witness :: BinaryField im) - 1)+ {-# INLINABLE arbitrary #-} -- Binary fields are pretty. instance KnownNat im => Pretty (BinaryField im) where@@ -114,7 +114,7 @@ -- Binary fields are random. instance KnownNat im => Random (BinaryField im) where random = first BF . randomR (0, order (witness :: BinaryField im) - 1)- {-# INLINE random #-}+ {-# INLINABLE random #-} randomR = panic "not implemented." -------------------------------------------------------------------------------
src/ExtensionField.hs view
@@ -39,18 +39,19 @@ {-# MINIMAL split #-} -- | Splitting polynomial @f(X)@. split :: ExtensionField k im -> VPoly k- -- | Splitting polynomial degree.+ -- Splitting polynomial degree. deg' :: ExtensionField k im -> Int deg' = pred . fromIntegral . degree . split+ {-# INLINABLE deg' #-} -- Extension fields are Galois fields. instance IrreducibleMonic k im => GaloisField (ExtensionField k im) where- char = const (char (witness :: k))- {-# INLINE char #-}- deg = (deg (witness :: k) *) . deg'- {-# INLINE deg #-}- frob = pow <*> char- {-# INLINE frob #-}+ char = const (char (witness :: k))+ {-# INLINABLE char #-}+ deg = (deg (witness :: k) *) . deg'+ {-# INLINABLE deg #-}+ frob = pow <*> char+ {-# INLINABLE frob #-} {-# RULES "ExtensionField/pow" forall (k :: IrreducibleMonic k im => ExtensionField k im) n . (^) k n = pow k n@@ -63,7 +64,7 @@ -- Extension fields are fractional. instance IrreducibleMonic k im => Fractional (ExtensionField k im) where recip (EF x) = EF (polyInv x (split (witness :: ExtensionField k im)))- {-# INLINE recip #-}+ {-# INLINABLE recip #-} fromRational (x:%y) = fromInteger x / fromInteger y {-# INLINABLE fromRational #-} @@ -72,7 +73,7 @@ EF x + EF y = EF (plus x y) {-# INLINE (+) #-} EF x * EF y = EF (rem (times x y) (split (witness :: ExtensionField k im)))- {-# INLINE (*) #-}+ {-# INLINABLE (*) #-} EF x - EF y = EF (x - y) {-# INLINE (-) #-} negate (EF x) = EF (S.negate x)@@ -91,7 +92,6 @@ quotRem = (flip (,) 0 .) . (/) {-# INLINE quotRem #-} degree = panic "not implemented."- {-# INLINE degree #-} -- Extension fields are fields. instance IrreducibleMonic k im => Field (ExtensionField k im) where@@ -119,7 +119,7 @@ times = (*) {-# INLINE times #-} fromNatural = fromIntegral- {-# INLINE fromNatural #-}+ {-# INLINABLE fromNatural #-} ------------------------------------------------------------------------------- -- Other instances@@ -128,6 +128,7 @@ -- Extension fields are arbitrary. instance IrreducibleMonic k im => Arbitrary (ExtensionField k im) where arbitrary = toField <$> vector (deg' (witness :: ExtensionField k im))+ {-# INLINABLE arbitrary #-} -- Extension fields are pretty. instance IrreducibleMonic k im => Pretty (ExtensionField k im) where@@ -141,7 +142,7 @@ | n <= 0 = (xs, g) | otherwise = case random g of (x, g') -> unfold (n - 1) (x : xs) g'- {-# INLINE random #-}+ {-# INLINABLE random #-} randomR = panic "not implemented." -------------------------------------------------------------------------------@@ -179,7 +180,7 @@ polyInv xs ps = case first leading (polyGCD xs ps) of (Just (0, x), ys) -> scale 0 (recip x) ys _ -> panic "no multiplicative inverse."-{-# INLINE polyInv #-}+{-# INLINABLE polyInv #-} -- Polynomial extended greatest common divisor algorithm. polyGCD :: forall k . GaloisField k => VPoly k -> VPoly k -> (VPoly k, VPoly k)@@ -189,4 +190,4 @@ polyGCD' s _ r 0 = (r, s) polyGCD' s s' r r' = case quot r r' of q -> polyGCD' s' (s - times q s') r' (r - times q r')-{-# INLINE polyGCD #-}+{-# INLINABLE polyGCD #-}
src/GaloisField.hs view
@@ -24,17 +24,17 @@ -- | Division. divide :: k -> k -> k divide = quot- {-# INLINE divide #-}+ {-# INLINABLE divide #-} -- | Inversion. invert :: k -> k invert = quot one- {-# INLINE invert #-}+ {-# INLINABLE invert #-} -- | Subtraction. minus :: k -> k -> k minus = (-)- {-# INLINE minus #-}+ {-# INLINABLE minus #-} -- | Galois fields @GF(p^q)@ for @p@ prime and @q@ non-negative. class (Arbitrary k, Field k, Fractional k,@@ -52,9 +52,9 @@ -- | Order @p^q@ of field. order :: k -> Integer order = (^) <$> char <*> deg- {-# INLINE order #-}+ {-# INLINABLE order #-} - -- | Frobenius endomorphism @x->x^p@ of prime subfield.+ -- | Frobenius endomorphism @x -> x^p@ of prime subfield. frob :: k -> k -- Functions@@ -74,32 +74,32 @@ z' = z * y y' = y * y m' = div m 2- {-# INLINE pow #-}+ {-# INLINABLE pow #-} -- | Get randomised quadratic nonresidue. qnr :: k qnr = getQNR- {-# INLINE qnr #-}+ {-# INLINABLE qnr #-} -- | Check if quadratic residue. qr :: k -> Bool qr = not . isQNR- {-# INLINE qr #-}+ {-# INLINABLE qr #-} -- | Solve quadratic @ax^2 + bx + c = 0@ over field. quad :: k -> k -> k -> Maybe k quad = solveQuadratic- {-# INLINE quad #-}+ {-# INLINABLE quad #-} -- | Randomised field element. rnd :: MonadRandom m => m k rnd = getRandom- {-# INLINE rnd #-}+ {-# INLINABLE rnd #-} -- | Square root of field element. sr :: k -> Maybe k sr = squareRoot- {-# INLINE sr #-}+ {-# INLINABLE sr #-} ------------------------------------------------------------------------------- -- Square roots@@ -108,7 +108,7 @@ -- Check if an element is a quadratic nonresidue. isQNR :: GaloisField k => k -> Bool isQNR n = pow n (shiftR (order n) 1) /= 1-{-# INLINE isQNR #-}+{-# INLINABLE isQNR #-} -- Factor the order @p - 1@ to get @q@ and @s@ such that @p - 1 = q2^s@. factorOrder :: GaloisField k => k -> (Integer, Int)@@ -118,7 +118,7 @@ factorOrder' qs@(q, s) | testBit q 0 = qs | otherwise = factorOrder' (shiftR q 1, s + 1)-{-# INLINE factorOrder #-}+{-# INLINABLE factorOrder #-} -- Get a random quadratic nonresidue. getQNR :: forall k . GaloisField k => k@@ -128,7 +128,7 @@ getQNR' (x, g) | x /= 0 && isQNR x = x | otherwise = getQNR' (runRand rnd g)-{-# INLINE getQNR #-}+{-# INLINABLE getQNR #-} -- Get a square root of @n@ with the Tonelli-Shanks algorithm. squareRoot :: forall k . GaloisField k => k -> Maybe k@@ -159,7 +159,7 @@ least :: k -> Int -> Int least 1 j = j least ti j = least (ti * ti) (j + 1)-{-# INLINE squareRoot #-}+{-# INLINABLE squareRoot #-} -- Solve a quadratic equation @ax^2 + bx + c = 0@. solveQuadratic :: forall k . GaloisField k => k -> k -> k -> Maybe k@@ -181,4 +181,4 @@ m = deg x xs = take m (iterate (join (*)) x) h = zipWith ($) (cycle [identity, const 0]) xs-{-# INLINE solveQuadratic #-}+{-# INLINABLE solveQuadratic #-}
src/PrimeField.hs view
@@ -25,11 +25,11 @@ -- Prime fields are Galois fields. instance KnownNat p => GaloisField (PrimeField p) where char = natVal- {-# INLINE char #-}+ {-# INLINABLE char #-} deg = const 1- {-# INLINE deg #-}+ {-# INLINABLE deg #-} frob = identity- {-# INLINE frob #-}+ {-# INLINABLE frob #-} pow (PF x) n = PF (powModInteger x n (natVal (witness :: PrimeField p))) {-# INLINE pow #-} @@ -82,7 +82,6 @@ quotRem = (flip (,) 0 .) . (/) {-# INLINE quotRem #-} degree = panic "not implemented."- {-# INLINE degree #-} -- Prime fields are fields. instance KnownNat p => Field (PrimeField p) where@@ -110,7 +109,7 @@ times = (*) {-# INLINE times #-} fromNatural = fromIntegral- {-# INLINE fromNatural #-}+ {-# INLINABLE fromNatural #-} ------------------------------------------------------------------------------- -- Other instances@@ -119,6 +118,7 @@ -- Prime fields are arbitrary. instance KnownNat p => Arbitrary (PrimeField p) where arbitrary = PF <$> choose (0, natVal (witness :: PrimeField p) - 1)+ {-# INLINABLE arbitrary #-} -- Prime fields are pretty. instance KnownNat p => Pretty (PrimeField p) where@@ -127,7 +127,7 @@ -- Prime fields are random. instance KnownNat p => Random (PrimeField p) where random = first PF . randomR (0, natVal (witness :: PrimeField p) - 1)- {-# INLINE random #-}+ {-# INLINABLE random #-} randomR = panic "not implemented." -------------------------------------------------------------------------------