A uniform polynomial-time generator for sparse binary trinomials

The generator accepts a unary half-degree and writes all coefficients of X^(2*d) + X^d + 1. Its input bit values do not matter. The certificate does not assume irreducibility and is valid uniformly at every input length.

theorem Complexity.BitPolynomial.trinomialEval_mem_FP : trinomialEval ∈ FP

Generating the sparse coefficient list is uniformly polynomial-time.

theorem Complexity.BitPolynomial.trinomialBits_mem_FP {d : List Bool → ℕ} (hd : UnaryFn d) : (fun (z : List Bool) => trinomialBits (d z)) ∈ FP

A polynomial-time unary half-degree can be used directly by the generator.

theorem Complexity.BitPolynomial.roundedTrinomialEval_mem_FP : roundedTrinomialEval ∈ FP

Rounding the requested half-degree to a power of three preserves polynomial time.