help/rcpow

   1 NAME
   2     rcpow - REDC powers
   3
   4 SYNOPSIS
   5     rcpow(x, k, m)
   6
   7 TYPES
   8     x           integer
   9     k           nonnegative integer
  10     m           odd positive integer
  11
  12     return      integer v, 0 <= v < m.
  13
  14 DESCRIPTION
  15     Let B be the base calc uses for representing integers internally
  16     (B = 2^16 for 32-bit machines, 2^32 for 64-bit machines) and N the
  17     number of words (base-B digits) in the representation of m.  Then
  18     rcpow(x,k,m) returns the value of B^-N * (B^N * x)^k % m, w here
  19     the inverse implicit in B^-N is modulo m and the modulus operator %
  20     gives the least nonnegative residue.  Note that rcpow(x,0,m) =
  21     rcin(1,m), rcpow(x,1,m) = x % m; rcpow(x,2,m) = rcsq(x,m).
  22
  23     The normal use of rcpow() may be said to be that of finding the
  24     encoded value of the k-th power of an integer modulo m:
  25
  26             rcin(x^k, m) = rcpow(rcin(x,m), k, m),
  27
  28     from which one gets:
  29
  30             x^k % m  = rcout(rcpow(rcin(x,m), k, m), m).
  31
  32     If x^k % m is to be evaluated for the same k and m and several
  33     values of x, it may be worth while to first evaluate:
  34
  35             a = minv(rcpow(1, k, m), m);
  36
  37     and use:
  38
  39         x^k % m = a * rcpow(x, k, m) % m.
  40
  41 RUNTIME
  42     If the value of m in rcpow(x,k,m) is being used for the first time
  43     in a REDC function, the information required for the REDC
  44     algorithms is calculated and stored for future use, possibly
  45     replacing an already stored valued, in a table covering up to 5
  46     (i.e. MAXREDC) values of m.  The runtime required for this is about
  47     two times that required for multiplying two N-word integers.
  48
  49     Two algorithms are available for evaluating rcpow(x,k,m), the one
  50     which is usually faster for small N is used when N <
  51     config("redc2"); the other is usually faster for larger N. If
  52     config("redc2") is set at about 90 and 0 <= x < m, the runtime
  53     required for rcpow(x,k,m) is at most about f times the runtime
  54     required for ilog2(k) N-word by N-word multiplications, where f
  55     increases from about 1.3 for N = 1 to near 4 for N > 90.  More
  56     runtime may be required if x has to be reduced modulo m.
  57
  58 EXAMPLE
  59     Using a 64-bit machine with B = 2^32:
  60
  61     > m = 1234567;
  62     > x = 15;
  63     > print rcout(rcpow((rcin(x,m), m - 1, m), m), pmod(x, m-1, m)
  64     783084 783084
  65
  66 LIMITS
  67     none
  68
  69 LINK LIBRARY
  70     void zredcpower(REDC *rp, ZVALUE z1, ZVALUE z2, ZVALUE *res)
  71
  72 SEE ALSO
  73     rcin, rcout, rcmul, rcsq
  74