logicaffeine_proof/
macaulay.rs

1//! Monomials and the Macaulay matrix — the combinatorial skeleton of the XL algorithm.
2//!
3//! XL ("eXtended Linearization", Courtois–Klimov–Patarin–Shamir 2000) solves a system of
4//! multivariate polynomial equations by *linearizing*: multiply every equation by every
5//! monomial up to a chosen degree, treat each distinct monomial as an independent unknown,
6//! and solve the resulting linear system. This is the engine behind Gröbner-basis-style
7//! algebraic cryptanalysis of multivariate schemes (Rainbow / Oil-and-Vinegar / HFE) — the
8//! attack surface Prof. Ding formalized through the *degree of regularity*.
9//!
10//! This module owns only the field-agnostic bookkeeping: how monomials are represented,
11//! enumerated up to a degree bound, and multiplied. The field arithmetic and the linear
12//! solve live in [`crate::xl`].
13//!
14//! A monomial is the **sorted multiset of its variable indices** — `[]` is the constant `1`,
15//! `[i]` is `x_i`, `[i, i]` is `x_i²`, `[i, j]` (i ≤ j) is `x_i x_j`. The degree is the length.
16//! In a multilinear ring (GF(2), where `x² = x`) monomials are squarefree (strictly
17//! increasing); otherwise repeats encode true exponents.
18
19/// A monomial: the sorted multiset of variable indices it contains. `Vec::new()` is `1`.
20pub type Monomial = Vec<u32>;
21
22/// The constant monomial `1`.
23pub fn one() -> Monomial {
24    Vec::new()
25}
26
27/// The degree of a monomial (its total number of variable factors).
28pub fn degree(m: &Monomial) -> usize {
29    m.len()
30}
31
32/// The product of two monomials. When `multilinear`, repeated variables collapse (`x² = x`),
33/// the correct rule for GF(2); otherwise exponents accumulate.
34pub fn mul(a: &Monomial, b: &Monomial, multilinear: bool) -> Monomial {
35    let mut m: Monomial = a.iter().chain(b.iter()).copied().collect();
36    m.sort_unstable();
37    if multilinear {
38        m.dedup();
39    }
40    m
41}
42
43/// Every monomial in `n` variables of degree exactly `deg`, listed with variable indices in
44/// nondecreasing order. Strictly increasing (squarefree) when `multilinear`.
45pub fn monomials_of_degree(n: u32, deg: usize, multilinear: bool) -> Vec<Monomial> {
46    fn rec(
47        start: u32,
48        n: u32,
49        remaining: usize,
50        multilinear: bool,
51        cur: &mut Monomial,
52        out: &mut Vec<Monomial>,
53    ) {
54        if remaining == 0 {
55            out.push(cur.clone());
56            return;
57        }
58        for v in start..n {
59            cur.push(v);
60            let next = if multilinear { v + 1 } else { v };
61            rec(next, n, remaining - 1, multilinear, cur, out);
62            cur.pop();
63        }
64    }
65    let mut out = Vec::new();
66    let mut cur = Vec::new();
67    rec(0, n, deg, multilinear, &mut cur, &mut out);
68    out
69}
70
71/// Every monomial in `n` variables of degree `0..=max_deg`. The constant `1` is always first
72/// (index `0`), which the XL solver relies on to read off constant terms.
73pub fn monomials_up_to_degree(n: u32, max_deg: usize, multilinear: bool) -> Vec<Monomial> {
74    let mut out = vec![one()];
75    for deg in 1..=max_deg {
76        out.extend(monomials_of_degree(n, deg, multilinear));
77    }
78    out
79}
80
81#[cfg(test)]
82#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/macaulay/tests.rs"]
83mod tests;
logicaffeine_proof/macaulay.rs

logicaffeine_proof/
macaulay.rs
