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

   1 /* -*-c-*-
   2  *
   3  * Arithmetic in the Goldilocks field GF(2^448 - 2^224 - 1)
   4  *
   5  * (c) 2017 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_FGOLDI_H
  29 #define CATACOMB_FGOLDI_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Header files ------------------------------------------------------*/
  36
  37 #include <mLib/bits.h>
  38
  39 #ifndef CATACOMB_QFARITH_H
  40 #  include "qfarith.h"
  41 #endif
  42
  43 /*----- Data structures ---------------------------------------------------*/
  44
  45 typedef union {
  46   int32 p28[16];
  47   int16 p12[40];
  48 } fgoldi;
  49
  50 #if !defined(FGOLDI_IMPL) && defined(HAVE_INT64)
  51 #  define FGOLDI_IMPL 28
  52 #endif
  53
  54 #ifndef FGOLDI_IMPL
  55 #  define FGOLDI_IMPL 12
  56 #endif
  57
  58 #if FGOLDI_IMPL == 28
  59   typedef int32 fgoldi_piece;
  60 #endif
  61 #if FGOLDI_IMPL == 12
  62   typedef int16 fgoldi_piece;
  63 #endif
  64
  65 /*----- Functions provided ------------------------------------------------*/
  66
  67 /* --- @fgoldi_load@ --- *
  68  *
  69  * Arguments:   @fgoldi *z@ = where to store the result
  70  *              @const octet xv[56]@ = source to read
  71  *
  72  * Returns:     ---
  73  *
  74  * Use:         Reads an element of %$\gf{2^{448} - 2^{224} - 19}$% in
  75  *              external representation from @xv@ and stores it in @z@.
  76  *
  77  *              External representation is little-endian base-256.  Some
  78  *              elements have multiple encodings, which are not produced by
  79  *              correct software; use of noncanonical encodings is not an
  80  *              error, and toleration of them is considered a performance
  81  *              feature.
  82  */
  83
  84 extern void fgoldi_load(fgoldi */*z*/, const octet /*xv*/[56]);
  85
  86 /* --- @fgoldi_store@ --- *
  87  *
  88  * Arguments:   @octet zv[56]@ = where to write the result
  89  *              @const fgoldi *x@ = the field element to write
  90  *
  91  * Returns:     ---
  92  *
  93  * Use:         Stores a field element in the given octet vector in external
  94  *              representation.  A canonical encoding is always stored.
  95  */
  96
  97 extern void fgoldi_store(octet /*zv*/[56], const fgoldi */*x*/);
  98
  99 /* --- @fgoldi_set@ --- *
 100  *
 101  * Arguments:   @fgoldi *z@ = where to write the result
 102  *              @int a@ = a small-ish constant
 103  *
 104  * Returns:     ---
 105  *
 106  * Use:         Sets @z@ to equal @a@.
 107  */
 108
 109 extern void fgoldi_set(fgoldi */*x*/, int /*a*/);
 110
 111 /* --- @fgoldi_add@ --- *
 112  *
 113  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@ or @y@)
 114  *              @const fgoldi *x, *y@ = two operands
 115  *
 116  * Returns:     ---
 117  *
 118  * Use:         Set @z@ to the sum %$x + y$%.
 119  */
 120
 121 extern void fgoldi_add(fgoldi */*z*/,
 122                        const fgoldi */*x*/, const fgoldi */*y*/);
 123
 124 /* --- @fgoldi_sub@ --- *
 125  *
 126  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@ or @y@)
 127  *              @const fgoldi *x, *y@ = two operands
 128  *
 129  * Returns:     ---
 130  *
 131  * Use:         Set @z@ to the difference %$x - y$%.
 132  */
 133
 134 extern void fgoldi_sub(fgoldi */*z*/,
 135                        const fgoldi */*x*/, const fgoldi */*y*/);
 136
 137 /* --- @fgoldi_neg@ --- *
 138  *
 139  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@)
 140  *              @const fgoldi *x@ = an operand
 141  *
 142  * Returns:     ---
 143  *
 144  * Use:         Set @z = -x@.
 145  */
 146
 147 extern void fgoldi_neg(fgoldi */*z*/, const fgoldi */*x*/);
 148
 149 /* --- @fgoldi_pick2@ --- *
 150  *
 151  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@ or @y@)
 152  *              @const fgoldi *x, *y@ = two operands
 153  *              @uint32 m@ = a mask
 154  *
 155  * Returns:     ---
 156  *
 157  * Use:         If @m@ is zero, set @z = y@; if @m@ is all-bits-set, then set
 158  *              @z = x@.  If @m@ has some other value, then scramble @z@ in
 159  *              an unhelpful way.
 160  */
 161
 162 extern void fgoldi_pick2(fgoldi */*z*/,
 163                          const fgoldi */*x*/, const fgoldi */*y*/,
 164                          uint32 /*m*/);
 165
 166 /* --- @fgoldi_pickn@ --- *
 167  *
 168  * Arguments:   @fgoldi *z@ = where to put the result
 169  *              @const fgoldi *v@ = a table of entries
 170  *              @size_t n@ = the number of entries in @v@
 171  *              @size_t i@ = an index
 172  *
 173  * Returns:     ---
 174  *
 175  * Use:         If @0 <= i < n < 32@ then set @z = v[i]@.  If @n >= 32@ then
 176  *              do something unhelpful; otherwise, if @i >= n@ then set @z@
 177  *              to zero.
 178  */
 179
 180 extern void fgoldi_pickn(fgoldi */*z*/,
 181                          const fgoldi */*v*/, size_t /*n*/, size_t /*i*/);
 182
 183 /* --- @fgoldi_condswap@ --- *
 184  *
 185  * Arguments:   @fgoldi *x, *y@ = two operands
 186  *              @uint32 m@ = a mask
 187  *
 188  * Returns:     ---
 189  *
 190  * Use:         If @m@ is zero, do nothing; if @m@ is all-bits-set, then
 191  *              exchange @x@ and @y@.  If @m@ has some other value, then
 192  *              scramble @x@ and @y@ in an unhelpful way.
 193  */
 194
 195 extern void fgoldi_condswap(fgoldi */*x*/, fgoldi */*y*/, uint32 /*m*/);
 196
 197 /* --- @fgoldi_condneg@ --- *
 198  *
 199  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@)
 200  *              @const fgoldi *x@ = an operand
 201  *              @uint32 m@ = a mask
 202  *
 203  * Returns:     ---
 204  *
 205  * Use:         If @m@ is zero, set @z = x@; if @m@ is all-bits-set, then set
 206  *              @z = -x@.  If @m@ has some other value then scramble @z@ in
 207  *              an unhelpful way.
 208  */
 209
 210 extern void fgoldi_condneg(fgoldi */*z*/, const fgoldi */*x*/, uint32 /*m*/);
 211
 212 /* --- @fgoldi_mulconst@ --- *
 213  *
 214  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@)
 215  *              @const fgoldi *x@ = an operand
 216  *              @long a@ = a small-ish constant; %$|a| < 2^{20}$%.
 217  *
 218  * Returns:     ---
 219  *
 220  * Use:         Set @z@ to the product %$a x$%.
 221  */
 222
 223 extern void fgoldi_mulconst(fgoldi */*z*/, const fgoldi */*x*/, long /*a*/);
 224
 225 /* --- @fgoldi_mul@ --- *
 226  *
 227  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@ or @y@)
 228  *              @const fgoldi *x, *y@ = two operands
 229  *
 230  * Returns:     ---
 231  *
 232  * Use:         Set @z@ to the product %$x y$%.
 233  */
 234
 235 extern void fgoldi_mul(fgoldi */*z*/,
 236                        const fgoldi */*x*/, const fgoldi */*y*/);
 237
 238 /* --- @fgoldi_sqr@ --- *
 239  *
 240  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@ or @y@)
 241  *              @const fgoldi *x@ = an operand
 242  *
 243  * Returns:     ---
 244  *
 245  * Use:         Set @z@ to the square %$x^2$%.
 246  */
 247
 248 extern void fgoldi_sqr(fgoldi */*z*/, const fgoldi */*x*/);
 249
 250 /* --- @fgoldi_inv@ --- *
 251  *
 252  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@)
 253  *              @const fgoldi *x@ = an operand
 254  *
 255  * Returns:     ---
 256  *
 257  * Use:         Stores in @z@ the multiplicative inverse %$x^{-1}$%.  If
 258  *              %$x = 0$% then @z@ is set to zero.  This is considered a
 259  *              feature.
 260  */
 261
 262 extern void fgoldi_inv(fgoldi */*z*/, const fgoldi */*x*/);
 263
 264 /* --- @fgoldi_quosqrt@ --- *
 265  *
 266  * Arguments:   @fgoldi *z@ = where to put the result (may alias @x@ or @y@)
 267  *              @const fgoldi *x, *y@ = two operands
 268  *
 269  * Returns:     Zero if successful, @-1@ if %$x/y$% is not a square.
 270  *
 271  * Use:         Stores in @z@ the one of the square roots %$\pm\sqrt{x/y}$%.
 272  *              If %$x = y = 0% then the result is zero; if %$y = 0$% but %$x
 273  *              \ne 0$% then the operation fails.  If you wanted a specific
 274  *              square root then you'll have to pick it yourself.
 275  */
 276
 277 extern int fgoldi_quosqrt(fgoldi */*z*/,
 278                           const fgoldi */*x*/, const fgoldi */*y*/);
 279
 280 /*----- That's all, folks -------------------------------------------------*/
 281
 282 #ifdef __cplusplus
 283   }
 284 #endif
 285
 286 #endif