Portability	Non-portable (GHC extensions)
Stability	Provisional
Maintainer	Daniel Fischer <daniel.is.fischer@googlemail.com>

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

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

argueCertificate :: Certificate -> Either CompositenessArgument PrimalityArgument Source

data CompositenessProof Source

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

Instances

Show CompositenessProof

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

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 :: Integer firstDivisor :: Integer secondDivisor :: Integer
Fermat	`compo` fails the strong Fermat test for `fermatBase`
Fields compo :: Integer fermatBase :: Integer
Lucas	`compo` fails the Lucas-Selfridge test
Fields compo :: Integer
Belief	No particular reason given
Fields compo :: Integer

Instances

Eq CompositenessArgument
Ord CompositenessArgument
Read CompositenessArgument
Show CompositenessArgument

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 :: Integer smallFactor :: Integer factorList :: [(Integer, Int, Integer, PrimalityArgument)]
Division	Primality should be provable by trial division to `alimit`
Fields aprime :: Integer 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
Ord PrimalityArgument
Read PrimalityArgument
Show PrimalityArgument

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.