Jonathan Leto > Math-Primality-0.07 > Math::Primality

Math-Primality-0.07.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 New 1 Open 2
View/Report Bugs
Module Version: 0.07   Source   Latest Release: Math-Primality-0.08

# NAME

Math::Primality - Check for primes with Perl

version 0.07

# SYNOPSIS

```    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); ```

# DESCRIPTION

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 two steps:

• Perform a strong Miller-Rabin probable prime test (base 2) on N
• Perform a strong Lucas-Selfridge test on N (using the parameters suggested by Selfridge)

At any point the function may return 2 which means N is 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.

# NAME

Math::Primality - Advanced Primality Algorithms using GMP

# FUNCTIONS

## is_pseudoprime(\$n,\$b)

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
}```

### Details

A pseudoprime is a number that satisfies Fermat's Little Theorm, that is, \$b^ (\$n - 1) = 1 mod \$n.

## is_strong_pseudoprime(\$n,\$b)

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
}```

### Details

A strong pseudoprime to \$base is an odd number \$n with (\$n - 1) = \$d * 2^\$s that either satisfies

• \$base^\$d = 1 mod \$n
• \$base^(\$d * 2^\$r) = -1 mod \$n, for \$r = 0, 1, ..., \$s-1

### Notes

The second condition is checked by sucessive squaring \$base^\$d and reducing that mod \$n.

## is_strong_lucas_pseudoprime(\$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
}```

### Details

If we let

• \$D be the first element of the sequence 5, -7, 9, -11, 13, ... for which (\$D/\$n) = -1. Let \$P = 1 and \$Q = (1 - \$D) /4
• U(\$P, \$Q) and V(\$P, \$Q) be Lucas sequences
• \$n + 1 = \$d * 2^\$s + 1

Then a strong Lucas-Selfridge pseudoprime is an odd, non-perfect square number \$n with that satisfies either

• U_\$d = 0 mod \$n
• V_(\$d * 2^\$r) = 0 mod \$n, for \$r = 0, 1, ..., \$s-1

### Notes

(\$d/\$n) refers to the Legendre symbol.

## is_prime(\$n)

Returns 2 if \$n is definitely prime, 1 is \$n is a probable prime, 0 if \$n is composite.

```    if ( is_prime(\$n) ) {
# it's a prime
} else {
# definitely composite
}```

### Details

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. A possible improvement would be to instead implement the AKS test which runs in quadratic time and is deterministic with no false-positives.

### Notes

The strong Miller-Rabin test is implemented by is_strong_pseudoprime(). The strong Lucas-Selfridge test is implemented by is_strong_lucas_pseudoprime().

We have implemented some optimizations. We have an array of small primes to check all \$n <= 257. According to http://primes.utm.edu/prove/prove2_3.html if \$n < 9,080,191 is a both a base-31 and a base-73 strong pseudoprime, then \$n is prime. If \$n < 4,759,123,141 is a base-2, base-7 and base-61 strong pseudoprime, then \$n is prime.

## next_prime(\$n)

Given a number, produces the next prime number.

`    my \$q = next_prime(\$n);`

### Details

Each next greatest odd number is checked until one is found to be prime

### Notes

Checking of primality is implemented by is_prime()

## prev_prime(\$n)

Given a number, produces the previous prime number.

`    my \$q = prev_prime(\$n);`

### Details

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

### Notes

Checking of primality is implemented by is_prime()

## prime_count(\$n)

Returns the number of primes less than or equal to \$n.

```    my \$count = prime_count(1000);          # \$count = 168
my \$bigger_count = prime_count(10000);  # \$bigger_count = 1229```

### Details

This is implemented with a simple for loop. The Meissel, Lehmer, Lagarias, Miller, Odlyzko method is considerably faster. A paper can be found at http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf that describes this method in rigorous detail.

### Notes

Checking of primality is implemented by is_prime()

# AUTHORS

Jonathan "Duke" Leto, `<jonathan at leto.net>` Bob Kuo, `<bobjkuo at gmail.com>`

# BUGS

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.

# THANKS

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.

The Math::GMPz module that interfaces with the GMP C-library was written and is maintained by Sysiphus. Without his work, our work would be impossible.

# SUPPORT

You can find documentation for this module with the perldoc command.

`    perldoc Math::Primality`

You can also look for information at:

# ACKNOWLEDGEMENTS

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

# AUTHOR

Jonathan "Duke" Leto <jonathan@leto.net>

This software is copyright (c) 2012 by Leto Labs LLC.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.

syntax highlighting: