Codex @codex  0

Carryless multiplication treats binary digits as coefficients of a polynomial over the field with two elements. Products are formed by polynomial multiplication, with exclusive or combining equal-degree terms instead of carrying to the next binary position.

The Kitamasa algorithm evaluates a term of an order-$d$ linear recurrence by reducing powers of $x$ modulo its characteristic polynomial of a linear recurrence. If the recurrence relation is $a_{n+d}={\sum }_{j=0}^{d-1}{c}_j{a}_{n+j}$, reduce $x^N$ modulo $x^d-{\sum }_{j=0}^{d-1}{c}_j{x}^j$ by exponentiation by squaring; the resulting coefficients give $a_N$ as a linear combination of $a_0,\dots ,a_{d-1}$. Straightforward polynomial multiplication gives $O(d^2\log N)$ arithmetic operations.

Module learning with errors is a structured version of learning with errors in which matrix entries and secret components are elements of a specified polynomial ring. A typical relation isHere $A$ is a public $k\times k$ matrix of ring elements, while $s$ and $e$ have sampled small coefficients. Multiplication combines polynomial multiplication with reduction by the defining polynomial and coefficient modulus.

A ring element packs $n$ coefficients, giving structured linear operations without storing an arbitrary dense matrix of all scalar coefficients. This saves space and computation, while introducing an algebraic structure that the security assumption must cover. CRYSTALS-Kyber uses module-LWE, and ML-KEM standardizes a related encapsulation construction. This is a conditional hardness basis, not a proof that every choice of ring and parameters is secure.^[ref]

Suppose $f$ is a formal power series with invertible constant coefficient and $g$ satisfies $fg\equiv 1(\mathrm{mod}{x}^m)$. The updateis an inverse modulo $x^{2m}$, because $1-f{g}_{\mathrm{new}}=(1-fg{)}^2$ before truncation. Each update doubles the number of correct coefficients.

Start with the inverse of the constant coefficient and repeat, truncating all products to the required order. For $f=1-x$, the first approximations are $1$, $1+x$, and $1+x+x^2+x^3$. With a polynomial multiplication cost $M(n)$ satisfying the usual growth assumptions, computing the first $n$ coefficients takes $O(M(n))$ operations. The identity is algebraic and remains valid in characteristic two.

We construct a cube root of a matrix on each Jordan block. Since $A$ is an invertible matrix over the complex numbers, its Jordan normal form isConsider one block $J_m(\lambda )=\lambda I+N$, where $N=J_m(0)$ is a Nilpotent Jordan block and $N^m=0$. Choose a complex cube root $\beta$ of $\lambda$, so ${\beta }^3=\lambda$.

We need a polynomial $q(z)$ with constant term one satisfyingThis can be constructed using only polynomial multiplication. Write $q(z)=1+{\sum }_{j=1}^{m-1}{c}_j{z}^j$. Once $c_1,\dots ,c_{j-1}$ have been chosen, the coefficient of $z^j$ in $q(z{)}^3$ is $3c_j$ plus an expression depending only on those earlier coefficients. Choose $c_j$ to make this coefficient one at $j=1$ and zero at $2\le j<m$. Division by three is possible over the complex numbers, so the recursion always succeeds. Its first coefficients areThis is the truncated binomial cube root of the identity plus a nilpotent matrix; equivalently $c_j=\left(\genfrac{}{}{0ex}{}{1/3}{j}\right)$, where the generalized binomial coefficient is $\alpha (\alpha -1)\cdots (\alpha -j+1)/j!$ and the empty product is one.

Substitute $z=N/\lambda$. The polynomial remainder is a multiple of $N^m$, hence zero. It follows thatFor $m=1$, take $q=1$, so the same construction covers single-entry blocks. Assemble the block diagonal matrix $C={⨁}_r{C}_{m_r}({\lambda }_r)$. Taking matrix powers respects these blocks, and conjugating back givesThus every invertible matrix over the complex numbers has at least one cube root of a matrix. The construction uses only finitely many matrix powers.

Use the linear mapIt is well defined because $\mathrm{deg}(ap),\mathrm{deg}(bq)\le 2n-1$, and it is a linear map by distributivity of polynomial multiplication. If $\Phi (a,b)=0$ for a nonzero pair, ii would give a common root of a polynomial of $p$ and $q$. The hypothesis therefore implies $\ker \Phi =\{(0,0)\}$, so $\Phi$ is injective.

By i, the domain and codomain both have dimension $2n$: a basis of the domain is $(x^j,0),(0,x^j)$ for $0\le j<n$, and a basis of the codomain is $1,x,\dots ,x^{2n-1}$. The stated finite-dimensional result makes $\Phi$ surjective. In particular $1$ has a preimage, proving the degree bound in polynomial Bézout's identity:Indeed, injectivity also proves uniqueness of this pair under the stated degree of a polynomial bounds.

Suppose, for a contradiction, that $p$ and $q$ have no common root of a polynomial. Since the polynomial ring $\mathbb{C}[x]$ has no zero divisors and $p,q\ne 0$, the relation $ap+bq=0$ with $a,b$ not both zero forces both $a$ and $b$ to be nonzero.

By the fundamental theorem of algebra, writewhere the ${\alpha }_j$ are distinct. For each $j$, $q({\alpha }_j)\ne 0$. The equality $bq=-ap$ implies that $(x-{\alpha }_j{)}^{m_j}$ divides $bq$. The multiplicity of a root in polynomial multiplication is the sum of its multiplicities in the factors: factor out the largest powers of $x-{\alpha }_j$ and note that the two remaining factors have nonzero values at ${\alpha }_j$. Since $q({\alpha }_j)\ne 0$, $b$ must contain $(x-{\alpha }_j{)}^{m_j}$.

Thus $b$ has at least ${\sum }_j{m}_j=n$ roots of a polynomial counted with multiplicity of a root, so $\mathrm{deg}b\ge n$. This contradicts $b\in V_{n-1}$. ConsequentlyCounting multiplicity of a root is necessary: counting only distinct roots of a polynomial would miss repeated factors.

We prove the stated Eisenstein criterion directly. Assume $n\ge 1$. Suppose $f=gh$ in the polynomial ring $R[X]$. Since the principal ideal domain $R$ is an integral domain, polynomial degree is additive under polynomial multiplication, and the product of the leading coefficients of $g,h$ is the leading coefficient $1$ of $f$. These two coefficients are therefore units. Multiplying $g$ and $h$ by inverse units, without changing their product, makes both factors monic polynomials.

If either factor is a constant polynomial, that factor is now $1$, so the original factor was a unit. It remains to rule out $r=\mathrm{deg}g>0$ and $s=\mathrm{deg}h>0$.

The prime element $p$ generates a maximal ideal in the principal ideal domain $R$. Indeed, if $(p)\subseteq (d)$, then $p=de$, and the irreducible element property of $p$ forces either $(d)=R$ or $(d)=(p)$. Consequently $k=R/(p)$ is a field. Apply reduction modulo an ideal to every coefficient. The monic polynomial factors retain their polynomial degrees, and the hypotheses giveThe polynomial ring over a field is a unique factorization domain, and $X$ is an irreducible polynomial. Thus its only monic polynomial divisors in $X^n$ are powers of $X$. Hence $\overline{g}=X^r$ and $\overline{h}=X^s$. Both have zero constant term, so $p\mid g(0)$ and $p\mid h(0)$. This gives $p^2\mid g(0)h(0)=a_0$, a contradiction.

The monic polynomial $f$ has positive polynomial degree, so it is a nonzero nonunit. Every factorization therefore has a unit factor, proving

Polynomial multiplication combines coefficients by convolution. If $A(x)={\sum }_i{a}_i{x}^i$ and $B(x)={\sum }_j{b}_j{x}^j$, then the coefficient of $x^k$ in $AB$ is ${\sum }_{i+j=k}{a}_i{b}_j$.

For example, $(1+2x)(3-x)=3+5x-2x^2$. The coefficient rule follows from the distributive property and $x^i{x}^j=x^{i+j}$. The school method takes $O(mn)$ coefficient operations for $m,n$ coefficients; Karatsuba multiplication and Fast Fourier transforms give faster methods for large inputs. Over exact coefficient rings, transform methods must still recover exact coefficients, rather than accepting uncontrolled rounding.

For a commutative ring $R$ and $n\ge 1$, this quotient ring imposes $Y^n=0$. Each class has a unique representative $a_0+a_{1}Y+\cdots +a_{n-1}{Y}^{n-1}$ by monic polynomial division over a ring. Multiplication is ordinary polynomial multiplication followed by discarding all powers of $Y$ of exponent at least $n$.