module/slib/factor.txi

   1
   2 @defvar prime:prngs
   3
   4 @var{prime:prngs} is the random-state (@pxref{Random Numbers}) used by these
   5 procedures.  If you call these procedures from more than one thread
   6 (or from interrupt), @code{random} may complain about reentrant
   7 calls.
   8 @end defvar
   9 @emph{Note:} The prime test and generation procedures implement (or
  10 use) the Solovay-Strassen primality test. See
  11
  12 @itemize @bullet
  13 @item Robert Solovay and Volker Strassen,
  14 @cite{A Fast Monte-Carlo Test for Primality},
  15 SIAM Journal on Computing, 1977, pp 84-85.
  16 @end itemize
  17
  18
  19 @defun jacobi-symbol p q
  20
  21 Returns the value (+1, @minus{}1, or 0) of the Jacobi-Symbol of
  22 exact non-negative integer @var{p} and exact positive odd integer @var{q}.
  23 @end defun
  24
  25 @defvar prime:trials
  26
  27 @var{prime:trials} the maxinum number of iterations of Solovay-Strassen that will
  28 be done to test a number for primality.
  29 @end defvar
  30
  31 @defun prime? n
  32
  33 Returns @code{#f} if @var{n} is composite; @code{#t} if @var{n} is prime.
  34 There is a slight chance @code{(expt 2 (- prime:trials))} that a
  35 composite will return @code{#t}.
  36 @end defun
  37
  38 @defun primes< start count
  39
  40 Returns a list of the first @var{count} prime numbers less than
  41 @var{start}.  If there are fewer than @var{count} prime numbers
  42 less than @var{start}, then the returned list will have fewer than
  43 @var{start} elements.
  44 @end defun
  45
  46 @defun primes> start count
  47
  48 Returns a list of the first @var{count} prime numbers greater than @var{start}.
  49 @end defun
  50
  51 @defun factor k
  52
  53 Returns a list of the prime factors of @var{k}.  The order of the
  54 factors is unspecified.  In order to obtain a sorted list do
  55 @code{(sort! (factor @var{k}) <)}.
  56 @end defun