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

6 files changed, 149 insertions, 111 deletions

diff --git a/sem2/Cargo.lock b/sem2/Cargo.lock
index ba4505a..99acdd9 100644
--- a/sem2/Cargo.lock
+++ b/sem2/Cargo.lock
@@ -9,12 +9,6 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"
 
 [[package]]
-name = "az"
-version = "1.2.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7b7e4c2464d97fe331d41de9d5db0def0a96f4d823b8b32a2efd503578988973"
-
-[[package]]
 name = "bitflags"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -58,13 +52,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "c9b0705efd4599c15a38151f4721f7bc388306f61084d3bfd50bd07fbca5cb60"
 
 [[package]]
-name = "gmp-mpfr-sys"
-version = "1.5.0"
+name = "fastrand"
+version = "1.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "751710e4e568a3057987c7dc5bf85aab59b9a306a014a1900e52bbe427bc0cf6"
+checksum = "e51093e27b0797c359783294ca4f0a911c270184cb10f85783b118614a1501be"
 dependencies = [
- "libc",
- "windows-sys 0.42.0",
+ "instant",
 ]
 
 [[package]]
@@ -84,6 +77,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "instant"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7a5bbe824c507c5da5956355e86a746d82e0e1464f65d862cc5e71da70e94b2c"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
 name = "lazy_static"
 version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -186,17 +188,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "rug"
-version = "1.19.1"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "a465f6576b9f0844bd35749197576d68e3db169120532c4e0f868ecccad3d449"
-dependencies = [
- "az",
- "gmp-mpfr-sys",
- "libc",
-]
-
-[[package]]
 name = "scopeguard"
 version = "1.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -206,8 +197,8 @@ checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
 name = "sem2"
 version = "0.1.0"
 dependencies = [
+ "fastrand",
  "inquire",
- "rug",
 ]
 
 [[package]]
diff --git a/sem2/Cargo.toml b/sem2/Cargo.toml
index aee29a2..4ae5a60 100644
--- a/sem2/Cargo.toml
+++ b/sem2/Cargo.toml
@@ -6,5 +6,5 @@ edition = "2021"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
+fastrand = "1.9.0"
 inquire = "0.5.3"
-rug = "1.17"
diff --git a/sem2/src/algo.rs b/sem2/src/algo.rs
new file mode 100644
index 0000000..0a54c72
--- /dev/null
+++ b/sem2/src/algo.rs
@@ -0,0 +1,38 @@
+use crate::mpn::Number;
+
+pub fn rabin_miller_test(n: &Number, k: u32) -> bool {
+    if n.clone() % 2.into() == 0.into() {
+        return false;
+    }
+
+    let n1: Number = n.clone() - 1.into();
+
+    let mut s = 0;
+    let mut d = n1.clone();
+
+    while d.clone() % 2.into() == 0.into() {
+        s += 1u32;
+        d = d / 2.into();
+    }
+
+    'outer: for _ in 0..k {
+        let bound = n.clone() - 4.into();
+        let a = bound.random_below() + 2.into();
+        let mut x = a.pow_mod(&d, &n).unwrap();
+
+        if x == 1.into() || x == n1 {
+            continue;
+        } else {
+            for _ in 0..=s - 1 {
+                x = x.pow_mod(&2.into(), &n).unwrap();
+                if x == 1.into() {
+                    return false;
+                } else if x == n1 {
+                    continue 'outer;
+                }
+            }
+        }
+        return false;
+    }
+    return true;
+}
diff --git a/sem2/src/main.rs b/sem2/src/main.rs
index 10e7871..adf47b8 100644
--- a/sem2/src/main.rs
+++ b/sem2/src/main.rs
@@ -1,58 +1,18 @@
+use fastrand;
 use inquire::Text;
-use rug::{Complete, Integer};
 use std::time::Instant;
+mod algo;
 mod mpn;
+mod program;
 
 fn main() {
-    let radix = match Text::new("Введите основание системы счисления:").prompt()
-    {
-        Ok(text) => text,
-        Err(_) => return,
-    };
-    let radix = match radix.parse::<i32>() {
-        Ok(number) => {
-            if number > 36 || number < 2 {
-                println!(
-                    "Система счисления должна принадлежать отрезку [2,36]"
-                );
-                return;
-            }
-            number
-        }
-        Err(_) => {
-            println!("Основание должно быть десятичным числом");
-            return;
-        }
-    };
+    let radix = 10;
 
-    let a_text = match Text::new("Введите число:").prompt() {
-        Ok(text) => text,
-        Err(_) => return,
-    };
-    let p_text = match Text::new("Введите степень:").prompt() {
+    let q_text = match Text::new("Введите число q:").prompt() {
         Ok(text) => text,
         Err(_) => return,
     };
-    let m_text = match Text::new("Введите модуль:").prompt() {
-        Ok(text) => text,
-        Err(_) => return,
-    };
-
-    let a = match mpn::Number::parse(&a_text, radix as u8) {
-        Ok(number) => number,
-        Err(what) => {
-            println!("{what}");
-            return;
-        }
-    };
-    let p = match mpn::Number::parse(&p_text, radix as u8) {
-        Ok(number) => number,
-        Err(what) => {
-            println!("{what}");
-            return;
-        }
-    };
-    let m = match mpn::Number::parse(&m_text, radix as u8) {
+    let q = match mpn::Number::parse(&q_text, radix as u8) {
         Ok(number) => number,
         Err(what) => {
             println!("{what}");
@@ -60,41 +20,29 @@ fn main() {
         }
     };
 
-    let a_rug = match Integer::parse_radix(a_text, radix) {
-        Ok(parsed) => parsed.complete(),
-        Err(_) => {
-            println!("Не удалось считать число");
-            return;
-        }
-    };
-    let p_rug = match Integer::parse_radix(p_text, radix) {
-        Ok(parsed) => parsed.complete(),
-        Err(_) => {
-            println!("Не удалось считать число");
-            return;
-        }
-    };
-    let m_rug = match Integer::parse_radix(m_text, radix) {
-        Ok(parsed) => parsed.complete(),
-        Err(_) => {
-            println!("Не удалось считать число");
-            return;
-        }
-    };
-
-    let mpn_start = Instant::now();
-    let mpn_res = a.pow_mod(&p, &m);
-    let mpn_elapsed = mpn_start.elapsed();
+    if !algo::rabin_miller_test(&q, 10) {
+        println!("Число q должно быть простым");
+        return;
+    }
 
-    let rug_start = Instant::now();
-    if let Ok(_) = &mpn_res {
-        let _rug_res = a_rug.pow_mod(&p_rug, &m_rug);
+    let mut p;
+    loop {
+        let s = mpn::Number::random_num(fastrand::usize(1..=30), radix);
+        println!("s = {s}");
+        p = q.clone() * s + 1.into();
+        if algo::rabin_miller_test(&p, 10) {
+            break;
+        }
     }
-    let rug_elapsed = rug_start.elapsed();
+    println!("Сгенерированное простое p: {p}");
+
+    let t_start = Instant::now();
+    let g = program::find_of_order(&p, &q);
+    let t_elapsed = t_start.elapsed();
 
-    match mpn_res {
+    match g {
         Ok(res) => {
-            println!("Результат: {res}");
+            println!("Найденный элемент g: {res}");
         }
         Err(msg) => {
             println!("{msg}");
@@ -102,12 +50,5 @@ fn main() {
         }
     }
 
-    println!(
-        "Операция произведения выполнена в mpn за {} наносекунд",
-        mpn_elapsed.as_nanos()
-    );
-    println!(
-        "Операция произведения выполнена в rug за {} наносекунд",
-        rug_elapsed.as_nanos()
-    );
+    println!("Операция выполнена за {} наносекунд", t_elapsed.as_nanos());
 }
diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs
index 91d3ff8..cb95e7f 100644
--- a/sem2/src/mpn.rs
+++ b/sem2/src/mpn.rs
@@ -1,11 +1,12 @@
+use fastrand;
 use std::cmp::{max, Ordering};
 use std::fmt;
 use std::ops::{Add, Div, Index, IndexMut, Mul, Rem, Sub};
 
 #[derive(Debug)]
 pub struct Number {
-    radix: u8,
-    digits: Vec<u8>,
+    pub radix: u8,
+    pub digits: Vec<u8>,
 }
 
 impl Clone for Number {
@@ -81,6 +82,27 @@ impl Number {
         return true;
     }
 
+    pub fn random_below(&self) -> Number {
+        loop {
+            let num = Number::random_num(self.len(), self.radix);
+            if num < self.clone() {
+                return num;
+            }
+        }
+    }
+
+    pub fn random_num(size: usize, radix: u8) -> Number {
+        let mut digits = Vec::new();
+        for _ in 0..size - 1 {
+            digits.push(fastrand::u8(..radix));
+        }
+        digits.push(fastrand::u8(1..radix));
+
+        return Number::from_digits(&digits, radix).unwrap();
+    }
+}
+
+impl Number {
     fn parse_digit(c: u8) -> Option<u8> {
         if c >= 'a' as u8 {
             Some(c - 'a' as u8 + 10_u8)
@@ -107,6 +129,26 @@ impl Number {
     }
 }
 
+impl From<u64> for Number {
+    fn from(mut num: u64) -> Self {
+        let radix = 10;
+        let mut digits = Vec::new();
+        while num != 0 {
+            let digit = num % radix;
+            num /= radix;
+            digits.push(digit as u8);
+        }
+        if digits.len() == 0 {
+            digits.push(0);
+        }
+        return Number {
+            radix: radix as u8,
+            digits,
+        }
+        .fix_leading_zeros();
+    }
+}
+
 impl fmt::Display for Number {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         for i in (0..self.digits.len()).rev() {
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);
+        }
+    }
+}