From 00856e19b215222176cf0cb9c83fd880846c2c0f Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Fri, 21 Apr 2023 09:42:07 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=20=D1=80=D0=B5=D0=B0=D0=BB=D0=B8=D0=B7=D0=B0=D1=86=D0=B8=D1=8F?=
 =?UTF-8?q?=20=D0=B0=D0=BB=D0=B3=D0=BE=D1=80=D0=B8=D1=82=D0=BC=D0=B0=20?=
 =?UTF-8?q?=D0=BD=D0=B0=D1=85=D0=BE=D0=B6=D0=B4=D0=B5=D0=BD=D0=B8=D1=8F=20?=
 =?UTF-8?q?=D1=8D=D0=BB=D0=B5=D0=BC=D0=B5=D0=BD=D1=82=D0=B0=20g=20=D0=BF?=
 =?UTF-8?q?=D0=BE=D1=80=D1=8F=D0=B4=D0=BA=D0=B0=20q=20=D0=B2=20=D0=BA?=
 =?UTF-8?q?=D0=BE=D0=BD=D0=B5=D1=87=D0=BD=D0=BE=D0=BC=20=D0=BF=D0=BE=D0=BB?=
 =?UTF-8?q?=D0=B5=20Z=5Fp.?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 sem2/src/program.rs | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
 create mode 100644 sem2/src/program.rs

(limited to 'sem2/src/program.rs')

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);
+        }
+    }
+}
-- 
cgit v1.2.3