Copyright	(c) 2011 Daniel Fischer
License	MIT
Maintainer	Daniel Fischer <daniel.is.fischer@googlemail.com>
Safe Haskell	None
Language	Haskell2010

Math.NumberTheory.Primes.Testing.Certificates

Contents

Certificates
Arguments
- Weaken proofs to arguments
- Prove valid arguments
Determine and prove whether a number is prime or composite
- Checks for the paranoid

Description

Certificates for primality or compositeness.

Synopsis

data Certificate
- = Composite !CompositenessProof
- | Prime !PrimalityProof
argueCertificate :: Certificate -> Either CompositenessArgument PrimalityArgument
data CompositenessProof
composite :: CompositenessProof -> Integer
data PrimalityProof
cprime :: PrimalityProof -> Integer
data CompositenessArgument
- = Divisors {
  - compo, firstDivisor, secondDivisor :: Integer
  }
- | Fermat {
  - compo, fermatBase :: Integer
  }
- | Lucas {
  - compo :: Integer
  }
- | Belief {
  - compo :: Integer
  }
data PrimalityArgument
- = Pock {
  - aprime :: Integer
  - largeFactor, smallFactor :: Integer
  - factorList :: [(Integer, Word, Integer, PrimalityArgument)]
  }
- | Division {
  - aprime, alimit :: Integer
  }
- | Obvious {
  - aprime :: Integer
  }
- | Assumption {
  - aprime :: Integer
  }
arguePrimality :: PrimalityProof -> PrimalityArgument
argueCompositeness :: CompositenessProof -> CompositenessArgument
verifyPrimalityArgument :: PrimalityArgument -> Maybe PrimalityProof
verifyCompositenessArgument :: CompositenessArgument -> Maybe CompositenessProof
certify :: Integer -> Certificate
checkCertificate :: Certificate -> Bool
checkCompositenessProof :: CompositenessProof -> Bool
checkPrimalityProof :: PrimalityProof -> Bool

Certificates

data Certificate Source #

A certificate of either compositeness or primality of an Integer. Only numbers > 1 can be certified, trying to create a certificate for other numbers raises an error.

Constructors

Composite !CompositenessProof
Prime !PrimalityProof

Instances

Show Certificate Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods showsPrec :: Int -> Certificate -> ShowS # show :: Certificate -> String # showList :: [Certificate] -> ShowS #

argueCertificate :: Certificate -> Either CompositenessArgument PrimalityArgument Source #

Eliminate Certificate.

data CompositenessProof Source #

A proof of compositeness of a positive number. The type is abstract to ensure the validity of proofs.

Instances

Show CompositenessProof Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods showsPrec :: Int -> CompositenessProof -> ShowS # show :: CompositenessProof -> String # showList :: [CompositenessProof] -> ShowS #

composite :: CompositenessProof -> Integer Source #

The number whose compositeness is proved.

data PrimalityProof Source #

A proof of primality of a positive number. The type is abstract to ensure the validity of proofs.

Instances

Show PrimalityProof Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods showsPrec :: Int -> PrimalityProof -> ShowS # show :: PrimalityProof -> String # showList :: [PrimalityProof] -> ShowS #

cprime :: PrimalityProof -> Integer Source #

The number whose primality is proved.

Arguments

data CompositenessArgument Source #

An argument for compositeness of a number (which must be > 1). CompositenessProofs translate directly to CompositenessArguments, correct arguments can be transformed into proofs. This type allows the manipulation of proofs while maintaining their correctness. The only way to access components of a CompositenessProof except the composite is through this type.

Constructors

Divisors	`compo == firstDiv*secondDiv`, where all are `> 1`
Fields compo, firstDivisor, secondDivisor :: Integer
Fermat	`compo` fails the strong Fermat test for `fermatBase`
Fields compo, fermatBase :: Integer
Lucas	`compo` fails the Lucas-Selfridge test
Fields compo :: Integer
Belief	No particular reason given
Fields compo :: Integer

Instances

Eq CompositenessArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods (==) :: CompositenessArgument -> CompositenessArgument -> Bool # (/=) :: CompositenessArgument -> CompositenessArgument -> Bool #
Ord CompositenessArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods compare :: CompositenessArgument -> CompositenessArgument -> Ordering # (<) :: CompositenessArgument -> CompositenessArgument -> Bool # (<=) :: CompositenessArgument -> CompositenessArgument -> Bool # (>) :: CompositenessArgument -> CompositenessArgument -> Bool # (>=) :: CompositenessArgument -> CompositenessArgument -> Bool # max :: CompositenessArgument -> CompositenessArgument -> CompositenessArgument # min :: CompositenessArgument -> CompositenessArgument -> CompositenessArgument #
Read CompositenessArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods readsPrec :: Int -> ReadS CompositenessArgument # readList :: ReadS [CompositenessArgument] # readPrec :: ReadPrec CompositenessArgument # readListPrec :: ReadPrec [CompositenessArgument] #
Show CompositenessArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods showsPrec :: Int -> CompositenessArgument -> ShowS # show :: CompositenessArgument -> String # showList :: [CompositenessArgument] -> ShowS #

data PrimalityArgument Source #

An argument for primality of a number (which must be > 1). PrimalityProofs translate directly to PrimalityArguments, correct arguments can be transformed into proofs. This type allows the manipulation of proofs while maintaining their correctness. The only way to access components of a PrimalityProof except the prime is through this type.

Constructors

Pock	A suggested Pocklington certificate
Fields aprime :: Integer largeFactor, smallFactor :: Integer factorList :: [(Integer, Word, Integer, PrimalityArgument)]
Division	Primality should be provable by trial division to `alimit`
Fields aprime, alimit :: Integer
Obvious	`aprime` is said to be obviously prime, that holds for primes `< 30`
Fields aprime :: Integer
Assumption	Primality assumed
Fields aprime :: Integer

Instances

Eq PrimalityArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods (==) :: PrimalityArgument -> PrimalityArgument -> Bool # (/=) :: PrimalityArgument -> PrimalityArgument -> Bool #
Ord PrimalityArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods compare :: PrimalityArgument -> PrimalityArgument -> Ordering # (<) :: PrimalityArgument -> PrimalityArgument -> Bool # (<=) :: PrimalityArgument -> PrimalityArgument -> Bool # (>) :: PrimalityArgument -> PrimalityArgument -> Bool # (>=) :: PrimalityArgument -> PrimalityArgument -> Bool # max :: PrimalityArgument -> PrimalityArgument -> PrimalityArgument # min :: PrimalityArgument -> PrimalityArgument -> PrimalityArgument #
Read PrimalityArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods readsPrec :: Int -> ReadS PrimalityArgument # readList :: ReadS [PrimalityArgument] # readPrec :: ReadPrec PrimalityArgument # readListPrec :: ReadPrec [PrimalityArgument] #
Show PrimalityArgument Source #
Instance details Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal Methods showsPrec :: Int -> PrimalityArgument -> ShowS # show :: PrimalityArgument -> String # showList :: [PrimalityArgument] -> ShowS #

Weaken proofs to arguments

arguePrimality :: PrimalityProof -> PrimalityArgument Source #

arguePrimality transforms a proof of primality into an argument for primality.

argueCompositeness :: CompositenessProof -> CompositenessArgument Source #

argueCompositeness transforms a proof of compositeness into an argument for compositeness.

Prove valid arguments

verifyPrimalityArgument :: PrimalityArgument -> Maybe PrimalityProof Source #

verifyPrimalityArgument checks the given argument and constructs a proof from it, if it is valid. For the explicit arguments, this is simple and resonably fast, for an Assumption, the verification uses certify and hence may take a long time.

verifyCompositenessArgument :: CompositenessArgument -> Maybe CompositenessProof Source #

verifyCompositenessArgument checks the given argument and constructs a proof from it, if it is valid. For the explicit arguments, this is simple and resonably fast, for a Belief, the verification uses certify and hence may take a long time.

Determine and prove whether a number is prime or composite

certify :: Integer -> Certificate Source #

certify n constructs, for n > 1, a proof of either primality or compositeness of n. This may take a very long time if the number has no small(ish) prime divisors

Checks for the paranoid

checkCertificate :: Certificate -> Bool Source #

Check the validity of a Certificate. Since it should be impossible to construct invalid certificates by the public interface, this should never return False.

checkCompositenessProof :: CompositenessProof -> Bool Source #

Check the validity of a CompositenessProof. Since it should be impossible to create invalid proofs by the public interface, this should never return False.

checkPrimalityProof :: PrimalityProof -> Bool Source #

Check the validity of a PrimalityProof. Since it should be impossible to create invalid proofs by the public interface, this should never return False.