ff-uint 0.2.4

Library for building and interfacing with fixed-sized integers and finite fields
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

use crate::traits::Borsh;
use crate::Uint;
use crate::{BitIterBE, BitIteratorBE};

pub trait PrimeFieldParams {
    type Inner: Uint;
    const MODULUS: Self::Inner;
    const MODULUS_BITS: u32;
    const REPR_SHAVE_BITS: u32;
    const R: Self::Inner;
    const R2: Self::Inner;
    const INV: u64;
    const GENERATOR: Self::Inner;
    const S: u32;
    const ROOT_OF_UNITY: Self::Inner;
}

#[derive(Debug, PartialEq)]
pub enum LegendreSymbol {
    Zero = 0,
    QuadraticResidue = 1,
    QuadraticNonResidue = -1,
}

pub trait Field:
    Sized
    + Clone
    + Copy
    + Default
    + core::cmp::PartialEq
    + core::cmp::Eq
    + core::fmt::Debug
    + core::fmt::Display
{
    const ZERO: Self;
    const ONE: Self;

    #[cfg(feature = "rand_support")]
    fn random<R: rand::Rng + ?Sized>(rng: &mut R) -> Self;
    fn is_zero(&self) -> bool;

    fn wrapping_add(self, other: Self) -> Self;
    fn wrapping_sub(self, other: Self) -> Self;
    fn wrapping_mul(self, other: Self) -> Self;
    fn wrapping_div(self, other: Self) -> Self {
        self.wrapping_mul(other.checked_inv().expect("Division by zero"))
    }
    fn wrapping_neg(self) -> Self;
    fn square(self) -> Self;
    fn double(self) -> Self;
    fn checked_inv(self) -> Option<Self>;

    fn frobenius_map(self, power: usize) -> Self;

    fn pow<S: BitIterBE>(self, exp: S) -> Self {
        let mut res = Self::ONE;
        let mut found_one = false;
        for i in exp.bit_iter_be() {
            if found_one {
                res = res.square();
            } else {
                found_one = i;
            }
            if i {
                res = res.wrapping_mul(self);
            }
        }
        res
    }
}

pub trait SqrtField: Field {
    fn legendre(&self) -> LegendreSymbol;
    fn sqrt(&self) -> Option<Self>;
}

pub trait PrimeField:
    PrimeFieldParams + SqrtField + core::str::FromStr + From<&'static str> + Borsh
{
    fn from_uint(v: Self::Inner) -> Option<Self>;
    fn from_mont_uint(v: Self::Inner) -> Option<Self>;
    fn from_uint_unchecked(v: Self::Inner) -> Self;
    fn from_mont_uint_unchecked(v: Self::Inner) -> Self;

    fn to_uint(&self) -> Self::Inner;
    fn to_mont_uint(&self) -> Self::Inner;
    fn as_mont_uint(&self) -> &Self::Inner;
    fn as_mont_uint_mut(&mut self) -> &mut Self::Inner;

    fn to_other<Fq: PrimeField>(&self) -> Option<Fq> {
        let u = self.to_uint().to_other()?;

        if u >= Fq::MODULUS {
            None
        } else {
            Some(Fq::from_uint_unchecked(u))
        }
    }

    fn to_other_reduced<Fq: PrimeField>(&self) -> Fq {
        match self.to_uint().to_other::<Fq::Inner>() {
            Some(u) => Fq::from_uint_unchecked(u.wrapping_rem(Fq::MODULUS)),
            None => {
                let u = self
                    .to_uint()
                    .wrapping_rem(<Fq as PrimeFieldParams>::MODULUS.to_other().unwrap());
                Fq::from_uint_unchecked(u.to_other().unwrap())
            }
        }
    }
}