help/ptest

   1 NAME
   2     ptest - probabilistic test of primality
   3
   4 SYNOPSIS
   5     ptest(n [,count [,skip]])
   6
   7 TYPES
   8     n           integer
   9     count       integer with absolute value less than 2^24, defaults to 1
  10     skip        integer, defaults to 1
  11
  12     return      0 or 1
  13
  14 DESCRIPTION
  15     In ptest(n, ...) the sign of n is ignored; here we assume n >= 0.
  16
  17     ptest(n, count, skip) always returns 1 if n is prime; equivalently,
  18     if 0 is returned then n is not prime.
  19
  20     If n is even, 1 is returned only if n = 2.
  21
  22     If count >= 0 and n < 2^32, ptest(n,...) essentially calls isprime(n)
  23     and returns 1 only if n is prime.
  24
  25     If count >= 0, n > 2^32, and n is divisible by a prime <= 101, then
  26     ptest(n,...) returns 0.
  27
  28     If count is zero, and none of the above cases have resulted in 0 being
  29     returned, 1 is returned.
  30
  31     In other cases (which includes all cases with count < 0), tests are
  32     made for abs(count) bases b:  if n - 1 = 2^s * m where m is odd,
  33     the test for base b of possible primality is passed if b is a
  34     multiple of n or b^m = 1 (mod n) or b^(2^j * m) = n - 1 (mod n) for
  35     some j where 0 <= j < s; integers that pass the test are called
  36     strong probable primes for the base b; composite integers that pass
  37     the test are called strong pseudoprimes for the base b; ( XXX ) Since
  38     the test for base b depends on b % n, and bases 0, 1 and n - 1 are
  39     trivial (n is always a strong probable prime for these bases), it
  40     is sufficient to consider 1 < b < n - 1.
  41
  42     The bases for ptest(n, count, skip) are selected as follows:
  43
  44         skip = 0:       random in [2, n-2]
  45         skip = 1:       successive primes 2, 3, 5, ...
  46                         not exceeding min(n, 65536)
  47         otherwise:      successive integers skip, skip + 1, ...,
  48                         skip+abs(count)-1
  49
  50     In particular, if m > 0, ptest(n, -m, 2) == 1 shows that n is either
  51     prime or a strong pseudoprime for all positive integer bases <= m + 1.
  52     If 1 < b < n - 1, ptest(n, -1, b) == 1 if and only if n is
  53     a strong pseudoprime for the base b.
  54
  55     For the random case (skip = 0), the probability that any one test
  56     with random base b will return 1 if n is composite is always
  57     less than 1/4, so with count = k, the probability is less
  58     than 1/4^k.  For most values of n the probability is much
  59     smaller, possible zero.
  60
  61 RUNTIME
  62     If n is composite, ptest(n, 1, skip) is usually faster than
  63     ptest(n, -1, skip), much faster if n is divisible by a small
  64     prime.  If n is prime, ptest(n, -1, skip) is usually faster than
  65     ptest(n, 1, skip), possibly much faster if n < 2^32, only slightly
  66     faster if n > 2^32.
  67
  68     If n is a large prime (say 50 or more decimal digits), the runtime
  69     for ptest(n, count, skip) will usually be roughly K * abs(count) *
  70     ln(n)^3 for some constant K. ( XXX )  For composite n with
  71     highbit(n) = N, the compositeness is detected quickly if n is
  72     divisible by a small prime and count >= 0; otherwise, if count is
  73     not zero, usually only one test is required to establish
  74     compositeness, so the runtime will probably be about K * N^3.   For
  75     some rare values of composite n, high values of count may be
  76     required to establish the compositeness.
  77
  78     If the word-count for n is less than conf("redc2"), REDC algorithms
  79     are used in evaluating ptest(n, count, skip) when small-factor
  80     cases have been eliminated.  For small word-counts (say < 10)
  81     this may more than double the speed of evaluation compared with
  82     the standard algorithms.
  83
  84 EXAMPLE
  85     > print ptest(103^3 * 3931, 0), ptest(4294967291,0)
  86     1 1
  87
  88     In the first example, the first argument > 2^32; in the second the
  89     first argument is the largest prime less than 2^32.
  90
  91     > print ptest(121,-1,2), ptest(121,-1,3), ptest(121,-2,2)
  92     0 1 0
  93
  94     121 is the smallest strong pseudoprime to the base 3.
  95
  96     > x = 151 * 751 * 28351
  97     > print x, ptest(x,-4,1), ptest(x,-5,1)
  98     3215031751 1 0
  99
 100     The integer x in this example is the smallest positive integer that is
 101     a strong pseudoprime to each of the first four primes 2, 3, 5, 7, but
 102     not to base 11.  The probability that ptest(x,-1,0) will return 1 is
 103     about .23.
 104
 105     > for (i = 0; i < 11; i++) print ptest(91,-1,0),:; print;
 106     0 0 0 1 0 0 0 0 0 0 1
 107
 108     The results for this example depend on the state of the
 109     random number generator; the expectation is that 1 will occur twice.
 110
 111     > a = 24444516448431392447461 * 48889032896862784894921;
 112     > print ptest(a,11,1), ptest(a,12,1), ptest(a,20,2), ptest(a,21,2)
 113     1 0 1 0
 114
 115     These results show that a is a strong pseudoprime for all 11 prime
 116     bases less than or equal to 31, and for all positive integer bases
 117     less than or equal to 21, but not for the bases 37 and 22.  The
 118     probability that ptest(a,-1,0) (or ptest(a,1,0)) will return 1 is
 119     about 0.19.
 120
 121 LIMITS
 122     none
 123
 124 LINK LIBRARY
 125     BOOL qprimetest(NUMBER *n, NUMBER *count, NUMBER *skip)
 126     BOOL zprimetest(ZVALUE n, long count, long skip)
 127
 128 SEE ALSO
 129     isprime, prevcand, nextcand
 130