cryptix-bn254 0.1.0

//! This is the implementation of Galois Field with order of p^2.
//! Here we use x^2 + 1 as the irreducible polynomial.
//! 
//! A element in Fp_2 can be represented as polynomial a + bx, 
//! where a, b are elements in Fp
//! 
//! With x^2 + 1 as the irreducible polynomial, i.e. the modulus, 
//! arithmetic in this field can be represented as:
//! 
//! 1. add: `(a0 + b0x) + (a1 + b1x) = (a0 + a1) + (b0 + b1)x`
//! 2. sub: `(a0 + b0x) - (a0 - b0x) = (a0 - a1) + (b0 - b1)x`
//! 3. mul by Fp element c: `(a0 + b0x) * c = (a0c + b0cx)`
//! 3. mul: 
//!    ```text,ignore   
//!    (a0 + b0x) * (a1 + b1x) = a0a1 + (a0b1 + a1b0)x + b0b1x^2 mod (x^2 + 1)
//!                            = (a0a1 - b0b1) + (a0b1 + a1b0)x 
//!    ```
//! 

use core::ops::{Add, Sub, Mul, Neg};

use cryptix_bigint::property::IsBigInt;
use cryptix_field::field::montgomery::Montgomery;
use cryptix_field::group::*;
use cryptix_field::ring::*;
use cryptix_field::field::*;
use cryptix_field::field::montgomery::MontgomeryOps;

use super::{U256, BN254, FpElement};

/// Element in field F_{p^2}
/// 
/// `Fp2[i] = Fp[i] / (i^2 + 1)`
/// 
#[derive(PartialEq, Eq, Clone, Copy)]
pub struct Fp2Element(pub FpElement, pub FpElement);

impl core::fmt::Debug for Fp2Element {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "fp2!(\n    \"")?;
        self.0.fmt(f)?;
        write!(f, "\", \n    \"")?;
        self.1.fmt(f)?;
        write!(f, "\"\n)\n    ")
    }
}

impl AbelianGroup for Fp2Element { }

impl Group for Fp2Element { }

impl Add for Fp2Element {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Self(self.0 + rhs.0, self.1 + rhs.1)
    }
}

impl Sub for Fp2Element {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        Self(self.0 - rhs.0, self.1 - rhs.1)
    }
}

impl AddIdentity for Fp2Element {
    const ADD_IDENTITY: Self = Self(FpElement::ZERO, FpElement::ZERO);
}

impl Neg for Fp2Element { 
    type Output = Self;

    fn neg(self) -> Self::Output {
        Self(-self.0, -self.1)
    }
}

/// # Safety
/// 
/// Element is backed by biguint, which is associative under addition
impl AssociativeAdd for Fp2Element { }

/// # Safety
/// 
/// Element is backed by biguint, which is communicative under addition
impl CommunicativeAdd for Fp2Element { }


impl Ring for Fp2Element { }

impl Mul for Fp2Element {
    type Output = Self;

    /// calculate a * b mod m
    /// this can be achieved more efficiently with montgomery multiplication
    fn mul(self, rhs: Self) -> Self::Output {
        self.mont_mul(rhs).mont_form()
    }
}

/// # Safety
/// 
/// our element type is backed by biguint, so mod mul is associative
impl AssociativeMul for Fp2Element { }

/// # Safety
/// 
/// our element type is backed by biguint, so mod mul is distributive over add
impl DistributiveMul for Fp2Element { }


/// # Safety
/// 
/// 1 is the multiplicative ideneity for biguint
impl MulIdentity for Fp2Element {
    const MUL_IDENTITY: Self = Self(FpElement::ONE, FpElement::ZERO);
}

/// # Safety
/// 
/// BigUInt mod mul is communicative
impl CommunicativeMul for Fp2Element { }

/// The montgomery trait bound restricts the modular to odd prime
impl MulInverse for Fp2Element {
    fn mul_inv(self) -> Self {
        // self.mont_inv() => self^{-1} RR mod P
        self.mont_inv().mont_mul_fp(BN254::R_INV_P)
    }
}


impl Field for Fp2Element {
    fn hlv(self) -> Self {
        Self(self.0.hlv(), self.1.hlv())
    }

    fn is_zero(&self) -> bool {
        self.0.is_zero() && self.1.is_zero()
    }
}

impl From<FpElement> for Fp2Element {
    fn from(value: FpElement) -> Self {
        Self(value, FpElement::ZERO)
    }
}

impl MontgomeryOps<U256, BN254> for Fp2Element {
    /// input: 
    /// - lhs: Fp^2 element `a0 + b0x`
    /// - rhs: Fp^2 element `a1 + b1x`
    /// 
    /// output: their production * R^{-1} with respect to irreducible polynomial `x^2 + 1`
    /// 
    /// ```text,ignore
    ///   (a0 + b0x) * (a1 + b1x)
    /// = (a0a1 + (a0b1 + a1b0)x + b0b1x^2) mod (x^2 + 1)
    /// = (a0a1 - b0b1) + (a0b1 + a1b0)x
    /// ```
    fn mont_mul(self, rhs: Self) -> Self {
        let (a0, b0) = (self.0, self.1);
        let (a1, b1) = (rhs.0, rhs.1);

        let a0a1 = a0.mont_mul(a1);
        let b0b1 = b0.mont_mul(b1);

        Self(
            a0a1 - b0b1, 
             // a0b1 + a1b0 = (a0 + b0) * (a1 + b1) - a0a1 - b0b1
            (a0 + b0).mont_mul(a1 + b1) - a0a1 - b0b1
        )
    }

    /// input: Fp2 element `a + bx`
    /// output: Fp2 element `(c + dx)RR` so that `(c + dx) * (a + bx) = 1`, that is
    /// 
    /// ```text,ignore
    ///  ac - bd + (bc + ad)x = 1
    /// ```
    /// 
    /// which means
    /// 
    /// ```text,ignore
    /// ac - bd = 1
    /// bc + ad = 0
    /// ```
    /// 
    /// solving these equations for `c, d`, we can know that
    /// 
    /// ```text,ignore
    /// c = a / (a^2 + b^2)
    /// d = -b / (a^2 + b^2)
    /// ```
    fn mont_inv(self) -> Self {
        // t = (a^2 * R^-1 + b^2 * R^-1)^-1 * RR = (a^2 + b^2)^-1 * RRR
        let t = (self.0.mont_sqr() + self.1.mont_sqr()).mont_inv();
        // c' = a * t * R^-1 = c * RR; d' = d * RR
        Self(self.0.mont_mul(t), -self.1.mont_mul(t))
    }

    /// input: 
    /// - Fp^2 element: `a + bx`
    /// - Fp element: `c`
    /// 
    /// output: their production `(a + bx) * c * R^{-1} = acR^{-1} + bcR^{-1}x`
    fn mont_mul_fp(self, rhs: FpElement) -> Self {
        Self(
            self.0.mont_mul(rhs),
            self.1.mont_mul(rhs)
        )
    }

    fn mont_rdc(self) -> Self {
        Self(self.0.mont_rdc(), self.1.mont_rdc())
    }
}

impl Fp2Element {
    /// input: Fp^2 Element `a + bi`
    /// 
    /// output: `(a + bi) * ξ = (a + bi)(1 + i) = (a - b) + (a + b)i`
    pub fn mul_xi(self) -> Self {
        Self(self.0 - self.1, self.0 + self.1)
    }

    /// TODO
    pub fn mul_3b(self) -> Self {
        let t = self.mont_mul(BN254::B_DIV_XI_MONT);
        t + t + t
    }

    /// TODO
    pub fn map_frob(self) -> Self {
        self.conjugate()
    }

    /// input: Fp^2 element: `a + bx`
    /// output: its conjugate element: `a - bx`
    pub fn conjugate(self) -> Self {
        Self(self.0, -self.1)
    }
}

#[cfg(feature = "rand")]
impl Fp2Element {
    pub fn rand(rng: &mut impl rand_core::CryptoRngCore) -> Self {
        Self(FpElement::rand(rng), FpElement::rand(rng))
    }
}

impl From<Fp2Element> for [u8; U256::BYTE_LEN * 2] {
    fn from(val: Fp2Element) -> Self {
        let mut buf = [0_u8; U256::BYTE_LEN * 2];
        let tmp: [u8; U256::BYTE_LEN] = val.0.into();
        buf[..U256::BYTE_LEN].copy_from_slice(&tmp);
        let tmp: [u8; U256::BYTE_LEN] = val.1.into();
        buf[U256::BYTE_LEN..].copy_from_slice(&tmp);
        buf
    }
}