finite-field 0.4.0 → 0.5.0

raw patch · 5 files changed

+97/−14 lines, 5 filesdep +template-haskellPVP ok

version bump matches the API change (PVP)

Dependencies added: template-haskell

API changes (from Hackage documentation)

Files

• finite-field.cabal +8/−3
• src/Data/FiniteField.hs +18/−0
• src/Data/FiniteField/Base.hs +30/−0
• src/Data/FiniteField/PrimeField.hs +25/−9
• test/TestPrimeField.hs +16/−2

@@ -1,5 +1,5 @@ Name:		finite-field-Version:	0.4.0+Version:	0.5.0 License:	BSD3 License-File:	COPYING Author:		Masahiro Sakai (masahiro.sakai@gmail.com)@@ -7,7 +7,9 @@ Category:	Math, Data Cabal-Version:	>= 1.10 Synopsis:	Finite Fields-Description:	Implementation of finite fields+Description:+  This is an implementation of finite fields.+  Currently only prime fields are supported. Bug-Reports:	https://github.com/msakai/finite-field/issues Extra-Source-Files:    README.md@@ -23,7 +25,7 @@ Library   Hs-source-dirs: src   Build-Depends:-     base >=4 && <5, deepseq, type-level-numbers, algebra >=3.1+     base >=4 && <5, template-haskell, deepseq, type-level-numbers, algebra >=3.1   Default-Language: Haskell2010   Other-Extensions:      DeriveDataTypeable@@ -31,7 +33,10 @@      ScopedTypeVariables      Rank2Types      GADTs+     TemplateHaskell   Exposed-Modules:+     Data.FiniteField+     Data.FiniteField.Base      Data.FiniteField.PrimeField      Data.FiniteField.SomeNat 

@@ -0,0 +1,18 @@+-----------------------------------------------------------------------------+-- |+-- module      :  Data.FiniteField+-- Copyright   :  (c) Masahiro Sakai 2013+-- License     :  BSD-style+--+-- Maintainer  :  masahiro.sakai@gmail.com+-- Stability   :  provisional+-- Portability :  portable+--+-----------------------------------------------------------------------------+module Data.FiniteField+  ( module Data.FiniteField.Base+  , module Data.FiniteField.PrimeField+  ) where++import Data.FiniteField.Base+import Data.FiniteField.PrimeField

@@ -0,0 +1,30 @@+-----------------------------------------------------------------------------+-- |+-- module      :  Data.FiniteField.Base+-- Copyright   :  (c) Masahiro Sakai 2013+-- License     :  BSD-style+--+-- Maintainer  :  masahiro.sakai@gmail.com+-- Stability   :  provisional+-- Portability :  portable+--+-----------------------------------------------------------------------------+module Data.FiniteField.Base+  ( FiniteField (..)+  ) where++import Data.Ratio+import qualified Numeric.Algebra as Alg++-- | Type class for finite fields+class Fractional k => FiniteField k where+  -- | The order is number of elements of a finite field @k@.+  -- It of the form @p^n@, where @p@ is  prime number called the characteristic+  -- of the field, and @n@ is a positive integer.+  order   :: k -> Integer++  -- | The characteristic of a field, @p@.+  char    :: k -> Integer++  -- | The inverse of Frobenius endomorphism @x@ ↦ @x^p@.+  pthRoot :: k -> k

@@ -1,4 +1,4 @@-{-# LANGUAGE ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable #-}+{-# LANGUAGE ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable, TemplateHaskell #-} {-# OPTIONS_GHC -Wall #-} ----------------------------------------------------------------------------- -- |@@ -8,9 +8,9 @@ -- -- Maintainer  :  masahiro.sakai@gmail.com -- Stability   :  provisional--- Portability :  non-portable (ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable)+-- Portability :  non-portable (ScopedTypeVariables, MultiParamTypeClasses, DeriveDataTypeable, TemplateHaskell) ----- Finite field of prime order Fp.+-- Finite field of prime order p, Fp = Z/pZ. -- -- References: --@@ -20,16 +20,21 @@ module Data.FiniteField.PrimeField   ( PrimeField   , toInteger+  -- * Template haskell utilities+  -- $TH+  , primeField   ) where  import Prelude hiding (toInteger) import Control.DeepSeq import Data.Ratio (denominator, numerator) import Data.Typeable+import qualified Language.Haskell.TH as TH import qualified Numeric.Algebra as Alg import qualified TypeLevel.Number.Nat as TL+import Data.FiniteField.Base --- | Finite field of prime order Fp.+-- | Finite field of prime order p, Fp = Z/pZ. -- -- NB: Primality of @p@ is assumed, but not checked. newtype PrimeField p = PrimeField Integer deriving (Eq, Typeable)@@ -78,6 +83,11 @@   PrimeField a `max` PrimeField b = PrimeField (a `max` b)   PrimeField a `min` PrimeField b = PrimeField (a `min` b) +instance TL.Nat p => FiniteField (PrimeField p) where+  order _   = TL.toInt (undefined :: p)+  char _    = TL.toInt (undefined :: p)+  pthRoot a = a+ -- ---------------------------------------------------------------------------  instance TL.Nat p => Alg.Multiplicative (PrimeField p) where@@ -127,8 +137,14 @@  -- --------------------------------------------------------------------------- -{--type GF2 = PrimeField (SuccessorTo (SuccessorTo Zero))-type GF3 = PrimeField (SuccessorTo (SuccessorTo (SuccessorTo Zero)))-type GF5 = PrimeField (SuccessorTo (SuccessorTo (SuccessorTo (SuccessorTo (SuccessorTo Zero)))))--}+-- | Create a PrimeField type+primeField :: Integer -> TH.TypeQ+primeField n+  | n <= 0    = error "primeField: negative value"+  | otherwise = [t| PrimeField $(TL.natT n) |]++-- $TH+-- Here is usage example for primeField:+--+-- > a :: $(primeField 15485867)+-- > a = 1

@@ -1,14 +1,15 @@ {-# LANGUAGE TemplateHaskell, ScopedTypeVariables #-} +import Test.HUnit hiding (Test) import Test.QuickCheck import Test.Framework.TH import Test.Framework.Providers.QuickCheck2+import Test.Framework.Providers.HUnit  import Control.Monad import Data.Numbers.Primes (primes) -import Data.FiniteField.PrimeField (PrimeField)-import qualified Data.FiniteField.PrimeField as PrimeField+import Data.FiniteField import Data.FiniteField.SomeNat (SomeNat (..)) import qualified Data.FiniteField.SomeNat as SomeNat import TypeLevel.Number.Nat@@ -106,11 +107,24 @@       a /= 0 ==> a * (recip a) == 1  -- ----------------------------------------------------------------------+-- pthRoot +prop_pthRoot =+  forAll smallPrimes $ \(SomeNat (_ :: p)) ->+    forAll arbitrary $ \(a :: PrimeField p) ->+      pthRoot a ^ char a == a++-- ----------------------------------------------------------------------+ prop_intToSomeNat = do   forAll arbitrary $ \n ->     case SomeNat.fromInteger (abs n) of       SomeNat m -> abs n == toInt m++case_primeFieldT = a @?= 1+  where+    a :: $(primeField 15485867)+    a = 15485867 + 1  ------------------------------------------------------------------------