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
//! Single iteration of the Lehmer extended GCD algorithm.
use super::GcdState;
impl GcdState {
/// Performs one iteration of the Lehmer extended GCD algorithm,
/// returning the updated state.
///
/// Delegates to [`lehmer`](Self::lehmer) to decide the reduction
/// strategy (full-precision, scalar, or Lehmer matrix). When a
/// non-trivial Lehmer matrix is produced, applies it to both the
/// remainder pair `(r0, r1)` and the coefficient pair `(t0, t1)`,
/// and merges the Lehmer parity into the cumulative swap parity.
///
/// After applying a Lehmer matrix, the remainder pair may be
/// misordered (`r0 < r1`) on rare edge cases where the 63-bit
/// approximation slightly diverges from the full-precision values
/// at the last accumulated step. When this occurs, the remainders
/// and coefficients are swapped and the parity is toggled.
///
/// Takes `self` by value and returns the advanced state, so the
/// caller sees a pure reassignment with no mutable aliasing.
#[inline]
pub fn step(mut self) -> Self {
if let Some(lehmer) = self.lehmer() {
(self.r0, self.r1) = lehmer.apply(self.r0, self.r1);
(self.t0, self.t1) = lehmer.apply(self.t0, self.t1);
self.even = self.even == lehmer.even;
if self.r0 < self.r1 {
core::mem::swap(&mut self.r0, &mut self.r1);
core::mem::swap(&mut self.t0, &mut self.t1);
self.even = !self.even;
}
}
self
}
}
#[cfg(test)]
mod ai_tests {
use crate::u256::U256;
const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
use super::*;
/// Step advances the state toward completion.
#[test]
fn advances_state() {
let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
let next = state.step();
assert_ne!(next.r0, state.r0);
}
/// Repeated steps eventually reach r1 == 0.
#[test]
fn reaches_termination() {
let mut state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
while !state.r1.is_zero() {
state = state.step();
}
assert_eq!(state.r0, U256::ONE);
}
/// Full GCD via step loop produces correct inverse.
#[test]
fn correct_inverse_via_step() {
let value = U256::from_be_limbs([0, 0, 0, 42]);
let mut state = GcdState::new(P, value);
while !state.r1.is_zero() {
state = state.step();
}
let inv = state.inverse().unwrap();
assert_eq!(value.mul_mod(&inv, &P), U256::ONE);
}
/// Original state is not modified (value semantics).
#[test]
fn value_semantics() {
let state = GcdState::new(P, U256::from_be_limbs([0, 0, 0, 7]));
let original = state;
let _ = state.step();
assert_eq!(state, original);
}
}