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/Cargo.lock | 37 +++++++----------- sem2/Cargo.toml | 2 +- sem2/src/algo.rs | 38 ++++++++++++++++++ sem2/src/main.rs | 111 ++++++++++++---------------------------------------- sem2/src/mpn.rs | 46 +++++++++++++++++++++- sem2/src/program.rs | 26 ++++++++++++ 6 files changed, 149 insertions(+), 111 deletions(-) create mode 100644 sem2/src/algo.rs create mode 100644 sem2/src/program.rs diff --git a/sem2/Cargo.lock b/sem2/Cargo.lock index ba4505a..99acdd9 100644 --- a/sem2/Cargo.lock +++ b/sem2/Cargo.lock @@ -8,12 +8,6 @@ version = "1.1.0" 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" @@ -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]] @@ -83,6 +76,15 @@ dependencies = [ "unicode-width", ] +[[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" @@ -185,17 +187,6 @@ dependencies = [ "bitflags", ] -[[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" @@ -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::() { - 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, + pub radix: u8, + pub digits: Vec, } 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 { if c >= 'a' as u8 { Some(c - 'a' as u8 + 10_u8) @@ -107,6 +129,26 @@ impl Number { } } +impl From 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 { + 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