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
//! Fermat-based modular inversion test oracle.
use super::U256;
impl U256 {
/// Computes the modular inverse of `self` modulo `modulus` using Fermat's
/// little theorem: `a^(p-2) mod p` for prime `p`.
///
/// Returns `Some(inverse)` when `self` is non-zero mod `modulus`, or `None`
/// when `self` is zero or a multiple of `modulus`. This is a test oracle —
/// trivially correct but slow (~7µs) — used exclusively to validate the
/// SafeGCD implementation. Not wired into any dispatcher.
///
/// Only correct when `modulus` is prime. For composite moduli the result
/// is meaningless.
#[allow(dead_code)]
pub(crate) fn mod_inv_fermat(&self, modulus: &U256) -> Option<U256> {
let reduced = self.modulo(modulus);
if reduced.is_zero() {
return None;
}
let (exp, _) = modulus.overflowing_sub(&U256::from_be_limbs([0, 0, 0, 2]));
Some(reduced.pow_mod(&exp, modulus))
}
}
#[cfg(test)]
mod ai_tests {
use super::*;
const P: U256 = U256::from_be_limbs([
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F,
]);
/// Inverse of 1 is 1.
#[test]
fn inverse_of_one() {
assert_eq!(U256::ONE.mod_inv_fermat(&P).unwrap(), U256::ONE);
}
/// Inverse of 2 mod P is (P + 1) / 2.
#[test]
fn inverse_of_two() {
let two = U256::from_be_limbs([0, 0, 0, 2]);
let inv = two.mod_inv_fermat(&P).unwrap();
assert_eq!(two.mul_mod(&inv, &P), U256::ONE);
}
/// Zero has no inverse.
#[test]
fn zero_has_no_inverse() {
assert!(U256::ZERO.mod_inv_fermat(&P).is_none());
}
/// Modulus multiple has no inverse.
#[test]
fn modulus_multiple_no_inverse() {
assert!(P.mod_inv_fermat(&P).is_none());
}
/// Matches Lehmer mod_inv for the generator x-coordinate.
#[test]
fn matches_lehmer() {
let gx = U256::from_be_limbs([
0x79BE667EF9DCBBAC, 0x55A06295CE870B07,
0x029BFCDB2DCE28D9, 0x59F2815B16F81798,
]);
let fermat = gx.mod_inv_fermat(&P).unwrap();
let lehmer = gx.mod_inv(&P).unwrap();
assert_eq!(fermat, lehmer);
}
/// Roundtrip: a * inv(a) = 1.
#[test]
fn roundtrip() {
let a = U256::from_be_limbs([0, 0, 0, 7]);
let inv = a.mod_inv_fermat(&P).unwrap();
assert_eq!(a.mul_mod(&inv, &P), U256::ONE);
}
/// Inverse of P-1 is P-1.
#[test]
fn inverse_of_p_minus_one() {
let p_minus_1 = P - U256::ONE;
let inv = p_minus_1.mod_inv_fermat(&P).unwrap();
assert_eq!(inv, p_minus_1);
}
}