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/mpn.rs | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'sem2/src/mpn.rs') 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