Merge branch 'powmod'

1 files changed, 24 insertions, 0 deletions

diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs
index 1709136..91d3ff8 100644
--- a/sem2/src/mpn.rs
+++ b/sem2/src/mpn.rs
@@ -349,6 +349,30 @@ impl Rem for Number {
     }
 }
 
+impl Number {
+    pub fn pow_mod(&self, power: &Self, modulo: &Self) -> Result<Self, String> {
+        if modulo.is_zero() {
+            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();
+        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() {