Math::Primality - Advanced Primality Algorithms using GMP
Version 0.03_02
use Math::Primality qw/:all/;
my $t1 = is_pseudoprime($x,$base);
my $t2 = is_strong_pseudoprime($x);
print "Prime!" if is_prime($outrageously_large_prime);
my $t3 = next_prime($x);
Math::Primality implements is_prime() and next_prime() as a replacement for Math::PARI::is_prime(). It uses the GMP library through Math::GMPz. The is_prime() method is actually a Baillie-PSW primality test which consists of three steps:
At any point the function may return as definitely composite. If not, N has passed the strong Baillie-PSW test and is either prime or a strong Baillie-PSW pseudoprime. To date no counterexample (Baillie-PSW strong pseudoprime) is known to exist for N < 10^15. Baillie-PSW requires O((log n)^3) bit operations. See http://www.trnicely.net/misc/bpsw.html for a more thorough introduction to the Baillie-PSW test. Also see http://mpqs.free.fr/LucasPseudoprimes.pdf for a more theoretical introduction to the Baillie-PSW test.
Returns true if $n is a base $b pseudoprime, otherwise false. The variable $n should be a Perl integer or Math::GMPz object.
The default base of 2 is used if no base is given. Base 2 pseudoprimes are often called Fermat pseudoprimes.
if ( is_pseudoprime($n,$b) ) {
# it's a pseudoprime
} else {
# not a psuedoprime
}
A pseudoprime is a number that satisfies Fermat's Little Theorm, that is, $b^ ($n - 1) = 1 mod $n.
Returns true if $n is a base $b strong pseudoprime, false otherwise. The variable $n should be a Perl integer or a Math::GMPz object. Strong psuedoprimes are often called Miller-Rabin pseudoprimes.
The default base of 2 is used if no base is given.
if ( is_strong_pseudoprime($n,$b) ) {
# it's a strong pseudoprime
} else {
# not a strong psuedoprime
}
A strong pseudoprime to $base is an odd number $n with ($n - 1) = $d * 2^$s that either satisfies
$s and $d are calculated with the helper function _find_s_d() and the second condition is checked by sucessive squaring $base^$d and reducing that mod $n.
Returns true if $n is a strong Lucas-Selfridge pseudoprime, false otherwise. The variable $n should be a Perl integer or a Math::GMPz object.
if ( is_strong_lucas_pseudoprime($n) ) {
# it's a strong Lucas-Selfridge pseudoprime
} else {
# not a strong Lucas-Selfridge psuedoprime
# i.e. definitely composite
}
If we let
Then a strong Lucas-Selfridge pseudoprime is an odd, non-perfect square number $n with that satisfies either
($d/$n) refers to the Legendre symbol. The tuple ($D, $P, $Q) is determined by the helper function _find_dpq_selfridge(). $d and $s are determined by the helper function _find_s_d().
Returns true if number is prime, false if number is composite.
if ( is_prime($n) ) {
# it's a prime
} else {
# definitely composite
}
is_prime() is implemented using the BPSW algorithim which is a combination of two probable-prime algorithims, the strong Miller-Rabin test and the strong Lucas-Selfridge test. While no psuedoprime has been found for N < 10^15, this does not mean there is not a pseudoprime.
The strong Miller-Rabin test is implemented by is_strong_pseudoprime(). The strong Lucas-Selfridge test is implemented by is_strong_lucas_pseudoprime().
Given a number, produces the next prime number.
my $q = next_prime($n);
Each next greatest odd number is checked until one is found to be prime
Checking of primality is implemented by is_prime()
Given a number, produces the previous prime number.
my $q = prev_prime($n);
Each previous odd number is checked until one is found to be prime. prev_prime(2) or for any number less than 2 returns undef
Checking of primality is implemented by is_prime()
Returns the count of the number of primes less than or equal to $n. This is the prime counting function.
Jonathan Leto, <jonathan at leto.net>
Please report any bugs or feature requests to bug-math-primality at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Math::Primality. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
The algorithms in this module have been ported from the C source code in bpsw1.zip by Thomas R. Nicely, available at http://www.trnicely.net/misc/bpsw.html or in the spec/bpsw directory of the Math::Primality source code. Without his research this module would not exist.
You can find documentation for this module with the perldoc command.
perldoc Math::Primality
You can also look for information at:
Copyright 2009 Jonathan Leto, all rights reserved.
This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
