Merge branch 'powmod'

2 files changed, 49 insertions, 8 deletions

diff --git a/sem2/src/main.rs b/sem2/src/main.rs
index a983772..10e7871 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,18 @@ 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);
     }
     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 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() {