Concept icon
Concept

Representing the extended truncated coefficient ring at finite precision

Use A=O[V]/(V^ell) and A_p=A/(2^p). Store e times ell coordinates, each as an integer residue from zero to 2^p-1. Multiply by polynomial convolution, reduce powers of U using the monic f, and discard V powers of degree at least ell. Storage is e ell p bits and arithmetic is polynomial in these dimensions. Divisibility is coordinatewise; A_p need not be a field because V is nilpotent. Original B_(p,ell) entries occupy only the constant U coordinate. A sum of products of those original entries remains in that subring, even if the algorithm uses the extension for intermediate calculations.

0

1

Concept icon
Updated 2026-11-08

Contributors are:

Who are from:

Tags

Math