# This Source Code Form is subject to the terms of the Mozilla Public
# License, v. 2.0. If a copy of the MPL was not distributed with this
# file, You can obtain one at http://mozilla.org/MPL/2.0/.

=head1 NAME

 isprime - probabilistic primality testing

=head1 SYNOPSIS

 isprime <a>

=head1 DESCRIPTION

The B<isprime> program attempts to determine whether the arbitrary
precision integer I<a> is prime.  It first tests I<a> for divisibility
by the first 170 or so small primes, and assuming I<a> is not
divisible by any of these, applies 15 iterations of the Rabin-Miller
probabilistic primality test.

If the program discovers that the number is composite, it will print:

 Not prime (reason)

Where I<reason> is either:

	divisible by small prime x

Or:

	failed nth pseudoprime test

In the first case, I<x> indicates the first small prime factor that
was found.  In the second case, I<n> indicates which of the
pseudoprime tests failed (numbered from 1)

If this happens, the number is definitely not prime.  However, if the
number succeeds, this message results:

 Probably prime, 1 in 4^15 chance of false positive

If this happens, the number is prime with very high probability, but
its primality has not been absolutely proven, only demonstrated to a
very convincing degree.

The value I<a> can be input in standard decimal notation, or, if it is
prefixed with I<Ox>, it will be read as hexadecimal.

=head1 ENVIRONMENT

You can control how many iterations of Rabin-Miller are performed on
the candidate number by setting the I<RM_TESTS> environment variable
to an integer value before starting up B<isprime>.  This will change
the output slightly if the number passes all the tests.

=head1 SEE ALSO

gcd(1), invmod(1), lap(1)

=head1 AUTHOR

 Michael J. Fromberger <sting@linguist.dartmouth.edu>
 Thayer School of Engineering, Hanover, New Hampshire, USA