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