c_cpp/etc/calc/help/rcsq

   1 NAME
   2     rcsq - REDC squaring
   3
   4 SYNOPSIS
   5     rcsq(x, m)
   6
   7 TYPES
   8     x           integer
   9     m           odd positive integer
  10
  11     return      integer v, 0 <= v < m.
  12
  13 DESCRIPTION
  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)
  16     and N the number of words (base-B digits) in the representation
  17     of m.  Then rcsq(x,m) returns the value of B^-N * x^2 % m,
  18     where the inverse implicit in B^-N is modulo m
  19     and the modulus operator % gives the least non-negative residue.
  20
  21     The normal use of rcsq() may be said to be that of squaring modulo m a
  22     value encoded by rcin() and REDC functions, as in:
  23
  24             rcin(x^2, m) = rcsq(rcin(x,m), m)
  25
  26     from which we get:
  27
  28             x^2 % m = rcout(rcsq(rcin(x,m), m), m)
  29
  30     Alternatively, x^2 % m may be evaluated usually more quickly by:
  31
  32             x^2 % m = rcin(rcsq(x,m), m).
  33
  34 RUNTIME
  35     If the value of m in rcsq(x,m) is being used for the first time in
  36     a REDC function, the information required for the REDC algorithms
  37     is calculated and stored for future use, possibly replacing an
  38     already stored valued, in a table covering up to 5 (i.e. MAXREDC)
  39     values of m.  The runtime required for this is about two times that
  40     required for multiplying two N-word integers.
  41
  42     Two algorithms are available for evaluating rcsq(x, m), the one
  43     which is usually faster for small N is used when N <
  44     config("redc2"); the other is usually faster for larger N. If
  45     config("redc2") is set at about 90 and 0 <= x < m, the runtime
  46     required for rcsq(x, m)i is at most about f times the runtime
  47     required for an N-word by N-word multiplication, where f increases
  48     from about 1.1 for N = 1 to near 2.8 for N > 90.  More runtime may
  49     be required if x has to be reduced modulo m.
  50
  51 EXAMPLE
  52     Using a 64-bit machine with B = 2^32:
  53
  54     ; for (i = 0; i < 9; i++) print rcsq(i,9),:; print;
  55     0 7 1 0 4 4 0 1 7
  56
  57     ; for (i = 0; i < 9; i++) print rcin((rcsq(i,9),:; print;
  58     0 1 4 0 7 7 0 4 1
  59
  60 LIMITS
  61     none
  62
  63 LINK LIBRARY
  64     void zredcsquare(REDC *rp, ZVALUE z1, ZVALUE *res)
  65
  66 SEE ALSO
  67     rcin, rcout, rcmul, rcpow
  68
  69 ## Copyright (C) 1999  Landon Curt Noll
  70 ##
  71 ## Calc is open software; you can redistribute it and/or modify it under
  72 ## the terms of the version 2.1 of the GNU Lesser General Public License
  73 ## as published by the Free Software Foundation.
  74 ##
  75 ## Calc is distributed in the hope that it will be useful, but WITHOUT
  76 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  77 ## or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  78 ## Public License for more details.
  79 ##
  80 ## A copy of version 2.1 of the GNU Lesser General Public License is
  81 ## distributed with calc under the filename COPYING-LGPL.  You should have
  82 ## received a copy with calc; if not, write to Free Software Foundation, Inc.
  83 ## 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  84 ##
  85 ## @(#) $Revision: 30.1 $
  86 ## @(#) $Id: rcsq,v 30.1 2007/03/16 11:10:42 chongo Exp $
  87 ## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/rcsq,v $
  88 ##
  89 ## Under source code control:   1996/02/25 02:22:21
  90 ## File existed as early as:    1996
  91 ##
  92 ## chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  93 ## Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/