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.

PVAC-HFHE performs all arithmetic operations in a 127-bit prime field F_p where p = 2^127 - 1 (a Mersenne prime).

​
The prime field F_p

​
Field definition

The field is defined by the prime: 
p = 2^127 - 1 = 170141183460469231731687303715884105727
This is the largest Mersenne prime that fits in 127 bits.
Using a Mersenne prime enables efficient modular reduction using bit shifts and additions instead of expensive division.

​
Field elements

Field elements are represented as 128-bit integers with the top bit always zero: 
struct Fp {
    uint64_t lo;  // Lower 64 bits
    uint64_t hi;  // Upper 63 bits (bit 63 always 0)
};
From include/pvac/core/field.hpp:17-20: 
struct Fp {
    uint64_t lo;
    uint64_t hi;
};
The hi field uses only 63 bits. Values are stored in the range [0, p-1].

​
Field operations

​
Addition

Addition with modular reduction: 
Fp fp_add(const Fp& a, const Fp& b) {
    u128 t0 = (u128)a.lo + (u128)b.lo;
    uint64_t lo = (uint64_t)t0;
    u128 t1 = (u128)a.hi + (u128)b.hi + (uint64_t)(t0 >> 64);
    
    return fp_from_words(lo, (uint64_t)t1);
}
From include/pvac/core/field.hpp:50-56. Steps:
  1. Add low words with carry
  2. Add high words with propagated carry
  3. Reduce modulo p using fp_from_words

​
Subtraction

Subtraction via negation: 
Fp fp_sub(const Fp& a, const Fp& b) {
    return fp_add(a, fp_neg(b));
}
Negation computes p - a: 
Fp fp_neg(const Fp& a) {
    u128 Plo = (u128)UINT64_MAX;
    u128 Phi = (u128)MASK63;  // 2^63 - 1
    
    u128 t0 = Plo - a.lo;
    uint64_t lo = (uint64_t)t0;
    u128 t1 = Phi - a.hi - (uint64_t)(t0 >> 64);
    
    return fp_from_words(lo, (uint64_t)t1);
}
From include/pvac/core/field.hpp:58-67.

​
Multiplication

Multiplication uses 128×128 → 256-bit widening multiplication: 
Fp fp_mul(const Fp& a, const Fp& b) {
    uint64_t z0, z1, z2, z3;
    mul128x128(a.lo, a.hi, b.lo, b.hi, z0, z1, z2, z3);
    return fp_reduce256(z0, z1, z2, z3);
}
From include/pvac/core/field.hpp:209-213. Implementation:
  • Uses platform-specific optimizations (x86 assembly, MSVC intrinsics, or portable 128-bit)
  • Computes full 256-bit product
  • Reduces modulo 2^127 - 1 efficiently
The x86 assembly version uses native mulq instructions for maximum performance.

​
Reduction modulo p

The reduction algorithm exploits the Mersenne prime structure: 
Fp fp_reduce256(uint64_t z0, uint64_t z1, uint64_t z2, uint64_t z3) {
    // Split into low 127 bits and high bits
    uint64_t L0 = z0;
    uint64_t L1 = z1 & MASK63;
    
    uint64_t H0 = (z1 >> 63) | (z2 << 1);
    uint64_t H1 = (z2 >> 63) | (z3 << 1);
    uint64_t H2 = (z3 >> 63);
    
    // Add high part to low part (since 2^127 ≡ 1 mod p)
    u128 t0 = (u128)L0 + (u128)H0;
    uint64_t x0 = (uint64_t)t0;
    uint64_t c0 = (uint64_t)(t0 >> 64);
    
    u128 t1 = (u128)L1 + (u128)H1 + (u128)c0;
    uint64_t x1 = (uint64_t)t1;
    uint64_t c1 = (uint64_t)(t1 >> 64);
    
    uint64_t x2 = H2 + c1;
    
    // Final reduction step
    uint64_t YL0 = x0;
    uint64_t YL1 = x1 & MASK63;
    uint64_t YH0 = (x1 >> 63) | (x2 << 1);
    
    u128 s0 = (u128)YL0 + (u128)YH0;
    uint64_t y0 = (uint64_t)s0;
    uint64_t cy = (uint64_t)(s0 >> 64);
    uint64_t y1 = YL1 + cy;
    
    return fp_from_words(y0, y1);
}
From include/pvac/core/field.hpp:179-207. Key insight: Since 2^127 ≡ 1 (mod p), we can reduce by adding the high bits to the low bits.

​
Inversion

Inversion uses Fermat’s Little Theorem: a^(p-1) ≡ 1 (mod p), so a^(-1) = a^(p-2). 
Fp fp_inv(const Fp& a) {
    return fp_inv_ct(a);
}
The constant-time implementation uses a windowed exponentiation algorithm: 
Fp fp_inv_ct(const Fp& a) {
    constexpr int W = 5;
    constexpr int T = 1 << W;  // 32 entries
    
    // Precompute table: a^1, a^2, ..., a^31
    Fp tbl[T];
    tbl[0] = fp_from_u64(1);
    tbl[1] = a;
    
    for (int i = 2; i < T; i++) {
        tbl[i] = fp_mul(tbl[i - 1], a);
    }
    
    // Exponentiate by p-2 = 2^127 - 3
    u128 e = (((u128)1) << 127) - 3;
    Fp r = fp_from_u64(1);
    // ... windowed exponentiation ...
    
    return r;
}
From include/pvac/core/field.hpp:229-269.
Inversion is constant-time to prevent timing side-channels, but it’s expensive (~100× slower than multiplication).

​
Why this field?

​
Advantages of F_(2^127 - 1)

  1. Mersenne prime: Fast reduction using bit operations
  2. Large enough: 127 bits provides ample space for computations
  3. Multiplicative group: p-1 = 2^127 - 2 is divisible by many small factors
  4. No NTT constraints: Unlike RLWE schemes, no need for NTT-friendly primes

​
Multiplicative group structure

The multiplicative group has order p - 1 = 2^127 - 2. Key generation requires finding a generator g of a subgroup of order B = 337: From include/pvac/core/types.hpp:40: 
int B = 337;  // Multiplicative group carrier
The parameter B is chosen so that B | (p-1), enabling efficient subgroup operations. The value 337 is a prime that divides 2^127 - 2.
The public key stores precomputed powers: 
std::vector<Fp> powg_B;  // [g^0, g^1, g^2, ..., g^336]
This enables fast lookups during encryption and homomorphic operations.

​
Vector operations

For batching (multi-slot encryption), operations extend element-wise: 
static std::vector<Fp> add(const std::vector<Fp>& a, const std::vector<Fp>& b) {
    std::vector<Fp> r(a.size());
    for (size_t i = 0; i < a.size(); ++i) 
        r[i] = fp_add(a[i], b[i]);
    return r;
}
From include/pvac/ops/encrypt.hpp:150-154.

​
Performance

Field operation timings on modern x86-64 CPUs:
OperationCycles (approx)Notes
Addition~10With reduction
Subtraction~15Via negation
Multiplication~30Using native mulq
Inversion~3000Constant-time exponentiation
For best performance, compile with -march=native to enable platform-specific optimizations.

​
Code example

#include <pvac/core/field.hpp>

using namespace pvac;

int main() {
    // Create field elements
    Fp a = fp_from_u64(42);
    Fp b = fp_from_u64(17);
    
    // Arithmetic operations
    Fp sum = fp_add(a, b);         // 42 + 17 = 59
    Fp diff = fp_sub(a, b);        // 42 - 17 = 25
    Fp prod = fp_mul(a, b);        // 42 * 17 = 714
    Fp inv = fp_inv(a);            // 42^(-1) mod p
    Fp ratio = fp_mul(a, fp_inv(b)); // 42 / 17 mod p
    
    return 0;
}

​
Next steps

Encryption scheme

Learn how field elements are encrypted

Homomorphic operations

Understand operations on encrypted data

Build docs developers (and LLMs) love

Get started for freeTalk to us