Concept
Storing truncated polynomials with coefficients modulo a power of two
The ring B_(p,ell)=(Z/2^p Z)[V]/(V^ell) stores ell coefficients, each as an integer residue from zero to 2^p-1. Add coefficientwise. Multiply by convolution, dropping every term of V-degree at least ell and reducing retained coefficients modulo 2^p. With p=3,ell=2, (1+2V)(3+4V) becomes 3+2V: the V coefficient ten reduces to two, and the V^2 term disappears. Storage needs p ell bits. This is not generally a field: nonzero elements can multiply to zero. For ell=1 it is ordinary arithmetic modulo 2^p. The coefficient-sum map must still be applied only after the shared truncated product.
0
1
Updated 2026-11-08
Tags
Math