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

Module Version: 0.42
Math::Prime::Util::PrimalityProving - Primality proofs and certificates

Version 0.42

Routines to support primality proofs and certificate verification.

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.

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.

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.

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.

Dana Jacobsen <dana@acm.org>

Copyright 2012-2013 by Dana Jacobsen <dana@acm.org>

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

syntax highlighting: