---
name: "Math::Prime::Util::PrimalityProving"
section: "3pm"
platform: "linux"
package: "libmath-prime-util-perl"
version: "0.73-2+b5"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/Math::Prime::Util::PrimalityProving"
---

# Math::Prime::Util::PrimalityProving(3pm)

Primality proofs and certificates

## 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.