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())
            }
        }
    }
}