From 4b906f732ee172bdd7f6df911a7695a8ade6dcf8 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sat, 18 Mar 2023 12:43:05 +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=D0=BE=D0=BF=D0=B5=D1=80=D0=B0=D1=86=D0=B8=D1=8F=20=D0=B2?= =?UTF-8?q?=D0=BE=D0=B7=D0=B2=D0=B5=D0=B4=D0=B5=D0=BD=D0=B8=D1=8F=20=D0=B2?= =?UTF-8?q?=20=D1=81=D1=82=D0=B5=D0=BF=D0=B5=D0=BD=D1=8C=20=D0=BF=D0=BE=20?= =?UTF-8?q?=D0=BC=D0=BE=D0=B4=D1=83=D0=BB=D1=8E?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- sem2/src/main.rs | 34 ++++++++++++++++++++++++++-------- sem2/src/mpn.rs | 21 +++++++++++++++++++++ 2 files changed, 47 insertions(+), 8 deletions(-) diff --git a/sem2/src/main.rs b/sem2/src/main.rs index a983772..ca52a20 100644 --- a/sem2/src/main.rs +++ b/sem2/src/main.rs @@ -29,7 +29,11 @@ fn main() { Ok(text) => text, Err(_) => return, }; - let b_text = match Text::new("Введите число:").prompt() { + let p_text = match Text::new("Введите степень:").prompt() { + Ok(text) => text, + Err(_) => return, + }; + let m_text = match Text::new("Введите модуль:").prompt() { Ok(text) => text, Err(_) => return, }; @@ -41,7 +45,14 @@ fn main() { return; } }; - let b = match mpn::Number::parse(&b_text, radix as u8) { + 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) { Ok(number) => number, Err(what) => { println!("{what}"); @@ -56,7 +67,14 @@ fn main() { return; } }; - let b_rug = match Integer::parse_radix(b_text, radix) { + 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!("Не удалось считать число"); @@ -65,19 +83,19 @@ fn main() { }; let mpn_start = Instant::now(); - let mpn_res = a.div_rem(b); + let mpn_res = a.pow_mod(&p, &m); let mpn_elapsed = mpn_start.elapsed(); let rug_start = Instant::now(); if let Ok(_) = &mpn_res { - let _rug_res = a_rug.div_rem(b_rug); + let _rug_res = a_rug.pow_mod(&p_rug, &m_rug); + println!("{_rug_res:?}"); } let rug_elapsed = rug_start.elapsed(); match mpn_res { - Ok((div, rem)) => { - println!("Частное: {}", div); - println!("Остаток: {}", rem); + Ok(res) => { + println!("Результат: {res}"); } Err(msg) => { println!("{msg}"); diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs index 97ba55d..991e813 100644 --- a/sem2/src/mpn.rs +++ b/sem2/src/mpn.rs @@ -343,6 +343,27 @@ impl Rem for Number { } } +impl Number { + pub fn pow_mod(&self, power: &Self, modulo: &Self) -> Result { + if modulo.is_zero() { + return Err("Модуль должен быть отличен от нуля".to_string()); + } + let one: Number = Number::from_digits(&vec![1], self.radix).unwrap(); + let two: Number = Number::from_digits(&vec![2], self.radix).unwrap(); + let mut acc = one.clone(); + let mut p = power.clone(); + let mut base = self.clone(); + while !p.is_zero() { + if p.clone() % two.clone() == one.clone() { + acc = (acc * base.clone()) % modulo.clone(); + } + p = p / two.clone(); + base = (base.clone() * base) % modulo.clone(); + } + return Ok(acc); + } +} + impl PartialEq for Number { fn eq(&self, other: &Self) -> bool { if self.len() != other.len() { -- cgit v1.2.3 From 66d688e038ee9274a932737dafeca12b9d6a3738 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Fri, 24 Mar 2023 11:38:44 +0400 Subject: =?UTF-8?q?=D0=A3=D0=B1=D1=80=D0=B0=D0=BD=20=D0=B2=D1=8B=D0=B2?= =?UTF-8?q?=D0=BE=D0=B4=20=D1=80=D0=B5=D0=B7=D1=83=D0=BB=D1=8C=D1=82=D0=B0?= =?UTF-8?q?=D1=82=D0=B0=20=D0=B1=D0=B8=D0=B1=D0=BB=D0=B8=D0=BE=D1=82=D0=B5?= =?UTF-8?q?=D0=BA=D0=B8=20rug?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- sem2/src/main.rs | 1 - 1 file changed, 1 deletion(-) diff --git a/sem2/src/main.rs b/sem2/src/main.rs index ca52a20..10e7871 100644 --- a/sem2/src/main.rs +++ b/sem2/src/main.rs @@ -89,7 +89,6 @@ fn main() { let rug_start = Instant::now(); if let Ok(_) = &mpn_res { let _rug_res = a_rug.pow_mod(&p_rug, &m_rug); - println!("{_rug_res:?}"); } let rug_elapsed = rug_start.elapsed(); -- cgit v1.2.3 From 0047be212165de45e25215daa863526c1dac98fe Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Mon, 3 Apr 2023 21:32:52 +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=D0=BE=D0=B1=D1=80=D0=B0=D0=B1=D0=BE=D1=82=D0=BA=D0=B0=20?= =?UTF-8?q?=D1=81=D1=82=D0=B5=D0=BF=D0=B5=D0=BD=D0=B8=200?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- sem2/src/mpn.rs | 3 +++ 1 file changed, 3 insertions(+) diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs index 991e813..e8a3c16 100644 --- a/sem2/src/mpn.rs +++ b/sem2/src/mpn.rs @@ -349,6 +349,9 @@ impl Number { return Err("Модуль должен быть отличен от нуля".to_string()); } let one: Number = Number::from_digits(&vec![1], self.radix).unwrap(); + if power.is_zero() { + return Ok(one.clone() % modulo.clone()); + } let two: Number = Number::from_digits(&vec![2], self.radix).unwrap(); let mut acc = one.clone(); let mut p = power.clone(); -- cgit v1.2.3 From 5b09f26c7cf95433528f428e56468b8ac5a4f013 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Mon, 3 Apr 2023 21:35:47 +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?=20b^n+1?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- sem2/src/mpn.rs | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs index e8a3c16..91d3ff8 100644 --- a/sem2/src/mpn.rs +++ b/sem2/src/mpn.rs @@ -301,10 +301,16 @@ impl Number { ) .unwrap(); + let b_num = Number::from_digits(&vec![0, 1], self.radix).unwrap(); + let mut b_pow = Number::from_digits(&vec![1], self.radix).unwrap(); + for _ in 0..=n { + b_pow = b_pow * b_num.clone(); + } + let (p, q) = if u_sub >= qv { (u_sub - qv, q as u8) } else { - (u_sub + v_number.clone() - qv, (q - 1) as u8) + (u_sub + b_pow - qv + v_number.clone(), (q - 1) as u8) }; for i in 0..n + 1 { u[j + i] = if i < p.len() { p.digits[i] } else { 0 }; -- cgit v1.2.3