simple_ring/
modular.rs

1
2#[inline(always)]
3pub fn mod_pow(mut base: u128, mut exp: u128, modulus: u128) -> u128 { //Function that computes b^e mod m, without overflowing.
4    let mut result = 1u128;
5    base %= modulus;
6    while exp > 0 {
7        if exp & 1 == 1 {
8            result = (result * base) % modulus;
9        }
10        base = (base * base) % modulus;
11        exp >>= 1;
12    }
13    result
14}
15
16
17pub fn find_valid_omega(n: usize, q: u64) -> u64 { 
18    let two_n = 2 * n;
19    let exp = (q - 1) / two_n as u64;
20    
21    for candidate in 2..q {
22        let omega = mod_pow(candidate as u128, exp as u128, q as u128) as u64;
23        
24        let omega_n = mod_pow(omega as u128, n as u128 , q as u128);
25        if omega_n == (q as u128 - 1)  {
26            return omega;
27        }
28    }
29    panic!("No valid omega found");
30}
31
32pub fn is_q_valid(n: usize, q: u64) -> bool {
33    if n == 0 || q < 2 {
34        return false;
35    }
36    
37    if !is_prime(q) {
38        return false;
39    }
40    
41    let two_n = 2 * n as u64;
42    (q - 1) % two_n == 0
43}
44
45pub fn is_prime(n: u64) -> bool { //Function that return if an uint is prime or not.
46    if n < 2 { return false; }
47    if n == 2 { return true; }
48    if n.is_multiple_of(2) { return false; }
49    let mut i = 3u64;
50    while i * i <= n {
51        if n.is_multiple_of(i) { return false; }
52        i += 2;
53    }
54    true
55}
simple_ring/modular.rs

simple_ring/
modular.rs
