Math::ProvablePrime - Generate a provable prime number, in pure Perl


    #The returned prime will be 512 bits long
    #(i.e., the first and last bits will be 1)
    #and will be an instance of Math::BigInt.
    my $prime = Math::ProvablePrime::find(512);


There’s not much more to say: this module returns a prime number of a specified bit length.

The specific algorithm is Maurer’s algorithm. The logic in this module is ported from a Python implementation first posted at


This module will be deprecated once Math::Prime::Util is installable without a compiler. (There is pure-Perl logic in that distribution; the install logic just needs to be tweaked.) Math::Prime::Util is faster and has a maintainer who understands the mathematics behind all of this much better than I do.

Math::ProvablePrime is too slow for its intended purpose (i.e., to provide pure-Perl primes), and really, I don’t have the mathematical background that would justify its continued maintenance.

If you have any objection, please let me know.


This module is too slow for practical use in pure Perl. If a recognized alternate backend for Math::BigInt is available, though, then this module will use that to achieve reasonable (though still unimpressive) speed.

Recognized alternate backends are (in order of preference):

Math::BigInt::BitVect and Math::BigInt::FastCalc are also recognized, but these don’t seem to achieve speed that’s practical for use in, e.g., creation of RSA keys.


This module is released under the same license as Perl.