p3-binary-field 0.8.0

//! Lookup tables for the tower's `GF(2^8)`.
//!
//! The multiplicative group of `GF(2^8)` is cyclic of order `255`, generated by
//! [`BinaryField8::GENERATOR`]. Writing every nonzero element as `g^e`, a product is a sum of
//! exponents, so a multiplication is two [`LOG`] lookups, an addition and one [`EXP`] lookup,
//! while squaring and inversion use direct unary tables.
//!
//! `LOG` and `EXP` are pinned constants; `regenerate_tables` in the test module below derives them
//! from [`BinaryField8::reference_mul`] and checks them against what is written here.
//!
//! [`BinaryField8::GENERATOR`]: crate::BinaryField8
//! [`BinaryField8::reference_mul`]: crate::BinaryField8::reference_mul

/// `LOG[x]` is the exponent `e < 255` with `GENERATOR^e = x`, for every nonzero `x`.
///
/// `LOG[0]` is a sentinel rather than a logarithm: zero is not a power of the generator. Its
/// value keeps every index the routines below form inside [`EXP`], so they can look up
/// unconditionally and discard the meaningless result with a mask.
#[rustfmt::skip]
pub(crate) const LOG: [u8; 256] = [
      0,   0, 170,  85, 204, 187,  51, 238, 119, 153, 102, 221,  34, 136,  68,  17,
    210, 207, 141,   1,  45, 252, 216,  16, 157,  83, 110,  78, 217,  53, 230, 228,
    125, 171, 122,  56, 132, 143, 223, 145, 215, 186, 167, 131,  72, 248, 253,  25,
     40, 226,  86,  37, 242, 195, 163, 168,  47,  60,  58, 138, 130,  46, 101,  82,
    159, 165,  27,   2, 156, 220,  59, 166,  90, 249,  32, 177, 205, 201, 106, 179,
    142, 162, 203,  15, 160, 139,  89, 148, 184,  10,  73, 149,  42, 232, 240, 188,
      6,  96, 208,  13, 134, 104,   3,  48,  26, 161,  12, 192,  67,  52,  24, 129,
    193, 211, 235,  93,  61,  28, 213, 190,  36, 124, 140, 254, 199,  66, 239, 200,
     74, 172,  80, 197, 120,  94, 116,  21,  71,  81, 135, 229,   5,  92, 164, 202,
    108,   8, 126, 150, 114, 115, 236, 154, 231, 105, 198, 128, 206, 169,  39,  55,
     57, 185,  77, 118, 212, 103, 147, 155,  75,  63,  54,   4,  99,  64, 180, 243,
    176, 183,  11, 123, 237,  44, 222, 194,  49, 218,  19, 173, 196, 107,  76, 182,
    244, 112,  87, 250, 175, 117,   7,  79,  35, 191,   9,  31, 241, 144, 251,  50,
     91,  38,  98, 181, 111,  97,  22, 246, 152, 109, 214, 137, 219,  88, 133, 189,
     23,  65, 178,  41, 121, 225,  84, 209,  29,  69,  30, 151, 146,  43,  20, 113,
    227,  33, 100, 247,  14, 158, 234,  95, 127,  70,  18,  62, 245, 174, 233, 224,
];

/// `EXP[e]` is `GENERATOR^(e mod 255)`.
///
/// Two periods of the cycle, so a sum of two logarithms indexes it directly rather than being
/// reduced modulo `255` first. A table of this length also covers every index a `u8` logarithm
/// can produce, which is what lets the compiler discharge the bounds checks below.
#[rustfmt::skip]
pub(crate) const EXP: [u8; 511] = [
      1,  19,  67, 102, 171, 140,  96, 198, 145, 202,  89, 178, 106,  99, 244,  83,
     23,  15, 250, 186, 238, 135, 214, 224, 110,  47, 104,  66, 117, 232, 234, 203,
     74, 241,  12, 200, 120,  51, 209, 158,  48, 227,  92, 237, 181,  20,  61,  56,
    103, 184, 207,   6, 109,  29, 170, 159,  35, 160,  58,  70,  57, 116, 251, 169,
    173, 225, 125, 108,  14, 233, 249, 136,  44,  90, 128, 168, 190, 162,  27, 199,
    130, 137,  63,  25, 230,   3,  50, 194, 221,  86,  72, 208, 141, 115, 133, 247,
     97, 213, 210, 172, 242,  62,  10, 165, 101, 153,  78, 189, 144, 217,  26, 212,
    193, 239, 148, 149, 134, 197, 163,   8, 132, 228,  34, 179, 121,  32, 146, 248,
    155, 111,  60,  43,  36, 222, 100, 138,  13, 219,  59,  85, 122,  18,  80,  37,
    205,  39, 236, 166,  87,  91, 147, 235, 216,   9, 151, 167,  68,  24, 245,  64,
     84, 105,  81,  54, 142,  65,  71,  42,  55, 157,   2,  33, 129, 187, 253, 196,
    176,  75, 226,  79, 174, 211, 191, 177,  88, 161,  41,   5,  95, 223, 119, 201,
    107, 112, 183,  53, 188, 131, 154, 124, 127,  77, 143,  82,   4,  76, 156,  17,
     98, 231,  16, 113, 164, 118, 218,  40,  22,  28, 185, 220,  69,  11, 182,  38,
    255, 229,  49, 240,  31, 139,  30, 152,  93, 254, 246, 114, 150, 180,   7, 126,
     94, 204,  52, 175, 192, 252, 215, 243,  45,  73, 195, 206,  21,  46, 123,   1,
     19,  67, 102, 171, 140,  96, 198, 145, 202,  89, 178, 106,  99, 244,  83,  23,
     15, 250, 186, 238, 135, 214, 224, 110,  47, 104,  66, 117, 232, 234, 203,  74,
    241,  12, 200, 120,  51, 209, 158,  48, 227,  92, 237, 181,  20,  61,  56, 103,
    184, 207,   6, 109,  29, 170, 159,  35, 160,  58,  70,  57, 116, 251, 169, 173,
    225, 125, 108,  14, 233, 249, 136,  44,  90, 128, 168, 190, 162,  27, 199, 130,
    137,  63,  25, 230,   3,  50, 194, 221,  86,  72, 208, 141, 115, 133, 247,  97,
    213, 210, 172, 242,  62,  10, 165, 101, 153,  78, 189, 144, 217,  26, 212, 193,
    239, 148, 149, 134, 197, 163,   8, 132, 228,  34, 179, 121,  32, 146, 248, 155,
    111,  60,  43,  36, 222, 100, 138,  13, 219,  59,  85, 122,  18,  80,  37, 205,
     39, 236, 166,  87,  91, 147, 235, 216,   9, 151, 167,  68,  24, 245,  64,  84,
    105,  81,  54, 142,  65,  71,  42,  55, 157,   2,  33, 129, 187, 253, 196, 176,
     75, 226,  79, 174, 211, 191, 177,  88, 161,  41,   5,  95, 223, 119, 201, 107,
    112, 183,  53, 188, 131, 154, 124, 127,  77, 143,  82,   4,  76, 156,  17,  98,
    231,  16, 113, 164, 118, 218,  40,  22,  28, 185, 220,  69,  11, 182,  38, 255,
    229,  49, 240,  31, 139,  30, 152,  93, 254, 246, 114, 150, 180,   7, 126,  94,
    204,  52, 175, 192, 252, 215, 243,  45,  73, 195, 206,  21,  46, 123,   1,
];

/// Direct unary tables avoid the dependent logarithm and exponential lookups.
const SQUARE: [u8; 256] = {
    let mut table = [0; 256];
    let mut i = 1;
    while i < 256 {
        table[i] = EXP[2 * LOG[i] as usize];
        i += 1;
    }
    table
};

const INVERSE: [u8; 256] = {
    let mut table = [0; 256];
    let mut i = 1;
    while i < 256 {
        table[i] = EXP[255 - LOG[i] as usize];
        i += 1;
    }
    table
};

/// The product of two `GF(2^8)` elements, in the tower representation.
#[inline]
pub(crate) const fn mul(a: u8, b: u8) -> u8 {
    let exponent = LOG[a as usize] as usize + LOG[b as usize] as usize;
    // The sentinel at `LOG[0]` is not a logarithm, so the lookup above is meaningful only when
    // both operands are nonzero. The mask is all ones exactly then, and all zeros otherwise,
    // which is the right answer for a product with zero.
    let both_nonzero = 0u8.wrapping_sub((a != 0) as u8 & (b != 0) as u8);
    EXP[exponent] & both_nonzero
}

/// The square of a `GF(2^8)` element, in the tower representation.
#[inline]
pub(crate) const fn square(a: u8) -> u8 {
    SQUARE[a as usize]
}

/// The inverse of a `GF(2^8)` element, or `None` for zero.
///
/// `g^e · g^(255 − e) = g^255 = 1`, and the exponent `255 − e` lies in `1..=255`, which
/// [`EXP`] covers.
#[inline]
pub(crate) const fn try_inverse(a: u8) -> Option<u8> {
    if a == 0 {
        None
    } else {
        Some(INVERSE[a as usize])
    }
}

#[cfg(test)]
mod tests {
    extern crate std;

    use std::println;

    use p3_field::{Field, PrimeCharacteristicRing};

    use super::*;
    use crate::BinaryField8;
    use crate::tower::TowerLevel;

    /// The tables as the powers of [`BinaryField8::GENERATOR`] define them, computed with the
    /// recursive tower product alone.
    fn derive_tables() -> ([u8; 256], [u8; 511]) {
        let mut log = [0u8; 256];
        let mut exp = [0u8; 511];

        let mut power = BinaryField8::ONE;
        for (e, slot) in exp.iter_mut().take(255).enumerate() {
            *slot = power.to_repr();
            log[power.to_repr() as usize] = e as u8;
            power = power.reference_mul(BinaryField8::GENERATOR);
        }
        assert_eq!(power, BinaryField8::ONE, "the generator has order 255");

        for e in 255..exp.len() {
            exp[e] = exp[e - 255];
        }

        (log, exp)
    }

    /// Every one of the `65_536` ordered pairs, against the recursive definition of the tower
    /// product. The tables are a rewriting of that product and must reproduce it exactly.
    #[test]
    fn the_table_product_agrees_with_the_recursive_one_on_every_pair() {
        for a in 0..=u8::MAX {
            for b in 0..=u8::MAX {
                let expected = BinaryField8::from_repr(a)
                    .reference_mul(BinaryField8::from_repr(b))
                    .to_repr();
                assert_eq!(mul(a, b), expected, "mul({a}, {b})");
            }
        }
    }

    #[test]
    fn the_table_square_agrees_with_the_recursive_product() {
        for a in 0..=u8::MAX {
            let x = BinaryField8::from_repr(a);
            assert_eq!(square(a), x.reference_mul(x).to_repr(), "square({a})");
        }
    }

    #[test]
    fn the_table_inverse_undoes_the_table_product() {
        assert_eq!(try_inverse(0), None);
        for a in 1..=u8::MAX {
            let inverse = try_inverse(a).expect("every nonzero element is invertible");
            assert_eq!(
                BinaryField8::from_repr(a).reference_mul(BinaryField8::from_repr(inverse)),
                BinaryField8::ONE,
                "inverse({a})"
            );
        }
    }

    /// `LOG` and `EXP` are inverse bijections on the nonzero elements.
    #[test]
    fn the_tables_invert_each_other() {
        for (e, &power) in EXP.iter().enumerate().take(255) {
            assert_eq!(LOG[power as usize] as usize, e, "LOG[EXP[{e}]]");
        }
        for x in 1..=u8::MAX {
            assert_eq!(EXP[LOG[x as usize] as usize], x, "EXP[LOG[{x}]]");
        }
    }

    /// The generator has full order, so its `255` powers are the `255` nonzero elements, and
    /// the second period of `EXP` repeats the first.
    #[test]
    fn the_generator_powers_enumerate_every_nonzero_element() {
        let mut seen = [false; 256];
        for (e, &power) in EXP.iter().enumerate().take(255) {
            assert_ne!(power, 0, "no power of the generator is zero");
            assert!(!seen[power as usize], "EXP[{e}] repeats an earlier power");
            seen[power as usize] = true;
        }
        assert!(seen.iter().skip(1).all(|&hit| hit));
        assert!(!seen[0]);

        for e in 255..511 {
            assert_eq!(EXP[e], EXP[e - 255], "EXP[{e}]");
        }
    }

    #[test]
    fn the_pinned_tables_match_the_derivation() {
        let (log, exp) = derive_tables();
        assert_eq!(log, LOG);
        assert_eq!(exp, EXP);
    }

    /// Prints the tables in the form they are pinned above.
    ///
    /// Run with `cargo test -p p3-binary-field --release -- --ignored --nocapture`.
    #[test]
    #[ignore = "one-off derivation used to pin the LOG and EXP tables"]
    fn regenerate_tables() {
        let (log, exp) = derive_tables();
        assert_eq!(log, LOG);
        assert_eq!(exp, EXP);

        for value in log {
            println!("LOG {value}");
        }
        for value in exp {
            println!("EXP {value}");
        }
    }
}