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