Math.NumberTheory.Primes.Testing.Certificates

Certificates for primality or compositeness.

Certificates

data Certificate

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

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

showsPrec :: Int -> Certificate -> ShowS

show :: Certificate -> String

showList :: [Certificate] -> ShowS

argueCertificate :: Certificate -> Either CompositenessArgument PrimalityArgument

Eliminate Certificate.

data CompositenessProof

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

Instances

Show CompositenessProof

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

showsPrec :: Int -> CompositenessProof -> ShowS

show :: CompositenessProof -> String

showList :: [CompositenessProof] -> ShowS

composite :: CompositenessProof -> Integer

The number whose compositeness is proved.

data PrimalityProof

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

Instances

Show PrimalityProof

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

showsPrec :: Int -> PrimalityProof -> ShowS

show :: PrimalityProof -> String

showList :: [PrimalityProof] -> ShowS

cprime :: PrimalityProof -> Integer

The number whose primality is proved.

Arguments

data CompositenessArgument

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

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

(==) :: CompositenessArgument -> CompositenessArgument -> Bool

(/=) :: CompositenessArgument -> CompositenessArgument -> Bool

Ord CompositenessArgument

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

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

readsPrec :: Int -> ReadS CompositenessArgument

readList :: ReadS [CompositenessArgument]

readPrec :: ReadPrec CompositenessArgument

readListPrec :: ReadPrec [CompositenessArgument]

Show CompositenessArgument

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

showsPrec :: Int -> CompositenessArgument -> ShowS

show :: CompositenessArgument -> String

showList :: [CompositenessArgument] -> ShowS

data PrimalityArgument

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

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

(==) :: PrimalityArgument -> PrimalityArgument -> Bool

(/=) :: PrimalityArgument -> PrimalityArgument -> Bool

Ord PrimalityArgument

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

Defined in Math.NumberTheory.Primes.Testing.Certificates.Internal

Methods

readsPrec :: Int -> ReadS PrimalityArgument

readList :: ReadS [PrimalityArgument]

readPrec :: ReadPrec PrimalityArgument

readListPrec :: ReadPrec [PrimalityArgument]

Show PrimalityArgument

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

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

argueCompositeness :: CompositenessProof -> CompositenessArgument

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

Prove valid arguments

verifyPrimalityArgument :: PrimalityArgument -> Maybe PrimalityProof

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

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

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

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

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

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