Skip to main content

maximal_order_complexity_of_bytes

Function maximal_order_complexity_of_bytes 

Source
pub fn maximal_order_complexity_of_bytes(data: &[u8]) -> usize
Expand description

The maximal order complexity of a byte string (its LSB-first bit expansion) — the length of the shortest feedback register, LINEAR OR NONLINEAR, generating it. The TOP of the FSR hierarchy: it catches nonlinear generators (NFSRs, algebraic combiners) that fool every linear-complexity measure. Low relative to the bit count ⇒ a short-register generator. This is the last cheap rung — a general nonlinear feedback function is a full truth table (as large as the data), so a low MOC is a certified STRUCTURAL weakness (a short register exists) even though recovering its sparse form is the (hard) algebraic attack. For a real cipher MOC ≈ n/2: the incompressible residue, the Chaitin ceiling.