Dana Jacobsen > Math-Prime-Util-0.37 > Math::Prime::Util::PrimalityProving

Math-Prime-Util-0.37.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 0
View/Report Bugs
Module Version: 0.37   Source   Latest Release: Math-Prime-Util-0.51

# NAME

Math::Prime::Util::PrimalityProving - Primality proofs and certificates

Version 0.37

# DESCRIPTION

Routines to support primality proofs and certificate verification.

# FUNCTIONS

## primality_proof_lucas

Given a positive number `n` as input, performs a full factorization of `n-1`, then attempts a Lucas test on the result. A Pratt-style certificate is returned. Note that if the input is composite, this will take a very long time to return.

## primality_proof_bls75

Given a positive number `n` as input, performs a partial factorization of `n-1`, then attempts a proof using theorem 5 of Brillhart, Lehmer, and Selfridge's 1975 paper. This can take a long time to return if given a composite, though it should not be anywhere near as long as the Lucas test.

## convert_array_cert_to_string

Takes as input a Perl structure certificate, used by Math::Prime::Util from version 0.26 through 0.29, and converts it to a multi-line text certificate starting with "[MPU - Primality Certificate]". This is the new format produced and processed by Math::Prime::Util, Math::Prime::Util::GMP, and associated tools.

## verify_cert

Takes a MPU primality certificate and verifies that it does prove the primality of the number it represents (the N after the "Proof for:" line). For backwards compatibility, if given an old-style Perl structure, it will be converted then verified.

The return value will be `0` (failed to verify) or `1` (verified). A result of `0` does not indicate the number is composite; it only indicates the proof given is not sufficient.

If the certificate is malformed, the routine will carp a warning in addition to returning 0. If the `verbose` option is set (see "prime_set_config") then if the validation fails, the reason for the failure is printed in addition to returning 0. If the `verbose` option is set to 2 or higher, then a message indicating success and the certificate type is also printed.

A later release may add support for Primo certificates, as all the method verifications are coded.

Math::Prime::Util

# AUTHORS

Dana Jacobsen <dana@acm.org>