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
//! Runs the Lehmer extended GCD algorithm to completion.
use super::GcdState;
impl GcdState {
/// Runs the Lehmer extended GCD algorithm until `r1` reaches zero,
/// returning the terminal state.
///
/// Repeatedly calls [`step`](Self::step) to advance the remainder
/// and coefficient pairs. At termination, `r0` holds the GCD and
/// `t0` holds the Bézout coefficient (up to sign). The caller
/// typically follows with [`inverse`](Self::inverse) to extract the
/// modular inverse.
///
/// # Examples
///
/// ```
/// use cnfy_uint::gcd_state::GcdState;
/// use cnfy_uint::u256::U256;
/// let P = U256::from_be_limbs([
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
/// 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
/// ]);
///
/// let inv = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]))
/// .run()
/// .inverse()
/// .unwrap();
/// assert_eq!(U256::from_be_limbs([0, 0, 0, 7]).mul_mod(&inv, &P), U256::ONE);
/// ```
#[inline]
pub fn run(mut self) -> Self {
while !self.r1.is_zero() {
self = self.step();
}
self
}
}
#[cfg(test)]
mod ai_tests {
use crate::u256::U256;
const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
use super::*;
/// Run terminates with r1 == 0.
#[test]
fn terminates() {
let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7])).run();
assert!(state.r1.is_zero());
}
/// Run finds GCD == 1 for coprime inputs.
#[test]
fn gcd_is_one() {
let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 42])).run();
assert_eq!(state.r0, U256::ONE);
}
/// Run followed by inverse produces correct result.
#[test]
fn run_then_inverse() {
let value = U256::from_be_limbs([0, 0, 0, 13]);
let inv = GcdState::new(P, value).run().inverse().unwrap();
assert_eq!(value.mul_mod(&inv, &P), U256::ONE);
}
/// Non-coprime inputs yield GCD != 1.
#[test]
fn non_coprime() {
let state = GcdState::new(
U256::from_be_limbs([0, 0, 0, 12]),
U256::from_be_limbs([0, 0, 0, 8]),
)
.run();
assert_eq!(state.r0, U256::from_be_limbs([0, 0, 0, 4]));
}
}