Добавлена реализация алгоритма нахождения элемента g порядка q в конечном поле Z_p.

1 files changed, 44 insertions, 2 deletions

diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs
index 91d3ff8..cb95e7f 100644
--- a/sem2/src/mpn.rs
+++ b/sem2/src/mpn.rs
@@ -1,11 +1,12 @@
+use fastrand;
 use std::cmp::{max, Ordering};
 use std::fmt;
 use std::ops::{Add, Div, Index, IndexMut, Mul, Rem, Sub};
 
 #[derive(Debug)]
 pub struct Number {
-    radix: u8,
-    digits: Vec<u8>,
+    pub radix: u8,
+    pub digits: Vec<u8>,
 }
 
 impl Clone for Number {
@@ -81,6 +82,27 @@ impl Number {
         return true;
     }
 
+    pub fn random_below(&self) -> Number {
+        loop {
+            let num = Number::random_num(self.len(), self.radix);
+            if num < self.clone() {
+                return num;
+            }
+        }
+    }
+
+    pub fn random_num(size: usize, radix: u8) -> Number {
+        let mut digits = Vec::new();
+        for _ in 0..size - 1 {
+            digits.push(fastrand::u8(..radix));
+        }
+        digits.push(fastrand::u8(1..radix));
+
+        return Number::from_digits(&digits, radix).unwrap();
+    }
+}
+
+impl Number {
     fn parse_digit(c: u8) -> Option<u8> {
         if c >= 'a' as u8 {
             Some(c - 'a' as u8 + 10_u8)
@@ -107,6 +129,26 @@ impl Number {
     }
 }
 
+impl From<u64> for Number {
+    fn from(mut num: u64) -> Self {
+        let radix = 10;
+        let mut digits = Vec::new();
+        while num != 0 {
+            let digit = num % radix;
+            num /= radix;
+            digits.push(digit as u8);
+        }
+        if digits.len() == 0 {
+            digits.push(0);
+        }
+        return Number {
+            radix: radix as u8,
+            digits,
+        }
+        .fix_leading_zeros();
+    }
+}
+
 impl fmt::Display for Number {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         for i in (0..self.digits.len()).rev() {