1 files changed, 38 insertions, 0 deletions
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;
+}