number_theory/
structs.rs

1use crate::ntrait::NumberTheory;
2
3/// A primality certificate, currently a modification of the Pratt Certificate.
4/// 
5/// Instead of checking if a^(n-1) mod n we use the stronger form of the Fermat test
6/// which permits proving that Carmichael numbers are composite  
7#[derive(Clone)]
8pub struct Certificate<T: NumberTheory>{
9   pub(crate) n: T,
10   pub(crate) witness: T,
11   pub(crate) fctr: Vec<T>,
12}
13
14impl<T: NumberTheory> Certificate<T>{
15
16  pub(crate) fn new(n: T, witness: T, fctr: Vec<T>) -> Self{
17     Self{n,witness,fctr}
18  } 
19  
20 
21    /// Check the certificate 
22   pub fn check(&self) -> bool{
23     if self.fctr.is_empty(){
24        return false;
25     }
26
27     if !self.n.clone().strong_fermat(self.witness.clone()){
28         return false;
29     }
30
31     for i in self.fctr.iter(){
32     if self.witness.exp_residue(i.clone(), self.n.clone()).is_unit() {
33         return false
34        }
35     }
36   return true;
37   }
38   
39}
40
41/// Factorization of an integer
42#[derive(Clone,Default)]
43pub struct Factorization<T>{
44   pub(crate) base: Vec<T>,
45   pub(crate) power: Vec<u64>,
46}
47
48impl <T: NumberTheory> Factorization<T>{
49
50   pub fn new() -> Self{
51      Self{base: vec![], power: vec![]}
52   }
53   
54   pub fn from_components(base: Vec<T>,power: Vec<u64>) -> Self{
55        Self{base,power}
56   }
57   
58   pub fn factor_iter(&self) -> std::slice::Iter<T>{
59      self.base.iter()
60   }
61   
62   pub fn power_iter(&self) -> std::slice::Iter<u64>{
63     self.power.iter()
64   }
65   
66   pub fn add_factor(&mut self, fctr: T){
67      self.base.push(fctr);
68   }
69   
70   pub fn add_power(&mut self, power: u64){
71      self.power.push(power);
72   }
73   
74  pub fn pair_iter(&self) -> std::iter::Zip<std::slice::Iter<T>,std::slice::Iter<u64>>{
75      self.base.iter().zip(self.power.iter())
76  } 
77  
78  pub fn max(&self) -> T{
79     self.factor_iter().max().unwrap().clone() 
80  }
81  
82  pub fn k_free(&self, k: u64) -> bool{
83      for i in self.power_iter(){
84        if *i >= k{
85           return false;
86        }
87      }
88      return true;
89  }
90  
91  pub fn prime_omega(&self) -> u64{
92     self.power_iter().sum::<u64>()
93  }
94  
95  }
96  
97 impl<T: NumberTheory> std::fmt::Display for Factorization<T>{
98 
99   fn fmt(&self,f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error>{
100
101      let mut output = String::new();
102      if self.power[0] != 1{
103        output+=&(self.base[0].to_string()+"^"+&self.power[0].to_string());
104      }
105      else{
106        output+=&(self.base[0].to_string());
107      }
108      if self.base.len() > 1{
109      for i in 1..self.base.len(){
110         if self.power[i] != 1{
111         let pair = self.base[i].to_string()+"^"+&self.power[i].to_string();
112         output+=&(" * ".to_owned() + &pair);
113         }
114         else{
115         let pair = self.base[i].to_string();
116         output+= &(" * ".to_owned()+&pair);
117         }
118      }
119      }
120      write!(f,"{}",output)
121  }
122}
123
124
number_theory/structs.rs

number_theory/
structs.rs
