cnfy-uint 0.2.3

Zero-dependency 256-bit unsigned integer arithmetic for cryptographic applications
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

//! Extended GCD state for tracking remainder and Bézout coefficient pairs
//! during Lehmer-based modular inversion.

use crate::u256::U256;

mod extract_top_bits;
mod full_step;
mod inverse;
mod lehmer;
mod new;
mod run;
mod scalar_step;
mod step;
mod toggle_even;
mod top_bits_shift;
mod mul_u256;

/// Full-precision state of an extended GCD computation.
///
/// Tracks the remainder pair `(r0, r1)` where `r0 >= r1`, the Bézout
/// coefficient pair `(t0, t1)` using wrapping 256-bit arithmetic, and
/// the cumulative swap parity `even`.
///
/// Each Euclidean reduction step (full-precision, scalar, or Lehmer matrix)
/// advances both pairs simultaneously. At termination, when `r0 == 1`,
/// the modular inverse is recovered from `t0` with a parity-dependent
/// sign correction.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct GcdState {
    /// The original modulus, preserved for the final sign correction.
    pub modulus: U256,
    /// The larger remainder (initially the modulus).
    pub r0: U256,
    /// The smaller remainder (initially the value to invert).
    pub r1: U256,
    /// Bézout coefficient for `r0` (initially zero).
    pub t0: U256,
    /// Bézout coefficient for `r1` (initially one).
    pub t1: U256,
    /// Cumulative parity of swap operations.
    pub even: bool,
}

#[cfg(test)]
mod ai_tests {
    use super::*;

    /// Construction with all fields.
    #[test]
    fn construct_and_access() {
        let state = GcdState {
            modulus: U256::from_be_limbs([0, 0, 0, 100]),
            r0: U256::from_be_limbs([0, 0, 0, 100]),
            r1: U256::from_be_limbs([0, 0, 0, 37]),
            t0: U256::ZERO,
            t1: U256::ONE,
            even: true,
        };
        assert_eq!(state.modulus, U256::from_be_limbs([0, 0, 0, 100]));
        assert_eq!(state.r0, U256::from_be_limbs([0, 0, 0, 100]));
        assert_eq!(state.r1, U256::from_be_limbs([0, 0, 0, 37]));
        assert_eq!(state.t0, U256::ZERO);
        assert_eq!(state.t1, U256::ONE);
        assert!(state.even);
    }

    /// Copy semantics work correctly.
    #[test]
    fn copy_semantics() {
        let state = GcdState {
            modulus: U256::MAX,
            r0: U256::MAX,
            r1: U256::ONE,
            t0: U256::ZERO,
            t1: U256::ONE,
            even: false,
        };
        let copy = state;
        assert_eq!(state, copy);
    }
}