michael@0: # This Source Code Form is subject to the terms of the Mozilla Public
michael@0: # License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0: # file, You can obtain one at http://mozilla.org/MPL/2.0/.
michael@0: 
michael@0: =head1 NAME
michael@0: 
michael@0:  isprime - probabilistic primality testing
michael@0: 
michael@0: =head1 SYNOPSIS
michael@0: 
michael@0:  isprime <a>
michael@0: 
michael@0: =head1 DESCRIPTION
michael@0: 
michael@0: The B<isprime> program attempts to determine whether the arbitrary
michael@0: precision integer I<a> is prime.  It first tests I<a> for divisibility
michael@0: by the first 170 or so small primes, and assuming I<a> is not
michael@0: divisible by any of these, applies 15 iterations of the Rabin-Miller
michael@0: probabilistic primality test.
michael@0: 
michael@0: If the program discovers that the number is composite, it will print:
michael@0: 
michael@0:  Not prime (reason)
michael@0: 
michael@0: Where I<reason> is either:
michael@0: 
michael@0: 	divisible by small prime x
michael@0: 
michael@0: Or:
michael@0: 
michael@0: 	failed nth pseudoprime test
michael@0: 
michael@0: In the first case, I<x> indicates the first small prime factor that
michael@0: was found.  In the second case, I<n> indicates which of the
michael@0: pseudoprime tests failed (numbered from 1)
michael@0: 
michael@0: If this happens, the number is definitely not prime.  However, if the
michael@0: number succeeds, this message results:
michael@0: 
michael@0:  Probably prime, 1 in 4^15 chance of false positive
michael@0: 
michael@0: If this happens, the number is prime with very high probability, but
michael@0: its primality has not been absolutely proven, only demonstrated to a
michael@0: very convincing degree.
michael@0: 
michael@0: The value I<a> can be input in standard decimal notation, or, if it is
michael@0: prefixed with I<Ox>, it will be read as hexadecimal.
michael@0: 
michael@0: =head1 ENVIRONMENT
michael@0: 
michael@0: You can control how many iterations of Rabin-Miller are performed on
michael@0: the candidate number by setting the I<RM_TESTS> environment variable
michael@0: to an integer value before starting up B<isprime>.  This will change
michael@0: the output slightly if the number passes all the tests.
michael@0: 
michael@0: =head1 SEE ALSO
michael@0: 
michael@0: gcd(1), invmod(1), lap(1)
michael@0: 
michael@0: =head1 AUTHOR
michael@0: 
michael@0:  Michael J. Fromberger <sting@linguist.dartmouth.edu>
michael@0:  Thayer School of Engineering, Hanover, New Hampshire, USA