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
82
83
84
85
86
87
88
89
//! Constructor for [`GcdState`].
use crate::u256::U256;
use super::GcdState;
impl GcdState {
/// Creates a new GCD state for computing the modular inverse of `value`
/// with respect to `modulus`.
///
/// Initialises the remainder pair to `(modulus, value)` and the Bézout
/// coefficients to `(0, 1)`, with even parity. This is the starting
/// configuration for the Lehmer extended GCD algorithm.
///
/// # Examples
///
/// ```
/// use cnfy_uint::gcd_state::GcdState;
/// use cnfy_uint::u256::U256;
///
/// let state = GcdState::new(
/// U256::from_be_limbs([0, 0, 0, 97]),
/// U256::from_be_limbs([0, 0, 0, 42]),
/// );
/// assert_eq!(state.r0, U256::from_be_limbs([0, 0, 0, 97]));
/// assert_eq!(state.r1, U256::from_be_limbs([0, 0, 0, 42]));
/// assert_eq!(state.t0, U256::ZERO);
/// assert_eq!(state.t1, U256::ONE);
/// assert!(state.even);
/// ```
#[inline]
pub const fn new(modulus: U256, value: U256) -> Self {
Self {
modulus,
r0: modulus,
r1: value,
t0: U256::ZERO,
t1: U256::ONE,
even: true,
}
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
/// Default coefficients and parity are set correctly.
#[test]
fn new_defaults() {
let state = GcdState::new(
U256::from_be_limbs([0, 0, 0, 97]),
U256::from_be_limbs([0, 0, 0, 42]),
);
assert_eq!(state.r0, U256::from_be_limbs([0, 0, 0, 97]));
assert_eq!(state.r1, U256::from_be_limbs([0, 0, 0, 42]));
assert_eq!(state.t0, U256::ZERO);
assert_eq!(state.t1, U256::ONE);
assert!(state.even);
}
/// Constructor is const-evaluable.
#[test]
fn const_eval() {
const STATE: GcdState = GcdState::new(U256::MAX, U256::ONE);
assert_eq!(STATE.r0, U256::MAX);
assert_eq!(STATE.r1, U256::ONE);
assert_eq!(STATE.t0, U256::ZERO);
assert_eq!(STATE.t1, U256::ONE);
assert!(STATE.even);
}
/// Large modulus and value are stored correctly.
#[test]
fn large_values() {
let modulus = U256::from_be_limbs([
0xFFFFFFFF_FFFFFFFF,
0xFFFFFFFF_FFFFFFFF,
0xFFFFFFFF_FFFFFFFF,
0xFFFFFFFF_FFFFFFED,
]);
let value = U256::from_be_limbs([0, 0, 0, 1]);
let state = GcdState::new(modulus, value);
assert_eq!(state.r0, modulus);
assert_eq!(state.r1, value);
}
}