#include <fp.hpp>

Public Types
typedef Fp_model< n, modulus >	my_Fp

Public Member Functions
	Fp_model ()

	Fp_model (const bigint< n > &b)

	Fp_model (const long x, const bool is_unsigned=false)

void	set_ulong (const unsigned long x)

void	mul_reduce (const bigint< n > &other)

void	clear ()

bigint< n >	as_bigint () const

unsigned long	as_ulong () const

bool	operator== (const Fp_model &other) const

bool	operator!= (const Fp_model &other) const

bool	is_zero () const

void	print () const

Fp_model &	operator+= (const Fp_model &other)

Fp_model &	operator-= (const Fp_model &other)

Fp_model &	operator*= (const Fp_model &other)

Fp_model &	operator^= (const unsigned long pow)

template<mp_size_t m>
Fp_model &	operator^= (const bigint< m > &pow)

Fp_model	operator+ (const Fp_model &other) const

Fp_model	operator- (const Fp_model &other) const

Fp_model	operator* (const Fp_model &other) const

Fp_model	operator- () const

Fp_model	squared () const

Fp_model &	invert ()

Fp_model	inverse () const

Fp_model	sqrt () const
	HAS TO BE A SQUARE (else does not terminate) More...

Fp_model	operator^ (const unsigned long pow) const

template<mp_size_t m>
Fp_model	operator^ (const bigint< m > &pow) const

Static Public Member Functions
static void	static_init ()

static bool	modulus_is_valid ()

static size_t	size_in_bits ()

static size_t	capacity ()

static const bigint< n > &	field_char ()

static constexpr size_t	extension_degree ()

static const Fp_model< n, modulus > &	zero ()

static const Fp_model< n, modulus > &	one ()

static Fp_model< n, modulus >	random_element ()
	returns random element of Fp_model More...

static Fp_model< n, modulus >	geometric_generator ()
	generator^k, for k = 1 to m, domain size m More...

static Fp_model< n, modulus >	arithmetic_generator ()
	generator++, for k = 1 to m, domain size m More...

Public Attributes
bigint< n >	mont_repr

Static Public Attributes
static const mp_size_t	num_limbs = n

static const constexpr bigint< n > &	mod = modulus

static const size_t	tower_extension_degree = 1
	The "base"/"ground" field. More...

static size_t	num_bits

static bigint< n >	euler
	(modulus-1)/2 More...

static size_t	s
	modulus = 2^s * t + 1 More...

static bigint< n >	t
	with t odd More...

static bigint< n >	t_minus_1_over_2
	(t-1)/2 More...

static Fp_model< n, modulus >	nqr
	a quadratic nonresidue More...

static Fp_model< n, modulus >	nqr_to_t
	nqr^t More...

static Fp_model< n, modulus >	multiplicative_generator
	generator of Fp^* More...

static Fp_model< n, modulus >	root_of_unity
	generator^((modulus-1)/2^s) More...

static mp_limb_t	inv
	-modulus^(-1) mod W, where W = 2^(word size) More...

static bigint< n >	Rsquared
	R^2, where R = W^k, where k = ?? More...

static bigint< n >	Rcubed
	R^3. More...

Static Protected Attributes
static bool	s_initialized

static Fp_model< n, modulus >	s_zero

static Fp_model< n, modulus >	s_one

Friends
std::ostream &	operator (std::ostream &out, const Fp_model< n, modulus > &p)

std::istream &	operator>> (std::istream &in, Fp_model< n, modulus > &p)

Detailed Description

template<mp_size_t n, const bigint< n > & modulus>
class libff::Fp_model< n, modulus >

Arithmetic in the finite field F[p], for prime p of fixed length.

This class implements Fp-arithmetic, for a large prime p, using a fixed number of words. It is optimized for tight memory consumption, so the modulus p is passed as a template parameter, to avoid per-element overheads.

The implementation is mostly a wrapper around GMP's MPN (constant-size integers). But for the integer sizes of interest for libff (3 to 5 limbs of 64 bits each), we implement performance-critical routines, like addition and multiplication, using hand-optimzied assembly code.

Definition at line 20 of file fp.hpp.

Member Typedef Documentation

◆ my_Fp

template<mp_size_t n, const bigint< n > & modulus>

typedef Fp_model<n, modulus> libff::Fp_model< n, modulus >::my_Fp

Definition at line 41 of file fp.hpp.

Constructor & Destructor Documentation

◆ Fp_model() [1/3]

template<mp_size_t n, const bigint< n > & modulus>

libff::Fp_model< n, modulus >::Fp_model ( )

inline

Definition at line 89 of file fp.hpp.

89 {};

◆ Fp_model() [2/3]

template<mp_size_t n, const bigint< n > & modulus>

libff::Fp_model< n, modulus >::Fp_model ( const bigint< n > & b )

◆ Fp_model() [3/3]

template<mp_size_t n, const bigint< n > & modulus>

libff::Fp_model< n, modulus >::Fp_model	(	const long	x,
		const bool	is_unsigned = `false`
	)

Member Function Documentation

◆ arithmetic_generator()

template<mp_size_t n, const bigint< n > & modulus>

static Fp_model<n, modulus> libff::Fp_model< n, modulus >::arithmetic_generator ( )

static

generator++, for k = 1 to m, domain size m

◆ as_bigint()

template<mp_size_t n, const bigint< n > & modulus>

bigint<n> libff::Fp_model< n, modulus >::as_bigint ( ) const

Return the standard (not Montgomery) representation of the Field element's requivalence class. I.e. Fp(2).as_bigint() would return bigint(2)

◆ as_ulong()

template<mp_size_t n, const bigint< n > & modulus>

unsigned long libff::Fp_model< n, modulus >::as_ulong ( ) const

Return the last limb of the standard representation of the field element. E.g. on 64-bit architectures Fp(123).as_ulong() and Fp(2^64+123).as_ulong() would both return 123.

◆ capacity()

template<mp_size_t n, const bigint< n > & modulus>

static size_t libff::Fp_model< n, modulus >::capacity ( )

inlinestatic

Definition at line 135 of file fp.hpp.

135 { return num_bits - 1; }

◆ clear()

template<mp_size_t n, const bigint< n > & modulus>

void libff::Fp_model< n, modulus >::clear ( )

Here is the caller graph for this function:

◆ extension_degree()

template<mp_size_t n, const bigint< n > & modulus>

static constexpr size_t libff::Fp_model< n, modulus >::extension_degree ( )

inlinestaticconstexpr

Definition at line 137 of file fp.hpp.

137 { return 1; }

◆ field_char()

template<mp_size_t n, const bigint< n > & modulus>

static const bigint<n>& libff::Fp_model< n, modulus >::field_char ( )

inlinestatic

Definition at line 136 of file fp.hpp.

136 { return modulus; }

Here is the caller graph for this function:

◆ geometric_generator()

template<mp_size_t n, const bigint< n > & modulus>

static Fp_model<n, modulus> libff::Fp_model< n, modulus >::geometric_generator ( )

static

generator^k, for k = 1 to m, domain size m

◆ inverse()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::inverse ( ) const

Here is the caller graph for this function:

◆ invert()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model& libff::Fp_model< n, modulus >::invert ( )

◆ is_zero()

template<mp_size_t n, const bigint< n > & modulus>

bool libff::Fp_model< n, modulus >::is_zero ( ) const

Here is the caller graph for this function:

◆ modulus_is_valid()

template<mp_size_t n, const bigint< n > & modulus>

static bool libff::Fp_model< n, modulus >::modulus_is_valid ( )

inlinestatic

Definition at line 84 of file fp.hpp.

     {
         return modulus.data[n - 1] != 0;
     } // mpn inverse assumes that highest limb is non-zero

Here is the caller graph for this function:

◆ mul_reduce()

template<mp_size_t n, const bigint< n > & modulus>

void libff::Fp_model< n, modulus >::mul_reduce ( const bigint< n > & other )

◆ one()

template<mp_size_t n, const bigint< n > & modulus>

static const Fp_model<n, modulus>& libff::Fp_model< n, modulus >::one ( )

static

◆ operator!=()

template<mp_size_t n, const bigint< n > & modulus>

bool libff::Fp_model< n, modulus >::operator!= ( const Fp_model< n, modulus > & other ) const

◆ operator*()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::operator* ( const Fp_model< n, modulus > & other ) const

◆ operator*=()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model& libff::Fp_model< n, modulus >::operator*= ( const Fp_model< n, modulus > & other )

◆ operator+()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::operator+ ( const Fp_model< n, modulus > & other ) const

◆ operator+=()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model& libff::Fp_model< n, modulus >::operator+= ( const Fp_model< n, modulus > & other )

◆ operator-() [1/2]

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::operator- ( ) const

◆ operator-() [2/2]

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::operator- ( const Fp_model< n, modulus > & other ) const

◆ operator-=()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model& libff::Fp_model< n, modulus >::operator-= ( const Fp_model< n, modulus > & other )

◆ operator==()

template<mp_size_t n, const bigint< n > & modulus>

bool libff::Fp_model< n, modulus >::operator== ( const Fp_model< n, modulus > & other ) const

◆ operator^() [1/2]

template<mp_size_t n, const bigint< n > & modulus>

template<mp_size_t m>

Fp_model libff::Fp_model< n, modulus >::operator^ ( const bigint< m > & pow ) const

◆ operator^() [2/2]

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::operator^ ( const unsigned long pow ) const

◆ operator^=() [1/2]

template<mp_size_t n, const bigint< n > & modulus>

template<mp_size_t m>

Fp_model& libff::Fp_model< n, modulus >::operator^= ( const bigint< m > & pow )

◆ operator^=() [2/2]

template<mp_size_t n, const bigint< n > & modulus>

Fp_model& libff::Fp_model< n, modulus >::operator^= ( const unsigned long pow )

◆ print()

template<mp_size_t n, const bigint< n > & modulus>

void libff::Fp_model< n, modulus >::print ( ) const

Here is the caller graph for this function:

◆ random_element()

template<mp_size_t n, const bigint< n > & modulus>

static Fp_model<n, modulus> libff::Fp_model< n, modulus >::random_element ( )

static

returns random element of Fp_model

Here is the caller graph for this function:

◆ set_ulong()

template<mp_size_t n, const bigint< n > & modulus>

void libff::Fp_model< n, modulus >::set_ulong ( const unsigned long x )

◆ size_in_bits()

template<mp_size_t n, const bigint< n > & modulus>

static size_t libff::Fp_model< n, modulus >::size_in_bits ( )

inlinestatic

Definition at line 134 of file fp.hpp.

134 { return num_bits; }

Here is the caller graph for this function:

◆ sqrt()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::sqrt ( ) const

HAS TO BE A SQUARE (else does not terminate)

Here is the caller graph for this function:

◆ squared()

template<mp_size_t n, const bigint< n > & modulus>

Fp_model libff::Fp_model< n, modulus >::squared ( ) const

◆ static_init()

template<mp_size_t n, const bigint< n > & modulus>

static void libff::Fp_model< n, modulus >::static_init ( )

static

Here is the caller graph for this function:

◆ zero()

template<mp_size_t n, const bigint< n > & modulus>

static const Fp_model<n, modulus>& libff::Fp_model< n, modulus >::zero ( )

static

Friends And Related Function Documentation

◆ operator

template<mp_size_t n, const bigint< n > & modulus>

std::ostream& operator	(	std::ostream &	out,
		const Fp_model< n, modulus > &	p
	)

friend

◆ operator>>

template<mp_size_t n, const bigint< n > & modulus>

std::istream& operator>>	(	std::istream &	in,
		Fp_model< n, modulus > &	p
	)

friend

Member Data Documentation

◆ euler

template<mp_size_t n, const bigint< n > & modulus>

bigint< n > libff::Fp_model< n, modulus >::euler

static

(modulus-1)/2

Definition at line 62 of file fp.hpp.

◆ inv

template<mp_size_t n, const bigint< n > & modulus>

mp_limb_t libff::Fp_model< n, modulus >::inv

static

-modulus^(-1) mod W, where W = 2^(word size)

Definition at line 78 of file fp.hpp.

◆ mod

template<mp_size_t n, const bigint< n > & modulus>

const constexpr bigint<n>& libff::Fp_model< n, modulus >::mod = modulus

staticconstexpr

Definition at line 48 of file fp.hpp.

◆ mont_repr

template<mp_size_t n, const bigint< n > & modulus>

bigint<n> libff::Fp_model< n, modulus >::mont_repr

Definition at line 43 of file fp.hpp.

◆ multiplicative_generator

template<mp_size_t n, const bigint< n > & modulus>

Fp_model< n, modulus > libff::Fp_model< n, modulus >::multiplicative_generator

static

generator of Fp^*

Definition at line 74 of file fp.hpp.

◆ nqr

template<mp_size_t n, const bigint< n > & modulus>

Fp_model< n, modulus > libff::Fp_model< n, modulus >::nqr

static

a quadratic nonresidue

Definition at line 70 of file fp.hpp.

◆ nqr_to_t

template<mp_size_t n, const bigint< n > & modulus>

Fp_model< n, modulus > libff::Fp_model< n, modulus >::nqr_to_t

static

nqr^t

Definition at line 72 of file fp.hpp.

◆ num_bits

template<mp_size_t n, const bigint< n > & modulus>

size_t libff::Fp_model< n, modulus >::num_bits

static

Definition at line 60 of file fp.hpp.

◆ num_limbs

template<mp_size_t n, const bigint< n > & modulus>

const mp_size_t libff::Fp_model< n, modulus >::num_limbs = n

static

Definition at line 47 of file fp.hpp.

◆ Rcubed

template<mp_size_t n, const bigint< n > & modulus>

bigint< n > libff::Fp_model< n, modulus >::Rcubed

static

R^3.

Definition at line 82 of file fp.hpp.

◆ root_of_unity

template<mp_size_t n, const bigint< n > & modulus>

Fp_model< n, modulus > libff::Fp_model< n, modulus >::root_of_unity

static

generator^((modulus-1)/2^s)

Definition at line 76 of file fp.hpp.

◆ Rsquared

template<mp_size_t n, const bigint< n > & modulus>

bigint< n > libff::Fp_model< n, modulus >::Rsquared

static

R^2, where R = W^k, where k = ??

Definition at line 80 of file fp.hpp.

◆ s

template<mp_size_t n, const bigint< n > & modulus>

size_t libff::Fp_model< n, modulus >::s

static

modulus = 2^s * t + 1

Definition at line 64 of file fp.hpp.

◆ s_initialized

template<mp_size_t n, const bigint< n > & modulus>

bool libff::Fp_model< n, modulus >::s_initialized

staticprotected

Definition at line 152 of file fp.hpp.

◆ s_one

template<mp_size_t n, const bigint< n > & modulus>

Fp_model<n, modulus> libff::Fp_model< n, modulus >::s_one

staticprotected

Definition at line 154 of file fp.hpp.

◆ s_zero

template<mp_size_t n, const bigint< n > & modulus>

Fp_model<n, modulus> libff::Fp_model< n, modulus >::s_zero

staticprotected

Definition at line 153 of file fp.hpp.

◆ t

template<mp_size_t n, const bigint< n > & modulus>

bigint< n > libff::Fp_model< n, modulus >::t

static

with t odd

Definition at line 66 of file fp.hpp.

◆ t_minus_1_over_2

template<mp_size_t n, const bigint< n > & modulus>

bigint< n > libff::Fp_model< n, modulus >::t_minus_1_over_2

static

(t-1)/2

Definition at line 68 of file fp.hpp.

◆ tower_extension_degree

template<mp_size_t n, const bigint< n > & modulus>

const size_t libff::Fp_model< n, modulus >::tower_extension_degree = 1

static

The "base"/"ground" field.

Definition at line 58 of file fp.hpp.

The documentation for this class was generated from the following file:

/home/runner/work/libff/libff/libff/algebra/fields/fp.hpp

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Static Protected Attributes

Friends

Detailed Description

template<mp_size_t n, const bigint< n > & modulus> class libff::Fp_model< n, modulus >

Member Typedef Documentation

◆ my_Fp

Constructor & Destructor Documentation

◆ Fp_model() [1/3]

◆ Fp_model() [2/3]

◆ Fp_model() [3/3]

Member Function Documentation

◆ arithmetic_generator()

◆ as_bigint()

◆ as_ulong()

◆ capacity()

◆ clear()

◆ extension_degree()

◆ field_char()

◆ geometric_generator()

◆ inverse()

◆ invert()

◆ is_zero()

◆ modulus_is_valid()

◆ mul_reduce()

◆ one()

◆ operator!=()

◆ operator*()

◆ operator*=()

◆ operator+()

◆ operator+=()

◆ operator-() [1/2]

◆ operator-() [2/2]

◆ operator-=()

◆ operator==()

◆ operator^() [1/2]

◆ operator^() [2/2]

◆ operator^=() [1/2]

◆ operator^=() [2/2]

◆ print()

◆ random_element()

◆ set_ulong()

◆ size_in_bits()

◆ sqrt()

◆ squared()

◆ static_init()

◆ zero()

Friends And Related Function Documentation

◆ operator

◆ operator>>

Member Data Documentation

◆ euler

◆ inv

◆ mod

◆ mont_repr

◆ multiplicative_generator

◆ nqr

◆ nqr_to_t

◆ num_bits

◆ num_limbs

◆ Rcubed

◆ root_of_unity

◆ Rsquared

◆ s

◆ s_initialized

◆ s_one

◆ s_zero

◆ t

◆ t_minus_1_over_2

◆ tower_extension_degree

template<mp_size_t n, const bigint< n > & modulus>
class libff::Fp_model< n, modulus >