help/nextcand

   1 NAME
   2     nextcand - next candidate for primeness
   3
   4 SYNOPSIS
   5     nextcand(n [,count [, skip [, residue [,modulus]]]])
   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     residue     integer, defaults to 0
  12     modulus     integer, defaults to 1
  13
  14     return      integer
  15
  16 DESCRIPTION
  17     If modulus is nonzero, nextcand(n, count, skip, residue, modulus)
  18     returns the least integer i greater than abs(n) expressible as
  19     residue + k * modulus, where k is an integer, for which
  20     ptest(i,count,skip) == 1, or if there is no such integer, zero.
  21
  22     If abs(n) < 2^32, count >= 0, and the returned value i is not zero, then
  23     i is definitely prime.  If count is not zero and the returned
  24     value i is greater than 2^32, then i is probably prime, particularly
  25     if abs(count) > 1.
  26
  27     If skip == 0, and abs(n) >= 2^32 or count < 0, the probabilistic test with
  28     random bases is used so that if n is composite the
  29     probability that it passes ptest() is less than 4^-abs(count).
  30
  31     If skip == 1 (the default value), the bases used in the probabilistic
  32     test are the first abs(count) primes 2, 3, 5, ...
  33
  34     For other values of skip, the bases used in the probabilistic tests
  35     are the abs(count) consecutive integers, skip, skip + 1, skip + 2, ...
  36
  37     In any case, if the integer returned by nextcand() is not zero,
  38     all integers between abs(n) and that integer are composite.
  39
  40     If modulus is zero, the value returned is that of residue if this is
  41     greater than abs(n) and ptest(residue,count,skip) = 1. Otherwise
  42     zero is returned.
  43
  44 RUNTIME
  45     The runtime for v = nextcand(n, ...) will depend strongly on the
  46     number and nature of the integers between n and v.  If this number
  47     is reasonably large the size of count is largely irrelevant as the
  48     compositeness of the numbers between n and v will usually be
  49     determined by the test for small prime factors or one pseudoprime
  50     test with some base b.  If N > 1, count should be positive so that
  51     candidates divisible by small primes will be passed over quickly.
  52
  53     On the average for random n with large word-count N, the runtime seems
  54     to be roughly K/N^3 some constant K.
  55
  56 EXAMPLE
  57     > print nextcand(50), nextcand(112140,-2), nextcand(112140,-3)
  58     53 112141 112153
  59
  60     > print nextcand(100,1,1,1,6), nextcand(100,1,1,-1,6)
  61     103 101
  62
  63     > print nextcand(100,1,1,2,6), nextcand(100,1,1,303,202)
  64     1 101
  65
  66     > print nextcand(2e60, 1, 1, 31, 1e30)
  67     2000000000000000000000000000053000000000000000000000000000031
  68
  69 LIMITS
  70     none
  71
  72 LINK LIBRARY
  73     int znextcand(ZVALUE n, long count, long skip, ZVALUE res, ZVALUE mod,
  74         ZVALUE *cand)
  75
  76 SEE ALSO
  77     prevcand, ptest
  78