src/snark/src/algebra/fields/fp.hpp

   1 /** @file
   2  *****************************************************************************
   3  Declaration of arithmetic in the finite field F[p], for prime p of fixed length.
   4  *****************************************************************************
   5  * @author     This file is part of libsnark, developed by SCIPR Lab
   6  *             and contributors (see AUTHORS).
   7  * @copyright  MIT license (see LICENSE file)
   8  *****************************************************************************/
   9
  10 #ifndef FP_HPP_
  11 #define FP_HPP_
  12
  13 #include "algebra/fields/bigint.hpp"
  14 #include "algebra/exponentiation/exponentiation.hpp"
  15
  16 namespace libsnark {
  17
  18 template<mp_size_t n, const bigint<n>& modulus>
  19 class Fp_model;
  20
  21 template<mp_size_t n, const bigint<n>& modulus>
  22 std::ostream& operator<<(std::ostream &, const Fp_model<n, modulus>&);
  23
  24 template<mp_size_t n, const bigint<n>& modulus>
  25 std::istream& operator>>(std::istream &, Fp_model<n, modulus> &);
  26
  27 /**
  28  * Arithmetic in the finite field F[p], for prime p of fixed length.
  29  *
  30  * This class implements Fp-arithmetic, for a large prime p, using a fixed number
  31  * of words. It is optimized for tight memory consumption, so the modulus p is
  32  * passed as a template parameter, to avoid per-element overheads.
  33  *
  34  * The implementation is mostly a wrapper around GMP's MPN (constant-size integers).
  35  * But for the integer sizes of interest for libsnark (3 to 5 limbs of 64 bits each),
  36  * we implement performance-critical routines, like addition and multiplication,
  37  * using hand-optimzied assembly code.
  38 */
  39 template<mp_size_t n, const bigint<n>& modulus>
  40 class Fp_model {
  41 public:
  42     bigint<n> mont_repr;
  43 public:
  44     static const mp_size_t num_limbs = n;
  45     static const constexpr bigint<n>& mod = modulus;
  46 #ifdef PROFILE_OP_COUNTS
  47     static long long add_cnt;
  48     static long long sub_cnt;
  49     static long long mul_cnt;
  50     static long long sqr_cnt;
  51     static long long inv_cnt;
  52 #endif
  53     static size_t num_bits;
  54     static bigint<n> euler; // (modulus-1)/2
  55     static size_t s; // modulus = 2^s * t + 1
  56     static bigint<n> t; // with t odd
  57     static bigint<n> t_minus_1_over_2; // (t-1)/2
  58     static Fp_model<n, modulus> nqr; // a quadratic nonresidue
  59     static Fp_model<n, modulus> nqr_to_t; // nqr^t
  60     static Fp_model<n, modulus> multiplicative_generator; // generator of Fp^*
  61     static Fp_model<n, modulus> root_of_unity; // generator^((modulus-1)/2^s)
  62     static mp_limb_t inv; // modulus^(-1) mod W, where W = 2^(word size)
  63     static bigint<n> Rsquared; // R^2, where R = W^k, where k = ??
  64     static bigint<n> Rcubed;   // R^3
  65
  66     static bool modulus_is_valid() { return modulus.data[n-1] != 0; } // mpn inverse assumes that highest limb is non-zero
  67
  68     Fp_model() {};
  69     Fp_model(const bigint<n> &b);
  70     Fp_model(const long x, const bool is_unsigned=false);
  71
  72     void set_ulong(const unsigned long x);
  73
  74     void mul_reduce(const bigint<n> &other);
  75
  76     void clear();
  77
  78     /* Return the standard (not Montgomery) representation of the
  79        Field element's requivalence class. I.e. Fp(2).as_bigint()
  80         would return bigint(2) */
  81     bigint<n> as_bigint() const;
  82     /* Return the last limb of the standard representation of the
  83        field element. E.g. on 64-bit architectures Fp(123).as_ulong()
  84        and Fp(2^64+123).as_ulong() would both return 123. */
  85     unsigned long as_ulong() const;
  86
  87     bool operator==(const Fp_model& other) const;
  88     bool operator!=(const Fp_model& other) const;
  89     bool is_zero() const;
  90
  91     void print() const;
  92
  93     Fp_model& operator+=(const Fp_model& other);
  94     Fp_model& operator-=(const Fp_model& other);
  95     Fp_model& operator*=(const Fp_model& other);
  96     Fp_model& operator^=(const unsigned long pow);
  97
  98     template<mp_size_t m>
  99     Fp_model& operator^=(const bigint<m> &pow);
 100
 101     Fp_model operator+(const Fp_model& other) const;
 102     Fp_model operator-(const Fp_model& other) const;
 103     Fp_model operator*(const Fp_model& other) const;
 104     Fp_model operator-() const;
 105     Fp_model squared() const;
 106     Fp_model& invert();
 107     Fp_model inverse() const;
 108     Fp_model sqrt() const; // HAS TO BE A SQUARE (else does not terminate)
 109
 110     Fp_model operator^(const unsigned long pow) const;
 111     template<mp_size_t m>
 112     Fp_model operator^(const bigint<m> &pow) const;
 113
 114     static size_t size_in_bits() { return num_bits; }
 115     static size_t capacity() { return num_bits - 1; }
 116     static bigint<n> field_char() { return modulus; }
 117
 118     static Fp_model<n, modulus> zero();
 119     static Fp_model<n, modulus> one();
 120     static Fp_model<n, modulus> random_element();
 121
 122     friend std::ostream& operator<< <n,modulus>(std::ostream &out, const Fp_model<n, modulus> &p);
 123     friend std::istream& operator>> <n,modulus>(std::istream &in, Fp_model<n, modulus> &p);
 124 };
 125
 126 #ifdef PROFILE_OP_COUNTS
 127 template<mp_size_t n, const bigint<n>& modulus>
 128 long long Fp_model<n, modulus>::add_cnt = 0;
 129
 130 template<mp_size_t n, const bigint<n>& modulus>
 131 long long Fp_model<n, modulus>::sub_cnt = 0;
 132
 133 template<mp_size_t n, const bigint<n>& modulus>
 134 long long Fp_model<n, modulus>::mul_cnt = 0;
 135
 136 template<mp_size_t n, const bigint<n>& modulus>
 137 long long Fp_model<n, modulus>::sqr_cnt = 0;
 138
 139 template<mp_size_t n, const bigint<n>& modulus>
 140 long long Fp_model<n, modulus>::inv_cnt = 0;
 141 #endif
 142
 143 template<mp_size_t n, const bigint<n>& modulus>
 144 size_t Fp_model<n, modulus>::num_bits;
 145
 146 template<mp_size_t n, const bigint<n>& modulus>
 147 bigint<n> Fp_model<n, modulus>::euler;
 148
 149 template<mp_size_t n, const bigint<n>& modulus>
 150 size_t Fp_model<n, modulus>::s;
 151
 152 template<mp_size_t n, const bigint<n>& modulus>
 153 bigint<n> Fp_model<n, modulus>::t;
 154
 155 template<mp_size_t n, const bigint<n>& modulus>
 156 bigint<n> Fp_model<n, modulus>::t_minus_1_over_2;
 157
 158 template<mp_size_t n, const bigint<n>& modulus>
 159 Fp_model<n, modulus> Fp_model<n, modulus>::nqr;
 160
 161 template<mp_size_t n, const bigint<n>& modulus>
 162 Fp_model<n, modulus> Fp_model<n, modulus>::nqr_to_t;
 163
 164 template<mp_size_t n, const bigint<n>& modulus>
 165 Fp_model<n, modulus> Fp_model<n, modulus>::multiplicative_generator;
 166
 167 template<mp_size_t n, const bigint<n>& modulus>
 168 Fp_model<n, modulus> Fp_model<n, modulus>::root_of_unity;
 169
 170 template<mp_size_t n, const bigint<n>& modulus>
 171 mp_limb_t Fp_model<n, modulus>::inv;
 172
 173 template<mp_size_t n, const bigint<n>& modulus>
 174 bigint<n> Fp_model<n, modulus>::Rsquared;
 175
 176 template<mp_size_t n, const bigint<n>& modulus>
 177 bigint<n> Fp_model<n, modulus>::Rcubed;
 178
 179 } // libsnark
 180 #include "algebra/fields/fp.tcc"
 181
 182 #endif // FP_HPP_