NAME¶
Math::Prime::Util::PrimalityProving - Primality proofs and certificates
VERSION¶
Version 0.46
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.