isprime.pod (1871B)
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