c_cpp/etc/calc/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
  75 ## Copyright (C) 1999  Landon Curt Noll
  76 ##
  77 ## Calc is open software; you can redistribute it and/or modify it under
  78 ## the terms of the version 2.1 of the GNU Lesser General Public License
  79 ## as published by the Free Software Foundation.
  80 ##
  81 ## Calc is distributed in the hope that it will be useful, but WITHOUT
  82 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  83 ## or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  84 ## Public License for more details.
  85 ##
  86 ## A copy of version 2.1 of the GNU Lesser General Public License is
  87 ## distributed with calc under the filename COPYING-LGPL.  You should have
  88 ## received a copy with calc; if not, write to Free Software Foundation, Inc.
  89 ## 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  90 ##
  91 ## @(#) $Revision: 30.1 $
  92 ## @(#) $Id: rcpow,v 30.1 2007/03/16 11:10:42 chongo Exp $
  93 ## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/rcpow,v $
  94 ##
  95 ## Under source code control:   1996/02/25 02:22:21
  96 ## File existed as early as:    1996
  97 ##
  98 ## chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  99 ## Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/