1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/doc/isprime.pod Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,63 @@
1.4 +# This Source Code Form is subject to the terms of the Mozilla Public
1.5 +# License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 +# file, You can obtain one at http://mozilla.org/MPL/2.0/.
1.7 +
1.8 +=head1 NAME
1.9 +
1.10 + isprime - probabilistic primality testing
1.11 +
1.12 +=head1 SYNOPSIS
1.13 +
1.14 + isprime <a>
1.15 +
1.16 +=head1 DESCRIPTION
1.17 +
1.18 +The B<isprime> program attempts to determine whether the arbitrary
1.19 +precision integer I<a> is prime. It first tests I<a> for divisibility
1.20 +by the first 170 or so small primes, and assuming I<a> is not
1.21 +divisible by any of these, applies 15 iterations of the Rabin-Miller
1.22 +probabilistic primality test.
1.23 +
1.24 +If the program discovers that the number is composite, it will print:
1.25 +
1.26 + Not prime (reason)
1.27 +
1.28 +Where I<reason> is either:
1.29 +
1.30 + divisible by small prime x
1.31 +
1.32 +Or:
1.33 +
1.34 + failed nth pseudoprime test
1.35 +
1.36 +In the first case, I<x> indicates the first small prime factor that
1.37 +was found. In the second case, I<n> indicates which of the
1.38 +pseudoprime tests failed (numbered from 1)
1.39 +
1.40 +If this happens, the number is definitely not prime. However, if the
1.41 +number succeeds, this message results:
1.42 +
1.43 + Probably prime, 1 in 4^15 chance of false positive
1.44 +
1.45 +If this happens, the number is prime with very high probability, but
1.46 +its primality has not been absolutely proven, only demonstrated to a
1.47 +very convincing degree.
1.48 +
1.49 +The value I<a> can be input in standard decimal notation, or, if it is
1.50 +prefixed with I<Ox>, it will be read as hexadecimal.
1.51 +
1.52 +=head1 ENVIRONMENT
1.53 +
1.54 +You can control how many iterations of Rabin-Miller are performed on
1.55 +the candidate number by setting the I<RM_TESTS> environment variable
1.56 +to an integer value before starting up B<isprime>. This will change
1.57 +the output slightly if the number passes all the tests.
1.58 +
1.59 +=head1 SEE ALSO
1.60 +
1.61 +gcd(1), invmod(1), lap(1)
1.62 +
1.63 +=head1 AUTHOR
1.64 +
1.65 + Michael J. Fromberger <sting@linguist.dartmouth.edu>
1.66 + Thayer School of Engineering, Hanover, New Hampshire, USA
