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

   1 /* -*-c-*-
   2  *
   3  * Arithmetic on binary polynomials
   4  *
   5  * (c) 2004 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_GF_H
  29 #define CATACOMB_GF_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 #ifndef CATACOMB_GFX_H
  42 #  include "gfx.h"
  43 #endif
  44
  45 /*----- Functions provided ------------------------------------------------*/
  46
  47 /* --- @gf_add@ --- *
  48  *
  49  * Arguments:   @mp *d@ = destination
  50  *              @mp *a, *b@ = sources
  51  *
  52  * Returns:     Result, @a@ added to @b@.
  53  */
  54
  55 extern mp *gf_add(mp */*d*/, mp */*a*/, mp */*b*/);
  56 #define gf_sub gf_add
  57
  58 /* --- @gf_mul@ --- *
  59  *
  60  * Arguments:   @mp *d@ = destination
  61  *              @mp *a, *b@ = sources
  62  *
  63  * Returns:     Result, @a@ multiplied by @b@.
  64  */
  65
  66 extern mp *gf_mul(mp */*d*/, mp */*a*/, mp */*b*/);
  67
  68 /* --- @gf_sqr@ --- *
  69  *
  70  * Arguments:   @mp *d@ = destination
  71  *              @mp *a@ = source
  72  *
  73  * Returns:     Result, @a@ squared.
  74  */
  75
  76 extern mp *gf_sqr(mp */*d*/, mp */*a*/);
  77
  78 /* --- @gf_div@ --- *
  79  *
  80  * Arguments:   @mp **qq, **rr@ = destination, quotient and remainder
  81  *              @mp *a, *b@ = sources
  82  *
  83  * Use:         Calculates the quotient and remainder when @a@ is divided by
  84  *              @b@.  The destinations @*qq@ and @*rr@ must be distinct.
  85  *              Either of @qq@ or @rr@ may be null to indicate that the
  86  *              result is irrelevant.  (Discarding both results is silly.)
  87  *              There is a performance advantage if @a == *rr@.
  88  */
  89
  90 extern void gf_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/);
  91
  92 /* --- @gf_exp@ --- *
  93  *
  94  * Arguments:   @mp *d@ = fake destination
  95  *              @mp *a@ = base
  96  *              @mp *e@ = exponent
  97  *
  98  * Returns:     Result, %$a^e$%.
  99  */
 100
 101 extern mp *gf_exp(mp */*d*/, mp */*a*/, mp */*e*/);
 102
 103 /* --- @gf_irreduciblep@ --- *
 104  *
 105  * Arguments:   @mp *f@ = a polynomial
 106  *
 107  * Returns:     Nonzero if the polynomial is irreducible; otherwise zero.
 108  */
 109
 110 extern int gf_irreduciblep(mp */*f*/);
 111
 112 /* --- @gf_gcd@ --- *
 113  *
 114  * Arguments:   @mp **gcd, **xx, **yy@ = where to write the results
 115  *              @mp *a, *b@ = sources (must be nonzero)
 116  *
 117  *
 118  * Returns:     ---
 119  *
 120  * Use:         Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
 121  *              @ax + by = gcd(a, b)@.  This is useful for computing modular
 122  *              inverses.
 123  */
 124
 125 extern void gf_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
 126                    mp */*a*/, mp */*b*/);
 127
 128 /* -- @gf_modinv@ --- *
 129  *
 130  * Arguments:   @mp *d@ = destination
 131  *              @mp *x@ = argument
 132  *              @mp *p@ = modulus
 133  *
 134  * Returns:     The inverse %$x^{-1} \bmod p$%.
 135  *
 136  * Use:         Computes a modular inverse, the catch being that the
 137  *              arguments and results are binary polynomials.  An assertion
 138  *              fails if %$p$% has no inverse.
 139  */
 140
 141 extern mp *gf_modinv(mp */*d*/, mp */*x*/, mp */*p*/);
 142
 143 /*----- That's all, folks -------------------------------------------------*/
 144
 145 #ifdef __cplusplus
 146   }
 147 #endif
 148
 149 #endif