cralgebra 0.2.1

A fast crypto algebra library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

use crate::*;
use noether::*;
use num_traits::*;
use std::ops::*;

fn prime_factors_naive<T: Clone + Zero + ClosedAddAssign + One + ClosedMul + Euclid + PartialOrd>(
    mut n: T,
) -> Vec<T> {
    debug_assert!(!n.is_zero());
    debug_assert!(!n.is_one());
    let mut r = vec![];
    let mut x = T::one() + T::one();
    while x.clone() * x.clone() <= n {
        if n.clone().rem_euclid(x.clone()).is_zero() {
            r.push(x.clone());
            n = n.div_euclid(&x);
            while n.clone().rem_euclid(x.clone()).is_zero() {
                n = n.div_euclid(&x);
            }
        }
        x += T::one();
    }
    r
}

fn pollard_rho<T: Clone + Zero + ClosedAdd + ClosedSub + One + ClosedMul + Euclid + PartialOrd>(
    n: T,
) -> Option<T> {
    let mut x = T::one() + T::one();
    let mut y = T::one() + T::one();
    let mut d = T::one();
    let g = |z: T| (z.clone() * z + T::one()).rem_euclid(n.clone());
    while d.is_one() {
        x = g(x);
        y = g(g(y));
        let diff = if x > y {
            x.clone() - y.clone()
        } else {
            y.clone() - x.clone()
        };
        d = diff.gcd(n.clone());
    }
    if d == n {
        None
    } else {
        Some(d)
    }
}

fn sieve_erathosthenes(n: usize) -> Vec<usize> {
	let mut sieve = Vec::with_capacity(n + 1);
	sieve.fill(false);
    sieve[0] = true;
    sieve[1] = true;
    for i in 2..n.isqrt() + 1 {
        if !sieve[i] {
            for j in (i * i..n + 1).step_by(i) {
                sieve[j] = true
            }
        }
    }
    let mut r = vec![];
    for x in 2..n + 1 {
    	r.push(x);
    }
    r
}

/*fn find_base<T>(n: T) {
	usize max_base = 100;
	let primes = sieve_erathosthenes(max_base);
	for p in primes {
		
	}
}

fn prime_factors_quadratic_sieve<T>(n: T) {
	let base = quadratic_sieve_find_base(n);
}*/

pub trait Factorization:
    Clone + Zero + ClosedAddAssign + One + ClosedMul + Euclid + PartialOrd
{
    fn prime_factors(self) -> Vec<Self> {
        prime_factors_naive(self)
    }
}

impl Factorization for u8 {}
impl Factorization for u16 {}
impl Factorization for u32 {}
impl Factorization for u64 {}
impl Factorization for u128 {}