chiark - git - mdw - catacomb/blob - math/mpbarrett.h

   1 /* -*-c-*-
   2  *
   3  * Barrett modular reduction
   4  *
   5  * (c) 1999 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Notes on Barrett reduction ----------------------------------------*
  29  *
  30  * Barrett reduction is a technique for computing modular residues.  Unlike
  31  * Montgomery reduction, it doesn't have restrictions on the modulus (except
  32  * that it be positive) and doesn't confuse matters by putting an extra
  33  * factor all the way through your computation.
  34  *
  35  * It's useful for slightly less heavy-duty work than Montgomery reduction
  36  * because the precomputation phase is rather simpler, involving a single
  37  * division operation.
  38  *
  39  * Sometimes it's useful to exponentiate modulo an even number, so there's a
  40  * modexp routine provided which uses Barrett reduction rather than
  41  * Montgomery reduction.  This is handy when you're working on indices in an
  42  * even-order cyclic group or something.
  43  *
  44  * In more detail: suppose that %$b^{k-1} \le m < b^k$%.  Let %$\mu = {}$%
  45  * %$\lfloor b^{2k}/m \rfloor$%; %$\mu$% is a scaled approximation to the
  46  * reciprocal %$1/m$%.  Now, suppose we're given some %$a$% with
  47  * %$0 \le a < b^{2k}$%.  The first step is to calculate an approximation
  48  * %$q = \lfloor \mu \lfloor a/b^{k-1} \rfloor/b^{k+1} \rfloor$% to the
  49  * quotient %$a/m$%.  Then we have:
  50  *
  51  *      %$\lfloor a/m - a/b^{2k} - b^{k-1}/m + 1/b^{k+1} \rfloor \le {}$%
  52  *              %$q \le \lfloor a/m \rfloor
  53  *
  54  * But by assumption %$a < b^{2k}$% and %$2^{k-1} \le m$% so
  55  *
  56  *      %$\lfloor a/m \rfloor - 2 \le q \le \lfloor a/m \rfloor$%
  57  *
  58  * Now we approximate the remainder by calculating %$r = a - q m$%.
  59  * Certainly %$r \equiv a \pmod{m}$%; and
  60  *
  61  *      %$0 \le r \le (a - m \lfloor a/m \rfloor) + 2 m < 3 m$%.
  62  *
  63  * So the remainder can be fixed up with at most two conditional
  64  * subtractions.
  65  */
  66
  67 #ifndef CATACOMB_MPBARRETT_H
  68 #define CATACOMB_MPBARRETT_H
  69
  70 #ifdef __cplusplus
  71   extern "C" {
  72 #endif
  73
  74 /*----- Header files ------------------------------------------------------*/
  75
  76 #ifndef CATACOMB_MP_H
  77 #  include "mp.h"
  78 #endif
  79
  80 /*----- Data structures ---------------------------------------------------*/
  81
  82 typedef struct mpbarrett {
  83   mp *m;
  84   mp *mu;
  85   size_t k;
  86 } mpbarrett;
  87
  88 /*----- Functions provided ------------------------------------------------*/
  89
  90 /* --- @mpbarrett_create@ --- *
  91  *
  92  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
  93  *              @mp *m@ = modulus to work to
  94  *
  95  * Returns:     Zero on success, nonzero on error.
  96  *
  97  * Use:         Initializes a Barrett reduction context ready for use.
  98  */
  99
 100 extern int mpbarrett_create(mpbarrett */*mb*/, mp */*m*/);
 101
 102 /* --- @mpbarrett_destroy@ --- *
 103  *
 104  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
 105  *
 106  * Returns:     ---
 107  *
 108  * Use:         Destroys a Barrett reduction context releasing any resources
 109  *              claimed.
 110  */
 111
 112 extern void mpbarrett_destroy(mpbarrett */*mb*/);
 113
 114 /* --- @mpbarrett_reduce@ --- *
 115  *
 116  * Arguments:   @const mpbarrett *mb@ = pointer to Barrett reduction context
 117  *              @mp *d@ = destination for result
 118  *              @mp *m@ = number to reduce
 119  *
 120  * Returns:     The residue of @m@ modulo the number in the reduction
 121  *              context.
 122  *
 123  * Use:         Performs an efficient modular reduction.
 124  */
 125
 126 extern mp *mpbarrett_reduce(const mpbarrett */*mb*/, mp */*d*/, mp */*m*/);
 127
 128 /* --- @mpbarrett_exp@ --- *
 129  *
 130  * Arguments:   @const mpbarrett *mb@ = pointer to Barrett reduction context
 131  *              @mp *d@ = fake destination
 132  *              @mp *a@ = base
 133  *              @mp *e@ = exponent
 134  *
 135  * Returns:     Result, %$a^e \bmod m$%.
 136  */
 137
 138 extern mp *mpbarrett_exp(const mpbarrett */*mb*/, mp */*d*/,
 139                          mp */*a*/, mp */*e*/);
 140
 141 /* --- @mpbarrett_mexp@ --- *
 142  *
 143  * Arguments:   @const mpbarrett *mb@ = pointer to Barrett reduction context
 144  *              @mp *d@ = fake destination
 145  *              @const mp_expfactor *f@ = pointer to array of factors
 146  *              @size_t n@ = number of factors supplied
 147  *
 148  * Returns:     If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
 149  *              exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
 150  *              is:
 151  *
 152  *              %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
 153  */
 154
 155 extern mp *mpbarrett_mexp(const mpbarrett */*mb*/, mp */*d*/,
 156                           const mp_expfactor */*f*/, size_t /*n*/);
 157
 158 /*----- That's all, folks -------------------------------------------------*/
 159
 160 #ifdef __cplusplus
 161   }
 162 #endif
 163
 164 #endif