NAME

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

VERSION

       Version 0.73

SYNOPSIS

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 <http://www.ellipsa.eu/public/primo/primo.html>
       certificates, as all the method verifications are coded.

SEE ALSO

       Math::Prime::Util

AUTHORS

       Dana Jacobsen <dana@acm.org>

COPYRIGHT

       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.