polycore 0.1.6

Fields, prime fields, sparse and dense polynomials, and sparse echelon forms.
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

use std::fmt::Debug;
use std::ops::{Div, Neg, Sub};

use num_traits::{One, Zero};

/// A field given by its operators. Every type with these operations is one, so `BigRational`,
/// [`crate::Fp`], [`crate::Gf`] and user extensions such as `Q(sqrt(m))` need no wrapper.
pub trait Field:
    Clone
    + PartialEq
    + Debug
    + Zero
    + One
    + Neg<Output = Self>
    + Sub<Output = Self>
    + Div<Output = Self>
{
    /// The multiplicative inverse, or `None` for zero.
    fn inverse(&self) -> Option<Self> {
        (!self.is_zero()).then(|| Self::one() / self.clone())
    }
}

impl<F> Field for F where
    F: Clone + PartialEq + Debug + Zero + One + Neg<Output = F> + Sub<Output = F> + Div<Output = F>
{
}

/// `x^e` by repeated squaring.
pub fn pow<F: Field>(x: &F, mut e: u64) -> F {
    let (mut base, mut acc) = (x.clone(), F::one());
    while e > 0 {
        if e & 1 == 1 {
            acc = acc * base.clone();
        }
        e >>= 1;
        if e > 0 {
            base = base.clone() * base;
        }
    }
    acc
}

/// `n` as a field element, by doubling.
pub fn nat<F: Field>(n: u64) -> F {
    let two = F::one() + F::one();
    (0..u64::BITS - n.leading_zeros())
        .rev()
        .fold(F::zero(), |acc, i| {
            let acc = acc * two.clone();
            if n >> i & 1 == 1 { acc + F::one() } else { acc }
        })
}