1NAME
2    rcin - encode for REDC algorithms
3
4SYNOPSIS
5    rcin(x, m)
6
7TYPES
8    x		integer
9    m		odd positive integer
10
11    return	integer v, 0 <= v < m.
12
13DESCRIPTION
14    Let B be the base calc uses for representing integers internally
15    (B = 2^16 for 32-bit machines, 2^32 for 64-bit machines) and N the
16    number of words (base-B digits) in the representation of m.	 Then
17    rcin(x,m) returns the value of B^N * x % m, where the modulus
18    operator % here gives the least nonnegative residue.
19
20    If y = rcin(x,m), x % m may be evaluated by x % m = rcout(y, m).
21
22    The "encoding" method of using rcmul(), rcsq(), and rcpow() for
23    evaluating products, squares and powers modulo m correspond to the
24    formulae:
25
26	    rcin(x * y, m) = rcmul(rcin(x,m), rcin(y,m), m);
27
28	    rcin(x^2, m) = rcsq(rcin(x,m), m);
29
30	    rcin(x^k, m) = rcpow(rcin(x,m), k, m).
31
32    Here k is any nonnegative integer.	Using these formulae may be
33    faster than direct evaluation of x * y % m, x^2 % m, x^k % m.
34    Some encoding and decoding may be bypassed by formulae like:
35
36	    x * y % m = rcin(rcmul(x, y, m), m).
37
38    If m is a divisor of B^N - h for some integer h, rcin(x,m) may be
39    computed by using rcin(x,m) = h * x % m.  In particular, if
40    m is a divisor of B^N - 1 and 0 <= x < m, then rcin(x,m) = x.
41    For example if B = 2^16 or 2^32, this is so for m = (B^N - 1)/d
42    for the divisors d = 3, 5, 15, 17, ...
43
44RUNTIME
45    The first time a particular value for m is used in rcin(x, m),
46    the information required for the REDC algorithms is
47    calculated and stored for future use in a table covering up to
48    5 (i.e. MAXREDC) values of m.  The runtime required for this is about
49    two that required for multiplying two N-word integers.
50
51    Two algorithms are available for evaluating rcin(x, m), the one
52    which is usually faster for small N is used when N <
53    config("pow2"); the other is usually faster for larger N. If
54    config("pow2") is set at about 200 and x has both been reduced
55    modulo m, the runtime required for rcin(x, m) is at most about f
56    times the runtime required for an N-word by N-word multiplication,
57    where f increases from about 1.3 for N = 1 to near 2 for N > 200.
58    More runtime may be required if x has to be reduced modulo m.
59
60EXAMPLE
61    Using a 64-bit machine with B = 2^32:
62
63    ; for (i = 0; i < 9; i++) print rcin(x, 9),:; print;
64    0 4 8 3 7 2 6 1 5
65
66LIMITS
67    none
68
69LINK LIBRARY
70    void zredcencode(REDC *rp, ZVALUE z1, ZVALUE *res)
71
72SEE ALSO
73   rcout, rcmul, rcsq, rcpow
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## Under source code control:	1996/02/25 02:22:21
92## File existed as early as:	1996
93##
94## chongo <was here> /\oo/\	http://www.isthe.com/chongo/
95## Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/
96