Добавлена реализация алгоритма нахождения элемента g порядка q в конечном поле Z_p.

1 files changed, 26 insertions, 0 deletions

diff --git a/sem2/src/program.rs b/sem2/src/program.rs
new file mode 100644
index 0000000..3a8dd26
--- /dev/null
+++ b/sem2/src/program.rs
@@ -0,0 +1,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);
+        }
+    }
+}