sem2/src/program.rs


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

use crate::algo;
use crate::mpn::Number;

pub fn find_of_order(p: &Number, q: &Number) -> Result<Number, String> {
    if !algo::rabin_miller_test(&p, 10) {
        return Err("Число p должно быть простым".to_string());
    }
    if !algo::rabin_miller_test(&q, 10) {
        return Err("Число q должно быть простым".to_string());
    }
    let (pow, rem) = (p.clone() - 1.into()).div_rem(q.clone()).unwrap();
    if rem != 0.into() {
        return Err(
            "Числа p и q должны соотноситься как p = qs + 1".to_string()
        );
    }

    loop {
        let bound = p.clone() - 3.into();
        let a = bound.random_below() + 2.into();
        let g = a.pow_mod(&pow, p).unwrap();
        if g != 1.into() {
            return Ok(g);
        }
    }
}