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

   1 /* -*-c-*-
   2  *
   3  * $Id: mpbarrett.h,v 1.1 1999/12/10 23:22:00 mdw Exp $
   4  *
   5  * Barrett modular reduction
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mpbarrett.h,v $
  33  * Revision 1.1  1999/12/10 23:22:00  mdw
  34  * Barrett reduction support: works with even moduli.
  35  *
  36  */
  37
  38 /*----- Notes on Barrett reduction ----------------------------------------*
  39  *
  40  * Barrett reduction is a technique for computing modular residues.  Unlike
  41  * Montgomery reduction, it doesn't have restrictions on the modulus (except
  42  * that it be positive) and doesn't confuse matters by putting an extra
  43  * factor all the way through your computation.
  44  *
  45  * It's useful for slightly less heavy-duty work than Montgomery reduction
  46  * because the precomputation phase is rather simpler, involving a single
  47  * division operation.
  48  *
  49  * Sometimes it's useful to exponentiate modulo an even number, so there's a
  50  * modexp routine provided which uses Barrett reduction rather than
  51  * Montgomery reduction.  This is handy when you're working on indices in an
  52  * even-order cyclic group or something.
  53  */
  54
  55 #ifndef CATACOMB_MPBARRETT_H
  56 #define CATACOMB_MPBARRETT_H
  57
  58 #ifdef __cplusplus
  59   extern "C" {
  60 #endif
  61
  62 /*----- Header files ------------------------------------------------------*/
  63
  64 #ifndef CATACOMB_MP_H
  65 #  include "mp.h"
  66 #endif
  67
  68 /*----- Data structures ---------------------------------------------------*/
  69
  70 typedef struct mpbarrett {
  71   mp *m;
  72   mp *mu;
  73   size_t k;
  74 } mpbarrett;
  75
  76 /*----- Functions provided ------------------------------------------------*/
  77
  78 /* --- @mpbarrett_create@ --- *
  79  *
  80  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
  81  *              @mp *m@ = modulus to work to
  82  *
  83  *
  84  * Returns:     ---
  85  *
  86  * Use:         Initializes a Barrett reduction context ready for use.
  87  */
  88
  89 extern void mpbarrett_create(mpbarrett */*mb*/, mp */*m*/);
  90
  91 /* --- @mpbarrett_destroy@ --- *
  92  *
  93  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
  94  *
  95  * Returns:     ---
  96  *
  97  * Use:         Destroys a Barrett reduction context releasing any resources
  98  *              claimed.
  99  */
 100
 101 extern void mpbarrett_destroy(mpbarrett */*mb*/);
 102
 103 /* --- @mpbarrett_reduce@ --- *
 104  *
 105  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
 106  *              @mp *d@ = destination for result
 107  *              @mp *m@ = number to reduce
 108  *
 109  * Returns:     The residue of @m@ modulo the number in the reduction
 110  *              context.
 111  *
 112  * Use:         Performs an efficient modular reduction.  The argument is
 113  *              assumed to be positive.
 114  */
 115
 116 extern mp *mpbarrett_reduce(mpbarrett */*mb*/, mp */*d*/, mp */*m*/);
 117
 118 /* --- @mpbarrett_exp@ --- *
 119  *
 120  * Arguments:   @mpbarrett *mb@ = pointer to Barrett reduction context
 121  *              @mp *d@ = fake destination
 122  *              @mp *a@ = base
 123  *              @mp *e@ = exponent
 124  *
 125  * Returns:     Result, %$a^e \bmod m$%.
 126  */
 127
 128 extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/);
 129
 130 /*----- That's all, folks -------------------------------------------------*/
 131
 132 #ifdef __cplusplus
 133   }
 134 #endif
 135
 136 #endif