rcpow

Calc Software Package for Number Calc

NAME
    rcpow - REDC powers

SYNOPSIS
    rcpow(x, k, m)

TYPES
    x		integer
    k		nonnegative integer
    m		odd positive integer

    return	integer v, 0 <= v < m.

DESCRIPTION
    Let B be the base calc uses for representing integers internally
    (B = 2^16 for 32-bit machines, 2^32 for 64-bit machines) and N the
    number of words (base-B digits) in the representation of m.	 Then
    rcpow(x,k,m) returns the value of B^-N * (B^N * x)^k % m, w here
    the inverse implicit in B^-N is modulo m and the modulus operator %
    gives the least nonnegative residue.  Note that rcpow(x,0,m) =
    rcin(1,m), rcpow(x,1,m) = x % m; rcpow(x,2,m) = rcsq(x,m).

    The normal use of rcpow() may be said to be that of finding the
    encoded value of the k-th power of an integer modulo m:

	    rcin(x^k, m) = rcpow(rcin(x,m), k, m),

    from which one gets:

	    x^k % m  = rcout(rcpow(rcin(x,m), k, m), m).

    If x^k % m is to be evaluated for the same k and m and several
    values of x, it may be worth while to first evaluate:

	    a = minv(rcpow(1, k, m), m);

    and use:

	x^k % m = a * rcpow(x, k, m) % m.

RUNTIME
    If the value of m in rcpow(x,k,m) is being used for the first time
    in a REDC function, the information required for the REDC
    algorithms is calculated and stored for future use, possibly
    replacing an already stored valued, in a table covering up to 5
    (i.e. MAXREDC) values of m.	 The runtime required for this is about
    two times that required for multiplying two N-word integers.

    Two algorithms are available for evaluating rcpow(x,k,m), the one
    which is usually faster for small N is used when N <
    config("redc2"); the other is usually faster for larger N. If
    config("redc2") is set at about 90 and 0 <= x < m, the runtime
    required for rcpow(x,k,m) is at most about f times the runtime
    required for ilog2(k) N-word by N-word multiplications, where f
    increases from about 1.3 for N = 1 to near 4 for N > 90.  More
    runtime may be required if x has to be reduced modulo m.

EXAMPLE
    Using a 64-bit machine with B = 2^32:

    ; m = 1234567;
    ; x = 15;
    ; print rcout(rcpow((rcin(x,m), m - 1, m), m), pmod(x, m-1, m)
    783084 783084

LIMITS
    none

LINK LIBRARY
    void zredcpower(REDC *rp, ZVALUE z1, ZVALUE z2, ZVALUE *res)

SEE ALSO
    rcin, rcout, rcmul, rcsq

## Copyright (C) 1999  Landon Curt Noll
##
## Calc is open software; you can redistribute it and/or modify it under
## the terms of the version 2.1 of the GNU Lesser General Public License
## as published by the Free Software Foundation.
##
## Calc is distributed in the hope that it will be useful, but WITHOUT
## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
## or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
## Public License for more details.
##
## A copy of version 2.1 of the GNU Lesser General Public License is
## distributed with calc under the filename COPYING-LGPL.  You should have
## received a copy with calc; if not, write to Free Software Foundation, Inc.
## 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
##
## @(#) $Revision: 29.3 $
## @(#) $Id: rcpow,v 29.3 2006/05/07 07:25:46 chongo Exp $
## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/rcpow,v $
##
## Under source code control:	1996/02/25 02:22:21
## File existed as early as:	1996
##
## chongo <was here> /\oo/\	http://www.isthe.com/chongo/
## Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/