finitefield.md

Arithmetic in the ring Z/qZ

The library supports arithmetic in the ring Z/qZ, i.e., the integers modulo some integer q, where q is fixed at compile time.

First, we declare the type of the ring by calling the Zq template function, which creates a dummy instance of the ZqElement class, of which we take the type using C++'s decltype keyword:

using GF101 = decltype(Zq(1267650600228229401496703205653_Z));
// define the type of a 101-bit prime field

Now, we can create instances of our newly created type, and perform arithmetic using the overloaded operators in the ring:

GF101 x(8732191096651392800298638976_Z);
GF101 y(27349736_Z);

auto sum = x + y;
auto prod = x * y;

The ZqElement class is mainly defined to be able to write functions like operator+ and operator* that bind exclusively to ZqElements. ZqElement has a big_int as its only data member. Below, we show its interface:

class skip_reduction {}; // used in a constructor of ZqElement

template <typename T, T... Modulus> struct ZqElement {
  big_int<sizeof...(Modulus), T> data;

  explicit operator auto() const { return data; } // allow casting to big_int

  //==============
  // constructors
  //==============
  
  constexpr ZqElement();
  // default

  template <std::size_t N>
  constexpr ZqElement(big_int<N, T> init);
  // will reduce init if necessary

  constexpr ZqElement(big_int<sizeof...(Modulus), T> init, skip_reduction);
  // skips modulo reduction, should only be used if it is guaranteed that:
  //   init < modulus

  template <T... Limbs>
  constexpr ZqElement(std::integer_sequence<T, Limbs...>);
  // initialize with a compile-time (constant-expression) big-integer
  
};