claimroutineinferred_dep
CRT address map via controlled shifts
CRT address map costs via controlled shifts
turns length- convolution into a -dimensional one
Claim·§9.3 An explicit cyclic-convolution layout·inside thmInteger multiplication in O(n (lg n)^{1-κ}) time
Statement (paper)
The map , , is an algebra isomorphism and so preserves cyclic convolution. On mixed-radix indices it sends to the monomial with coordinates . Padding insertion, the triangular prefix-controlled cyclic shifts for (each a bijection of the padded box preserving the valid box and zero padding, and explicitly invertible), the axis reorders and the deletion scan together compute and its inverse, with padding operations, in total cost .
In plain English
The substitution is an algebra isomorphism from onto the multidimensional cyclic-convolution algebra with side lengths , so it preserves cyclic convolution. It sends a mixed-radix index to coordinates , and both it and its inverse, with padding handling, can be computed in total cost .
Why it's here
This turns the length- cyclic convolution into a -dimensional one over the distinct primes from the previous claim, giving a concrete layout for the tensor transforms. The address change is realized as triangular prefix-controlled cyclic shifts, each a linear-time affine update by the affine-stream lemma, plus axis reorders by the chunk-swap lemma, and each step is invertible and respects the padding. The algorithm's normalization bookkeeping and the cost table use this to charge the address conversion at the stated cost.
Classified routine:
The isomorphism is the classical CRT/Good–Thomas (Agarwal–Cooley) prime-factor reindexing of a cyclic convolution into a multidimensional one, as used in Harvey–van der Hoeven's n log n algorithm. The Turing-machine realization via controlled shifts is cost bookkeeping built on the paper's affine-stream and chunk-swap lemmas.