From 00856e19b215222176cf0cb9c83fd880846c2c0f Mon Sep 17 00:00:00 2001 From: Andrew Guschin 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/algo.rs | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) create mode 100644 sem2/src/algo.rs (limited to 'sem2/src/algo.rs') 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; +} -- cgit v1.2.3