The Tor Browser / file revision

 # 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