The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/isprime.pod
security/nss/lib/freebl/mpi/doc/isprime.pod
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:889d75c38080 |
|---|---|
| 1 # This Source Code Form is subject to the terms of the Mozilla Public | |
| 2 # License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 3 # file, You can obtain one at http://mozilla.org/MPL/2.0/. | |
| 4 | |
| 5 =head1 NAME | |
| 6 | |
| 7 isprime - probabilistic primality testing | |
| 8 | |
| 9 =head1 SYNOPSIS | |
| 10 | |
| 11 isprime <a> | |
| 12 | |
| 13 =head1 DESCRIPTION | |
| 14 | |
| 15 The B<isprime> program attempts to determine whether the arbitrary | |
| 16 precision integer I<a> is prime. It first tests I<a> for divisibility | |
| 17 by the first 170 or so small primes, and assuming I<a> is not | |
| 18 divisible by any of these, applies 15 iterations of the Rabin-Miller | |
| 19 probabilistic primality test. | |
| 20 | |
| 21 If the program discovers that the number is composite, it will print: | |
| 22 | |
| 23 Not prime (reason) | |
| 24 | |
| 25 Where I<reason> is either: | |
| 26 | |
| 27 divisible by small prime x | |
| 28 | |
| 29 Or: | |
| 30 | |
| 31 failed nth pseudoprime test | |
| 32 | |
| 33 In the first case, I<x> indicates the first small prime factor that | |
| 34 was found. In the second case, I<n> indicates which of the | |
| 35 pseudoprime tests failed (numbered from 1) | |
| 36 | |
| 37 If this happens, the number is definitely not prime. However, if the | |
| 38 number succeeds, this message results: | |
| 39 | |
| 40 Probably prime, 1 in 4^15 chance of false positive | |
| 41 | |
| 42 If this happens, the number is prime with very high probability, but | |
| 43 its primality has not been absolutely proven, only demonstrated to a | |
| 44 very convincing degree. | |
| 45 | |
| 46 The value I<a> can be input in standard decimal notation, or, if it is | |
| 47 prefixed with I<Ox>, it will be read as hexadecimal. | |
| 48 | |
| 49 =head1 ENVIRONMENT | |
| 50 | |
| 51 You can control how many iterations of Rabin-Miller are performed on | |
| 52 the candidate number by setting the I<RM_TESTS> environment variable | |
| 53 to an integer value before starting up B<isprime>. This will change | |
| 54 the output slightly if the number passes all the tests. | |
| 55 | |
| 56 =head1 SEE ALSO | |
| 57 | |
| 58 gcd(1), invmod(1), lap(1) | |
| 59 | |
| 60 =head1 AUTHOR | |
| 61 | |
| 62 Michael J. Fromberger <sting@linguist.dartmouth.edu> | |
| 63 Thayer School of Engineering, Hanover, New Hampshire, USA |
