fp/field/

mod.rs

use self::field_internal::FieldInternal;
use crate::prime::Prime;

pub mod element;
pub(crate) mod field_internal;

pub mod fp;
pub mod smallfq;

use element::FieldElement;
pub use fp::Fp;
pub use smallfq::SmallFq;

pub trait Field: FieldInternal + Sized {
    type Characteristic: Prime;

    fn characteristic(self) -> Self::Characteristic;

    fn degree(self) -> u32;

    fn q(self) -> u32 {
        self.characteristic().pow(self.degree())
    }

    fn zero(self) -> FieldElement<Self>;
    fn one(self) -> FieldElement<Self>;

    #[cfg(feature = "proptest")]
    fn arb_element(self) -> impl proptest::strategy::Strategy<Value = FieldElement<Self>>;
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;

    use super::{Field, SmallFq, element::FieldElement};
    use crate::prime::P2;

    #[test]
    fn test_f_4() {
        // Multiplication table generated by Sage.
        let f4 = SmallFq::new(P2, 2);
        let one = f4.one();
        let a = f4.a();

        let mut elements = vec![one];
        for _ in 1..f4.q() {
            let prev = elements.last().unwrap();
            elements.push(*prev * a);
        }

        let expansions = vec![one, a, a + one, one];

        assert_eq!(elements, expansions);
    }

    #[test]
    fn test_f_8() {
        // Multiplication table generated by Sage.
        let f8 = SmallFq::new(P2, 3);
        let one = f8.one();
        let a = f8.a();
        let a2 = a * a;

        let mut elements = vec![one];
        for _ in 1..f8.q() {
            let prev = elements.last().unwrap();
            elements.push(*prev * a);
        }

        let expansions = vec![one, a, a2, a + one, a2 + a, a2 + a + one, a2 + one, one];

        assert_eq!(elements, expansions);
    }

    #[test]
    fn test_f_16() {
        // Multiplication table generated by Sage.
        let f16 = SmallFq::new(P2, 4);
        let one = f16.one();
        let a = f16.a();
        let a2 = a * a;
        let a3 = a2 * a;

        let mut elements = vec![one];
        for _ in 1..f16.q() {
            let prev = elements.last().unwrap();
            elements.push(*prev * a);
        }

        let expansions = vec![
            one,
            a,
            a2,
            a3,
            a + one,
            a2 + a,
            a3 + a2,
            a3 + a + one,
            a2 + one,
            a3 + a,
            a2 + a + one,
            a3 + a2 + a,
            a3 + a2 + a + one,
            a3 + a2 + one,
            a3 + one,
            one,
        ];

        assert_eq!(elements, expansions);
    }

    #[cfg(feature = "odd-primes")]
    #[test]
    fn test_f_9() {
        use crate::prime::P3;

        // Multiplication table generated by Sage.
        let f9 = SmallFq::new(P3, 2);

        let one = f9.one();
        let two = one + one;
        let a = f9.a();

        let mut elements = vec![one];
        for _ in 1..f9.q() {
            let prev = elements.last().unwrap();
            elements.push(*prev * a);
        }

        let expansions = vec![
            one,
            a,
            a + one,
            two * a + one,
            two,
            two * a,
            two * a + two,
            a + two,
            one,
        ];

        assert_eq!(elements, expansions);
    }

    pub(super) fn arb_elements<F: Field, const N: usize>()
    -> impl Strategy<Value = (F, [FieldElement<F>; N])> {
        any::<F>().prop_flat_map(move |f| (Just(f), std::array::from_fn(|_| f.arb_element())))
    }

    /// Test the field axioms and good behavior of the Frobenius endomorphism.
    macro_rules! field_tests {
        ($field:ty) => {
            use proptest::prelude::*;

            use crate::{
                field::{element::FieldElement, Field},
                prime::Prime,
            };

            // We shadow the `arb_elements` function with one that is specialized to the concrete
            // field type we're working with
            fn arb_elements<const N: usize>(
            ) -> impl Strategy<Value = ($field, [FieldElement<$field>; N])> {
                crate::field::tests::arb_elements()
            }

            proptest! {
                #[test]
                fn test_bit_length((f, []) in arb_elements()) {
                    use crate::field::field_internal::FieldInternal;
                    prop_assert!(f.bit_length() <= 63);
                }

                #[test]
                fn test_addition_associative((_, [a, b, c]) in arb_elements()) {
                    prop_assert_eq!((a + b) + c, a + (b + c));
                }

                #[test]
                fn test_addition_identity((f, [a]) in arb_elements()) {
                    prop_assert_eq!(a + f.zero(), a);
                }

                #[test]
                fn test_addition_inverse((f, [a]) in arb_elements()) {
                    prop_assert_eq!(a + (-a), f.zero());
                }

                #[test]
                fn test_addition_commutative((_, [a, b]) in arb_elements()) {
                    prop_assert_eq!(a + b, b + a);
                }

                #[test]
                fn test_multiplication_associative((_, [a, b, c]) in arb_elements()) {
                    prop_assert_eq!((a * b) * c, a * (b * c));
                }

                #[test]
                fn test_multiplication_identity((f, [a]) in arb_elements()) {
                    prop_assert_eq!(a * f.one(), a);
                }

                #[test]
                fn test_multiplication_inverse((f, [a]) in arb_elements()) {
                    if a != f.zero() {
                        prop_assert_eq!(a * a.inv().unwrap(), f.one());
                    }
                }

                #[test]
                fn test_multiplication_commutative((_, [a, b]) in arb_elements()) {
                    prop_assert_eq!(a * b, b * a);
                }

                #[test]
                fn test_division_is_multiplication_by_inverse((f, [a, b]) in arb_elements()) {
                    if b != f.zero() {
                        prop_assert_eq!((a / b).unwrap(), a * b.inv().unwrap());
                    }
                }

                #[test]
                fn test_distributive((_, [a, b, c]) in arb_elements()) {
                    prop_assert_eq!(a * (b + c), a * b + a * c);
                }

                #[test]
                fn test_frobenius_is_pth_power((f, [a]) in arb_elements()) {
                    let a_frob = a.frobenius();
                    let a_pth_power = (0..f.characteristic().as_u32()).fold(f.one(), |acc, _| acc * a);
                    prop_assert_eq!(a_frob, a_pth_power);
                }

                #[test]
                fn test_frobenius_additive((_, [a, b]) in arb_elements()) {
                    prop_assert_eq!((a + b).frobenius(), a.frobenius() + b.frobenius());
                }

                #[test]
                fn test_frobenius_multiplicative((_, [a, b]) in arb_elements()) {
                    prop_assert_eq!((a * b).frobenius(), a.frobenius() * b.frobenius());
                }
            }
        };
    }

    pub(super) use field_tests;
}