From 056f59346b727c9367998a423551eaba52854fce Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 10 Nov 2022 14:56:20 +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=81=D0=B5=D0=B4=D1=8C=D0=BC=D0=B0=D1=8F=20=D0=BB=D0=B0?=
 =?UTF-8?q?=D0=B1=D0=B0?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab7/src/main.rs | 89 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 89 insertions(+)
 create mode 100644 lab7/src/main.rs

(limited to 'lab7/src/main.rs')

diff --git a/lab7/src/main.rs b/lab7/src/main.rs
new file mode 100644
index 0000000..271116a
--- /dev/null
+++ b/lab7/src/main.rs
@@ -0,0 +1,89 @@
+use rug::{rand::RandState, Complete, Integer};
+use std::io;
+
+fn rabin_miller_test(n: &Integer, k: u32) -> bool {
+    let one = Integer::from(1u32);
+    let two = Integer::from(2u32);
+    let n1 = Integer::from(n - 1u32);
+
+    let mut s = 0;
+    let mut d = n1.clone();
+    while d.mod_u(2u32) == 0 {
+        s += 1u32;
+        d /= 2u32;
+    }
+
+    let mut rand = RandState::new();
+
+    'outer: for _ in 0..k {
+        let bound = n.clone() - 4u32;
+        let a = bound.random_below(&mut rand) + 2u32;
+        let mut x = Integer::from(a.pow_mod_ref(&d, n).unwrap());
+        if x == one || x == n1 {
+            continue;
+        } else {
+            for _ in 0..=s - 1 {
+                x = Integer::from(x.pow_mod_ref(&two, n).unwrap());
+                if x == one {
+                    return false;
+                } else if x == n1 {
+                    continue 'outer;
+                }
+            }
+        }
+        return false;
+    }
+    return true;
+}
+
+fn main() {
+    println!("Введите положительное нечётное число n:");
+    let mut p = String::new();
+    let stdin = io::stdin();
+    match stdin.read_line(&mut p) {
+        Ok(_) => (),
+        Err(_) => {
+            println!("Произошла ошибка при чтении из стандартного ввода");
+            return ();
+        }
+    }
+    let p = match Integer::parse(p) {
+        Ok(parsed) => parsed.complete(),
+        Err(_) => {
+            println!("Не удалось считать число");
+            return ();
+        }
+    };
+    if p.is_divisible(&Integer::from(2u32)) {
+        println!("Введено чётное число");
+        return ();
+    }
+
+    println!("Введите количество раундов k:");
+    let mut k = String::new();
+    match stdin.read_line(&mut k) {
+        Ok(_) => (),
+        Err(_) => {
+            println!("Произошла ошибка при чтении из стандартного ввода");
+            return ();
+        }
+    }
+    let k = match k.trim_end().parse::<u32>() {
+        Ok(parsed) => parsed,
+        Err(_) => {
+            println!("Не удалось считать число");
+            return ();
+        }
+    };
+
+    let is_prime = rabin_miller_test(&p, k);
+    if is_prime {
+        let probability = 1f64 - 0.25f64.powf(k as f64);
+        println!(
+            "Число {} является простым с вероятностью {}",
+            &p, probability
+        );
+    } else {
+        println!("Число не является простым");
+    }
+}
-- 
cgit v1.2.3