pht_crypto/
util.rs

1use rug::{Assign, Complete, Integer};
2
3/// Chinese remainder theorem case where k = 2 using Bezout's identity. Unlike
4/// other mpz functions rop must not be an aliased with any of the other
5/// arguments! This is done to save excessive copying in this function, plus
6/// it is usually not beneficial as conX_a and conX_m cannot be the same value
7/// anyway
8/// Source: https://github.com/tiehuis/libhcs/blob/0e1deeaca38617b7908b462747dbb80ae9f29d44/src/com/util.c#L294-L298
9pub(crate) fn crt2(
10    con1_a: &Integer,
11    con1_m: &Integer,
12    con2_a: &Integer,
13    con2_m: &Integer,
14) -> Integer {
15    let mut t = con1_m.gcd_ref(&con2_m).complete();
16    assert_eq!(t, 1);
17    let mut res = con2_m.clone().invert(&con1_m).unwrap();
18    res *= (con2_m * con1_a).complete();
19    t.assign(con1_m.clone().invert(&con2_m).unwrap() * con1_m * con2_a);
20    res += t;
21    t = (con1_m * con2_m).complete();
22    res %= t;
23    res
24}