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 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(+) (limited to 'sem2/src/mpn.rs') 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(-) (limited to 'sem2/src/mpn.rs') 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