polycore/
field.rs

1use std::fmt::Debug;
2use std::ops::{Div, Neg, Sub};
3
4use num_traits::{One, Zero};
5
6/// A field given by its operators. Every type with these operations is one, so `BigRational`,
7/// [`crate::Fp`], [`crate::Gf`] and user extensions such as `Q(sqrt(m))` need no wrapper.
8pub trait Field:
9    Clone
10    + PartialEq
11    + Debug
12    + Zero
13    + One
14    + Neg<Output = Self>
15    + Sub<Output = Self>
16    + Div<Output = Self>
17{
18    /// The multiplicative inverse, or `None` for zero.
19    fn inverse(&self) -> Option<Self> {
20        (!self.is_zero()).then(|| Self::one() / self.clone())
21    }
22}
23
24impl<F> Field for F where
25    F: Clone + PartialEq + Debug + Zero + One + Neg<Output = F> + Sub<Output = F> + Div<Output = F>
26{
27}
28
29/// `x^e` by repeated squaring.
30pub fn pow<F: Field>(x: &F, mut e: u64) -> F {
31    let (mut base, mut acc) = (x.clone(), F::one());
32    while e > 0 {
33        if e & 1 == 1 {
34            acc = acc * base.clone();
35        }
36        e >>= 1;
37        if e > 0 {
38            base = base.clone() * base;
39        }
40    }
41    acc
42}
43
44/// `n` as a field element, by doubling.
45pub fn nat<F: Field>(n: u64) -> F {
46    let two = F::one() + F::one();
47    (0..u64::BITS - n.leading_zeros())
48        .rev()
49        .fold(F::zero(), |acc, i| {
50            let acc = acc * two.clone();
51            if n >> i & 1 == 1 { acc + F::one() } else { acc }
52        })
53}
polycore/field.rs

polycore/
field.rs
