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
use crate::integer_square_root_with_binary_search_u64::isqrt;
/// for odd integer n
/// n = ab (\exist a, b are odd)
/// a = x + y
/// b = x - y
/// n = x^2 - y^2
/// x^2 = n + y^2
/// brute force y=0..n/2 to find x. (because x > y)
/// return x + y
pub fn fermat_factorization_method(n: u64) -> u64 {
assert!(n & 1 == 1);
let mut x2 = n;
for y in 0..=n / 2 {
let x = isqrt(x2);
if x * x == x2 {
debug_assert!((x + y) * (x - y) == n);
return x + y;
}
x2 += y << 1 | 1;
}
panic!("can't be here");
}
#[cfg(test)]
mod tests {
#[test]
fn test() {}
}