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

   1 /* -*-c-*-
   2  *
   3  * $Id: gfreduce.h,v 1.2 2004/03/21 22:52:06 mdw Exp $
   4  *
   5  * Reduction modulo sparse binary polynomials
   6  *
   7  * (c) 2004 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: gfreduce.h,v $
  33  * Revision 1.2  2004/03/21 22:52:06  mdw
  34  * Merge and close elliptic curve branch.
  35  *
  36  * Revision 1.1.2.1  2004/03/21 22:39:46  mdw
  37  * Elliptic curves on binary fields work.
  38  *
  39  */
  40
  41 #ifndef CATACOMB_GFREDUCE_H
  42 #define CATACOMB_GFREDUCE_H
  43
  44 #ifdef __cplusplus
  45   extern "C" {
  46 #endif
  47
  48 /*----- Header files ------------------------------------------------------*/
  49
  50 #ifndef CATACOMB_GF_H
  51 #  include "gf.h"
  52 #endif
  53
  54 /*----- Data structures ---------------------------------------------------*/
  55
  56 typedef struct gfreduce_instr {
  57   unsigned op;                          /* Instruction opcode */
  58   size_t arg;                           /* Immediate argument */
  59 } gfreduce_instr;
  60
  61 enum {
  62   GFRI_LOAD,                            /* Load @p[arg]@ */
  63   GFRI_LSL,                             /* XOR with @w << arg@ */
  64   GFRI_LSR,                             /* XOR with @w >> arg@ */
  65   GFRI_STORE,                           /* Store @p[arg]@ */
  66   GFRI_MAX
  67 };
  68
  69 typedef struct gfreduce {
  70   size_t lim;                           /* Word of degree bit */
  71   mpw mask;                             /* Mask for degree word */
  72   mp *p;                                /* Copy of the polynomial */
  73   size_t in;                            /* Number of instruction words */
  74   gfreduce_instr *iv, *liv;             /* Vector of instructions */
  75 } gfreduce;
  76
  77 /*----- Functions provided ------------------------------------------------*/
  78
  79 /* --- @gfreduce_create@ --- *
  80  *
  81  * Arguments:   @gfreduce *r@ = structure to fill in
  82  *              @mp *x@ = a (hopefully sparse) polynomial
  83  *
  84  * Returns:     ---
  85  *
  86  * Use:         Initializes a context structure for reduction.
  87  */
  88
  89 extern void gfreduce_create(gfreduce */*r*/, mp */*p*/);
  90
  91 /* --- @gfreduce_destroy@ --- *
  92  *
  93  * Arguments:   @gfreduce *r@ = structure to free
  94  *
  95  * Returns:     ---
  96  *
  97  * Use:         Reclaims the resources from a reduction context.
  98  */
  99
 100 extern void gfreduce_destroy(gfreduce */*r*/);
 101
 102 /* --- @gfreduce_dump@ --- *
 103  *
 104  * Arguments:   @gfreduce *r@ = structure to dump
 105  *              @FILE *fp@ = file to dump on
 106  *
 107  * Returns:     ---
 108  *
 109  * Use:         Dumps a reduction context.
 110  */
 111
 112 extern void gfreduce_dump(gfreduce */*r*/, FILE */*fp*/);
 113
 114 /* --- @gfreduce_do@ --- *
 115  *
 116  * Arguments:   @gfreduce *r@ = reduction context
 117  *              @mp *d@ = destination
 118  *              @mp *x@ = source
 119  *
 120  * Returns:     Destination, @x@ reduced modulo the reduction poly.
 121  */
 122
 123 extern mp *gfreduce_do(gfreduce */*r*/, mp */*d*/, mp */*x*/);
 124
 125 /* --- @gfreduce_sqrt@ --- *
 126  *
 127  * Arguments:   @gfreduce *r@ = pointer to reduction context
 128  *              @mp *d@ = destination
 129  *              @mp *x@ = some polynomial
 130  *
 131  * Returns:     The square root of @x@ modulo @r->p@, or null.
 132  */
 133
 134 extern mp *gfreduce_sqrt(gfreduce */*r*/, mp */*d*/, mp */*x*/);
 135
 136 /* --- @gfreduce_trace@ --- *
 137  *
 138  * Arguments:   @gfreduce *r@ = pointer to reduction context
 139  *              @mp *x@ = some polynomial
 140  *
 141  * Returns:     The trace of @x@. (%$\Tr(x)=x + x^2 + \cdots + x^{2^{m-1}}$%
 142  *              if %$x \in \gf{2^m}$%).
 143  */
 144
 145 extern int gfreduce_trace(gfreduce */*r*/, mp */*x*/);
 146
 147 /* --- @gfreduce_halftrace@ --- *
 148  *
 149  * Arguments:   @gfreduce *r@ = pointer to reduction context
 150  *              @mp *d@ = destination
 151  *              @mp *x@ = some polynomial
 152  *
 153  * Returns:     The half-trace of @x@.
 154  *              (%$\HfTr(x)= x + x^{2^2} + \cdots + x^{2^{m-1}}$%
 155  *              if %$x \in \gf{2^m}$% with %$m$% odd).
 156  */
 157
 158 extern mp *gfreduce_halftrace(gfreduce */*r*/, mp */*d*/, mp */*x*/);
 159
 160 /* --- @gfreduce_quadsolve@ --- *
 161  *
 162  * Arguments:   @gfreduce *r@ = pointer to reduction context
 163  *              @mp *d@ = destination
 164  *              @mp *x@ = some polynomial
 165  *
 166  * Returns:     A polynomial @y@ such that %$y^2 + y = x$%, or null.
 167  */
 168
 169 extern mp *gfreduce_quadsolve(gfreduce */*r*/, mp */*d*/, mp */*x*/);
 170
 171 /* --- @gfreduce_exp@ --- *
 172  *
 173  * Arguments:   @gfreduce *gr@ = pointer to reduction context
 174  *              @mp *d@ = fake destination
 175  *              @mp *a@ = base
 176  *              @mp *e@ = exponent
 177  *
 178  * Returns:     Result, %$a^e \bmod m$%.
 179  */
 180
 181 extern mp *gfreduce_exp(gfreduce */*gr*/, mp */*d*/, mp */*a*/, mp */*e*/);
 182
 183 /*----- That's all, folks -------------------------------------------------*/
 184
 185 #ifdef __cplusplus
 186   }
 187 #endif
 188
 189 #endif