fgf 3.0.0

//! Normal-basis binary presentations at degrees 2, 4, and 8.
//!
//! [`Normal`] wraps a polynomial [`Polynomial`] basis element
//! `E` into its conjugate basis: bit `i` selects `E^(2^i)`, and one is all
//! `N` bits set. The descriptor pins both coordinate matrices; the inverse
//! columns come from bounded enumeration of the forward map, never from a
//! matrix solver.
//!
//! Smallest valid test instances: `E = 2` over `P = 0x7`, `E = 8` over
//! `P = 0x13`, and `E = 0x20` over [`AES`](super::poly::AES) and
//! [`RS`](super::poly::RS).
//!
//! ```compile_fail,E0080
//! // E = 1 has all conjugates equal to one, so the basis collapses.
//! let _ = fgf::Elem::<fgf::Binary<8, fgf::Normal<0x11B, 1>>>::from_raw(1);
//! ```

use super::description::{BinaryDescription, ByteLogExp};
use super::poly::Polynomial;
use super::{BinaryRepr, private};

/// A normal-basis presentation over `Polynomial<P>` generated by `E`.
///
/// `E` is a raw element of `Polynomial<P>`; bit `i` of the basis coordinates
/// selects `E^(2^i)`.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Default, PartialOrd, Ord)]
pub struct Normal<const P: u128, const E: u8>;

impl<const P: u128, const E: u8> private::Sealed for Normal<P, E> {}

/// Conjugate powers of `E` in `Polynomial<P>` coordinates: `to_base[i]` is
/// `E^(2^i)`, with unused slots zero.
pub(crate) const fn to_base<const P: u128, const E: u8, const N: u8>() -> [u8; 8] {
    let desc = BinaryDescription::polynomial(N, P);
    let mut cols = [0u8; 8];
    let mut power = E as u64;
    let mut i = 0;
    while i < N as usize {
        #[allow(clippy::cast_possible_truncation)]
        let byte = power as u8;
        cols[i] = byte;
        power = desc.mul(power, power);
        i += 1;
    }
    cols
}

/// Inverse columns of a forward map by bounded enumeration.
///
/// For each polynomial basis vector `1 << j`, the unique basis word mapping
/// to it; the caller guarantees the map is bijective, so the search
/// terminates.
pub(crate) const fn inverse_columns(forward: [u8; 8], n: u8) -> [u8; 8] {
    let mut inverse = [0u8; 8];
    let mut j = 0;
    while j < n as usize {
        let target = 1u64 << j;
        let mut w = 0u64;
        loop {
            assert!(w < (1u64 << n), "basis map is not bijective");
            let mut image = 0u64;
            let mut i = 0;
            while i < 8 {
                if (w >> i) & 1 == 1 {
                    image ^= forward[i] as u64;
                }
                i += 1;
            }
            if image == target {
                #[allow(clippy::cast_possible_truncation)]
                let byte = w as u8;
                inverse[j] = byte;
                break;
            }
            w += 1;
        }
        j += 1;
    }
    inverse
}

macro_rules! normal_row {
    ($n:literal) => {
        impl<const P: u128, const E: u8> BinaryRepr<$n> for Normal<P, E> {
            const NAME: &'static str = "normal";
            const DESCRIPTION: &'static BinaryDescription = &BinaryDescription::append_basis(
                &BinaryDescription::polynomial($n, P),
                to_base::<P, E, $n>(),
                inverse_columns(to_base::<P, E, $n>(), $n),
            );
            const LOG_EXP: Option<&'static ByteLogExp> = None;
            const VALID: () = {
                assert!((E as u64) < (1u64 << $n), "normal element has excess bits");
                <Self as BinaryRepr<$n>>::DESCRIPTION.validate();
                assert!(
                    <Self as BinaryRepr<$n>>::DESCRIPTION.one() == (1u64 << $n) - 1,
                    "normal basis one is all bits set"
                );
            };
        }
    };
}

normal_row!(2);
normal_row!(4);

/// Transport the polynomial generator of `P` into basis coordinates.
pub(crate) const fn transported_generator<const P: u128, const E: u8, const N: u8>() -> u64 {
    let poly_desc = BinaryDescription::polynomial(N, P);
    let poly_gen = Polynomial::<P>::smallest_generator(&poly_desc);
    let from = inverse_columns(to_base::<P, E, N>(), N);
    let mut image = 0u64;
    let mut i = 0;
    while i < 8 {
        if (poly_gen >> i) & 1 == 1 {
            image ^= from[i] as u64;
        }
        i += 1;
    }
    image
}

use super::super::HasGenerator;
use super::Binary;

impl<const P: u128, const E: u8> HasGenerator for Binary<2, Normal<P, E>> {
    const GENERATOR_RAW: u8 = {
        let g = transported_generator::<P, E, 2>();
        assert!(
            <Normal<P, E> as BinaryRepr<2>>::DESCRIPTION.is_generator(g),
            "basis generator does not have full order"
        );
        #[allow(clippy::cast_possible_truncation)]
        let generator = g as u8;
        generator
    };
}

impl<const P: u128, const E: u8> HasGenerator for Binary<4, Normal<P, E>> {
    const GENERATOR_RAW: u8 = {
        let g = transported_generator::<P, E, 4>();
        assert!(
            <Normal<P, E> as BinaryRepr<4>>::DESCRIPTION.is_generator(g),
            "basis generator does not have full order"
        );
        #[allow(clippy::cast_possible_truncation)]
        let generator = g as u8;
        generator
    };
}

impl<const P: u128, const E: u8> HasGenerator for Binary<8, Normal<P, E>> {
    const GENERATOR_RAW: u8 = {
        let g = transported_generator::<P, E, 8>();
        assert!(
            <Normal<P, E> as BinaryRepr<8>>::DESCRIPTION.is_generator(g),
            "basis generator does not have full order"
        );
        #[allow(clippy::cast_possible_truncation)]
        let generator = g as u8;
        generator
    };
}

impl<const P: u128, const E: u8> BinaryRepr<8> for Normal<P, E> {
    const NAME: &'static str = "normal";
    const DESCRIPTION: &'static BinaryDescription = &BinaryDescription::append_basis(
        &BinaryDescription::polynomial(8, P),
        to_base::<P, E, 8>(),
        inverse_columns(to_base::<P, E, 8>(), 8),
    );
    const LOG_EXP: Option<&'static ByteLogExp> = Some(&ByteLogExp::build(
        &BinaryDescription::append_basis(
            &BinaryDescription::polynomial(8, P),
            to_base::<P, E, 8>(),
            inverse_columns(to_base::<P, E, 8>(), 8),
        ),
        {
            let poly_desc = BinaryDescription::polynomial(8, P);
            let poly_gen = Polynomial::<P>::smallest_generator(&poly_desc);
            let mut image = 0u64;
            let mut i = 0;
            let from = inverse_columns(to_base::<P, E, 8>(), 8);
            while i < 8 {
                if (poly_gen >> i) & 1 == 1 {
                    image ^= from[i] as u64;
                }
                i += 1;
            }
            image
        },
    ));
    const VALID: () = {
        <Self as BinaryRepr<8>>::DESCRIPTION.validate();
        assert!(
            <Self as BinaryRepr<8>>::DESCRIPTION.one() == 0xFF,
            "normal basis one is all bits set"
        );
        assert!(
            <Self as BinaryRepr<8>>::DESCRIPTION.is_generator({
                let poly_desc = BinaryDescription::polynomial(8, P);
                let poly_gen = Polynomial::<P>::smallest_generator(&poly_desc);
                let mut image = 0u64;
                let mut i = 0;
                let from = inverse_columns(to_base::<P, E, 8>(), 8);
                while i < 8 {
                    if (poly_gen >> i) & 1 == 1 {
                        image ^= from[i] as u64;
                    }
                    i += 1;
                }
                image
            }),
            "basis generator does not have full order"
        );
    };
}

#[cfg(test)]
mod tests {
    use core::hint::black_box;

    use super::super::poly::tests::{apply_columns, oracle_mul, oracle_smallest_generator};
    use super::*;

    /// The conjugate columns, the inverse columns, and the transported
    /// generator of one normal basis, evaluated at runtime against the
    /// shift-reduce oracle.
    fn check_normal(poly: u128, n: u32, e: u8, forward: [u8; 8], generator: u64) {
        let mut conjugate = u64::from(e);
        for (i, &column) in forward.iter().enumerate() {
            if i < n as usize {
                assert_eq!(u64::from(column), conjugate, "E^(2^{i}) over {poly:#x}");
                conjugate = oracle_mul(poly, n, conjugate, conjugate);
            } else {
                assert_eq!(column, 0, "unused column {i} over {poly:#x}");
            }
        }
        assert_eq!(conjugate, u64::from(e), "E^(2^n) returns to E");
        #[allow(clippy::cast_possible_truncation)]
        let inverse = inverse_columns(black_box(forward), black_box(n as u8));
        for word in 0..1u64 << n {
            assert_eq!(
                apply_columns(inverse, apply_columns(forward, word)),
                word,
                "inverse after forward over {poly:#x}"
            );
        }
        assert_eq!(
            apply_columns(forward, generator),
            oracle_smallest_generator(poly, n),
            "transported generator over {poly:#x}"
        );
    }

    #[test]
    fn conjugate_columns_invert_and_transport_the_generator() {
        check_normal(
            0x7,
            2,
            2,
            to_base::<0x7, 2, 2>(),
            transported_generator::<0x7, 2, 2>(),
        );
        check_normal(
            0x13,
            4,
            8,
            to_base::<0x13, 8, 4>(),
            transported_generator::<0x13, 8, 4>(),
        );
        check_normal(
            0x11B,
            8,
            0x20,
            to_base::<0x11B, 0x20, 8>(),
            transported_generator::<0x11B, 0x20, 8>(),
        );
        check_normal(
            0x11D,
            8,
            0x20,
            to_base::<0x11D, 0x20, 8>(),
            transported_generator::<0x11D, 0x20, 8>(),
        );
    }

    /// Column inversion recovers an arbitrary invertible map, not only a
    /// conjugate basis: a unit triangular byte matrix.
    #[test]
    fn inverse_columns_invert_a_triangular_map() {
        let forward = [0x01, 0x03, 0x05, 0x0F, 0x11, 0x33, 0x55, 0xFF];
        let inverse = inverse_columns(black_box(forward), black_box(8));
        for word in 0..=0xFFu64 {
            assert_eq!(apply_columns(inverse, apply_columns(forward, word)), word);
            assert_eq!(apply_columns(forward, apply_columns(inverse, word)), word);
        }
    }

    #[test]
    #[should_panic(expected = "not bijective")]
    fn inverse_columns_reject_a_singular_map() {
        let _ = inverse_columns(black_box([0x3, 0x3, 0, 0, 0, 0, 0, 0]), black_box(2));
    }
}