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

   1 /* -*-c-*-
   2  *
   3  * Montgomery 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 #ifndef CATACOMB_MPMONT_H
  29 #define CATACOMB_MPMONT_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #ifndef CATACOMB_MP_H
  38 #  include "mp.h"
  39 #endif
  40
  41 /*----- Notes on Montgomery reduction -------------------------------------*
  42  *
  43  * Given a little bit of precomputation, Montgomery reduction enables modular
  44  * reductions of products to be calculated rather rapidly, without recourse
  45  * to annoying things like division.
  46  *
  47  * Before starting, you need to do a little work.  In particular, the
  48  * following things need to be worked out:
  49  *
  50  *   * %$m$%, which is the modulus you'll be working with.  This must be odd,
  51  *     otherwise the whole thing doesn't work.  You're better off using
  52  *     Barrett reduction if your modulus might be even.
  53  *
  54  *   * %$b$%, the radix of the number system you're in (here, it's
  55  *     @MPW_MAX + 1@).
  56  *
  57  *   * %$-m^{-1} \bmod b$%, a useful number for the reduction step.  (This
  58  *     means that the modulus mustn't be even.  This shouldn't be a problem.)
  59  *
  60  *   * %$R = b^n > m > b^{n - 1}$%, or at least %$\log_2 R$%.
  61  *
  62  *   * %$R \bmod m$% and %$R^2 \bmod m$%, which are useful when doing
  63  *     calculations such as exponentiation.
  64  *
  65  * The result of a Montgomery reduction of %$x$% is %$x R^{-1} \bmod m$%,
  66  * which doesn't look ever-so useful.  The trick is to initially apply a
  67  * factor of %$R$% to all of your numbers so that when you multiply and
  68  * perform a Montgomery reduction you get %$(x R \cdot y R) R^{-1} \bmod m$%,
  69  * which is just %$x y R \bmod m$%.  Thanks to distributivity, even additions
  70  * and subtractions can be performed on numbers in this form -- the extra
  71  * factor of %$R$% just runs through all the calculations until it's finally
  72  * stripped out by a final reduction operation.
  73  */
  74
  75 /*----- Data structures ---------------------------------------------------*/
  76
  77 /* --- A Montgomery reduction context --- */
  78
  79 typedef struct mpmont {
  80   mp *m;                                /* Modulus */
  81   mp *mi;                               /* %$-m^{-1} \bmod R$% */
  82   size_t n;                             /* %$\log_b R$% */
  83   mp *r, *r2;                           /* %$R \bmod m$%, %$R^2 \bmod m$% */
  84 } mpmont;
  85
  86 /*----- Functions provided ------------------------------------------------*/
  87
  88 /* --- @mpmont_create@ --- *
  89  *
  90  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
  91  *              @mp *m@ = modulus to use
  92  *
  93  * Returns:     Zero on success, nonzero on error.
  94  *
  95  * Use:         Initializes a Montgomery reduction context ready for use.
  96  *              The argument @m@ must be a positive odd integer.
  97  */
  98
  99 extern int mpmont_create(mpmont */*mm*/, mp */*m*/);
 100
 101 /* --- @mpmont_destroy@ --- *
 102  *
 103  * Arguments:   @mpmont *mm@ = pointer to a Montgomery reduction context
 104  *
 105  * Returns:     ---
 106  *
 107  * Use:         Disposes of a context when it's no longer of any use to
 108  *              anyone.
 109  */
 110
 111 extern void mpmont_destroy(mpmont */*mm*/);
 112
 113 /* --- @mpmont_reduce@ --- *
 114  *
 115  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 116  *              @mp *d@ = destination
 117  *              @mp *a@ = source, assumed positive
 118  *
 119  * Returns:     Result, %$a R^{-1} \bmod m$%.
 120  */
 121
 122 extern mp *mpmont_reduce(mpmont */*mm*/, mp */*d*/, mp */*a*/);
 123
 124 /* --- @mpmont_mul@ --- *
 125  *
 126  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 127  *              @mp *d@ = destination
 128  *              @mp *a, *b@ = sources, assumed positive
 129  *
 130  * Returns:     Result, %$a b R^{-1} \bmod m$%.
 131  */
 132
 133 extern mp *mpmont_mul(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*b*/);
 134
 135 /* --- @mpmont_expr@ --- *
 136  *
 137  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 138  *              @mp *d@ = fake destination
 139  *              @mp *a@ = base
 140  *              @mp *e@ = exponent
 141  *
 142  * Returns:     Result, %$(a R^{-1})^e R \bmod m$%.  This is useful if
 143  *              further modular arithmetic is to be performed on the result.
 144  */
 145
 146 extern mp *mpmont_expr(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/);
 147
 148 /* --- @mpmont_exp@ --- *
 149  *
 150  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 151  *              @mp *d@ = fake destination
 152  *              @mp *a@ = base
 153  *              @mp *e@ = exponent
 154  *
 155  * Returns:     Result, %$a^e \bmod m$%.
 156  */
 157
 158 extern mp *mpmont_exp(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/);
 159
 160 /* --- @mpmont_mexpr@ --- *
 161  *
 162  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 163  *              @mp *d@ = fake destination
 164  *              @const mp_expfactor *f@ = pointer to array of factors
 165  *              @size_t n@ = number of factors supplied
 166  *
 167  * Returns:     If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
 168  *              exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
 169  *              is:
 170  *
 171  *              %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
 172  *
 173  *
 174  *              except that the %$g_i$% and result are in Montgomery form.
 175  */
 176
 177 extern mp *mpmont_mexpr(mpmont */*mm*/, mp */*d*/,
 178                         const mp_expfactor */*f*/, size_t /*n*/);
 179
 180 /* --- @mpmont_mexp@ --- *
 181  *
 182  * Arguments:   @mpmont *mm@ = pointer to Montgomery reduction context
 183  *              @mp *d@ = fake destination
 184  *              @const mp_expfactor *f@ = pointer to array of factors
 185  *              @size_t n@ = number of factors supplied
 186  *
 187  * Returns:     Product of bases raised to exponents, all mod @m@.
 188  *
 189  * Use:         Convenient interface over @mpmont_mexpr@.
 190  */
 191
 192 extern mp *mpmont_mexp(mpmont */*mm*/, mp */*d*/,
 193                        const mp_expfactor */*f*/, size_t /*n*/);
 194
 195 /*----- That's all, folks -------------------------------------------------*/
 196
 197 #ifdef __cplusplus
 198   }
 199 #endif
 200
 201 #endif