Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/octra-labs/pvac_hfhe_cpp/llms.txt

Use this file to discover all available pages before exploring further.

​
Overview

This module implements arithmetic operations in the finite field modulo the Mersenne prime p = 2^127 - 1. All operations are implemented using 128-bit arithmetic with two 64-bit words, where the high word uses only 63 bits.

​
Type definition

​
u128

Unsigned 128-bit integer type. 
using u128 = unsigned __int128;
Requires compiler support for 128-bit integers. Will fail to compile if not available.

​
MASK63

Mask for the upper 63 bits. 
static constexpr uint64_t MASK63 = 0x7FFFFFFFFFFFFFFFULL;

​
Construction

​
fp_from_u64

Creates a field element from a 64-bit unsigned integer. 
Fp fp_from_u64(uint64_t x);
​
x
uint64_t
Input value (automatically reduced modulo p)
​
return
Fp
Field element with value x mod p
Example: 
Fp zero = fp_from_u64(0);
Fp one = fp_from_u64(1);
Fp x = fp_from_u64(42);

​
fp_from_words

Creates a field element from two 64-bit words with automatic modular reduction. 
Fp fp_from_words(uint64_t lo, uint64_t hi);
​
lo
uint64_t
Low 64 bits
​
hi
uint64_t
High 64 bits (will be reduced to 63 bits)
​
return
Fp
Field element representing (hi * 2^64 + lo) mod p
Example: 
Fp x = fp_from_words(0xFFFFFFFFFFFFFFFFULL, 0x7FFFFFFFFFFFFFFFULL);

​
Basic arithmetic

​
fp_add

Addition in the field. 
Fp fp_add(const Fp& a, const Fp& b);
​
a
const Fp&
First operand
​
b
const Fp&
Second operand
​
return
Fp
Result of (a + b) mod p
Example: 
Fp a = fp_from_u64(10);
Fp b = fp_from_u64(20);
Fp sum = fp_add(a, b); // sum = 30

​
fp_neg

Negation in the field. 
Fp fp_neg(const Fp& a);
​
a
const Fp&
Input element
​
return
Fp
Result of (-a) mod p = (p - a) mod p
Example: 
Fp a = fp_from_u64(5);
Fp neg_a = fp_neg(a); // neg_a = p - 5

​
fp_sub

Subtraction in the field. 
Fp fp_sub(const Fp& a, const Fp& b);
​
a
const Fp&
Minuend
​
b
const Fp&
Subtrahend
​
return
Fp
Result of (a - b) mod p
Example: 
Fp a = fp_from_u64(30);
Fp b = fp_from_u64(20);
Fp diff = fp_sub(a, b); // diff = 10

​
fp_mul

Multiplication in the field. 
Fp fp_mul(const Fp& a, const Fp& b);
​
a
const Fp&
First factor
​
b
const Fp&
Second factor
​
return
Fp
Result of (a * b) mod p
Example: 
Fp a = fp_from_u64(6);
Fp b = fp_from_u64(7);
Fp product = fp_mul(a, b); // product = 42
Multiplication uses optimized platform-specific implementations (MSVC intrinsics, GCC inline assembly, or portable 128-bit arithmetic).

​
Advanced operations

​
fp_inv

Multiplicative inverse in the field. 
Fp fp_inv(const Fp& a);
​
a
const Fp&
Non-zero field element
​
return
Fp
Result b such that (a * b) mod p = 1
Example: 
Fp a = fp_from_u64(5);
Fp a_inv = fp_inv(a);
Fp one = fp_mul(a, a_inv); // one = 1
Attempting to invert zero will produce incorrect results. The caller must ensure the input is non-zero.

​
fp_inv_ct

Constant-time multiplicative inverse using windowed exponentiation. 
Fp fp_inv_ct(const Fp& a);
​
a
const Fp&
Non-zero field element
​
return
Fp
Multiplicative inverse of a
This function computes a^(p-2) mod p using Fermat’s little theorem. It uses windowed exponentiation with window size 5 for efficiency while maintaining constant-time operation.

​
fp_pow_u64

Exponentiation with a 64-bit exponent. 
Fp fp_pow_u64(Fp a, uint64_t e);
​
a
Fp
Base element
​
e
uint64_t
Exponent
​
return
Fp
Result of a^e mod p
Example: 
Fp a = fp_from_u64(2);
Fp result = fp_pow_u64(a, 10); // result = 2^10 = 1024
Uses binary exponentiation (square-and-multiply) for efficiency.

​
Low-level operations

​
mul128x128

Multiplies two 128-bit integers to produce a 256-bit result. 
void mul128x128(uint64_t a0, uint64_t a1, uint64_t b0, uint64_t b1,
                uint64_t& z0, uint64_t& z1, uint64_t& z2, uint64_t& z3);
​
a0
uint64_t
Low word of first operand
​
a1
uint64_t
High word of first operand
​
b0
uint64_t
Low word of second operand
​
b1
uint64_t
High word of second operand
​
z0
uint64_t&
Output: bits [0:63] of result
​
z1
uint64_t&
Output: bits [64:127] of result
​
z2
uint64_t&
Output: bits [128:191] of result
​
z3
uint64_t&
Output: bits [192:255] of result
This function has three implementations:
  • MSVC: Uses _umul128 intrinsic
  • GCC on x86-64: Uses inline assembly with mulq
  • Portable: Uses 128-bit integer arithmetic

​
fp_reduce256

Reduces a 256-bit integer modulo p. 
Fp fp_reduce256(uint64_t z0, uint64_t z1, uint64_t z2, uint64_t z3);
​
z0
uint64_t
Bits [0:63]
​
z1
uint64_t
Bits [64:127]
​
z2
uint64_t
Bits [128:191]
​
z3
uint64_t
Bits [192:255]
​
return
Fp
Result reduced modulo p = 2^127 - 1
Uses the fact that 2^127 ≡ 1 (mod p) to perform efficient reduction via addition rather than division.

​
Implementation details

​
Field modulus

The field modulus is the Mersenne prime: 
p = 2^127 - 1 = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
This prime allows for efficient modular reduction using bitwise operations.

​
Representation

Field elements are represented in the range [0, p) using two 64-bit words:
  • lo: bits [0:63]
  • hi: bits [64:126] (bit 127 is always 0)

​
Modular reduction

Reduction modulo 2^127 - 1 is optimized using the identity: 
x mod (2^127 - 1) = (x & (2^127 - 1)) + (x >> 127)
Multiple rounds may be needed to fully reduce the result.

​
Platform support

This module requires 128-bit integer support (unsigned __int128). Compilation will fail on platforms without this feature.
Supported compilers:
  • GCC 4.6+
  • Clang 3.0+
  • MSVC with Clang frontend
  • ICC (Intel C++ Compiler)

Build docs developers (and LLMs) love

Get started for freeTalk to us