arcium-primitives 0.7.0

Arcium primitives
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//! Fixed-exponent helpers shared by the fields whose `invert`/`sqrt` closed forms are built from
//! repeated squaring (Mersenne primes, GF(2^k)).

use ff::Field;

/// Returns `x^(2^n)`, i.e. `n` repeated squarings (in char 2, the Frobenius map iterated `n`
/// times).
#[inline]
pub(crate) fn pow2_pow<F: Field>(x: F, n: u32) -> F {
    (0..n).fold(x, |acc, _| acc.square())
}

/// Returns `x^(2^k - 1)` via an Itoh–Tsujii-style addition chain: ≈`k` squarings and `O(log k)`
/// multiplications, versus the ~`2k` operations of plain square-and-multiply on the all-ones
/// exponent.
pub(crate) fn pow2_minus_1<F: Field>(x: F, k: u32) -> F {
    debug_assert!(k >= 1);
    // Invariant: `acc == x^(2^cur - 1)`; grow `cur` from 1 to `k` following the bits of `k`.
    let mut acc = x;
    let mut cur = 1u32;
    for i in (0..(u32::BITS - 1 - k.leading_zeros())).rev() {
        // x^(2^{2·cur} - 1) = (x^(2^cur - 1))^(2^cur) · x^(2^cur - 1)
        acc = pow2_pow(acc, cur) * acc;
        cur *= 2;
        if (k >> i) & 1 == 1 {
            // x^(2^{cur+1} - 1) = (x^(2^cur - 1))^2 · x
            acc = acc.square() * x;
            cur += 1;
        }
    }
    debug_assert_eq!(cur, k);
    acc
}