fhelium.engine.ntt.plans.twiddles

Canonical negacyclic NTT root and compact-twiddle construction.

build_compact_twiddles

function View source

def build_compact_twiddles(moduli: Iterable[int], log_ring_dimension: int, dtype: torch.dtype, *, device: torch.device) -> tuple[torch.Tensor, torch.Tensor]: ...

Build canonical bit-reversed forward and inverse rows per prime.

These [prime, coefficient] rows are the mathematical source shared by compact kernels and by indexed-plan expansion. They do not encode a grouped execution policy.

For row i with primitive $2N$-th root ${\psi }_i$, column k stores ${\psi }_i^{\mathrm{br}(k)}mod{q}_i$ for forward execution and its inverse for inverse execution. Rows follow the input moduli order exactly. Outputs use dtype on device in standard representation; callers convert the tables to Montgomery form before CUDA NTT.

expand_stage_twiddles

function View source

def expand_stage_twiddles(compact_twiddles: torch.Tensor, twiddle_indices: torch.Tensor) -> torch.Tensor: ...

Gather standard twiddles into [prime, stage, butterfly].

The functional result follows the prime rows, dtype, and device of compact_twiddles and does not alias either input.

build_power_of_two_radix_twiddles

function View source

def build_power_of_two_radix_twiddles(moduli: Iterable[int], log_ring_dimension: int, radix: int, dtype: torch.dtype, *, device: torch.device) -> tuple[torch.Tensor, torch.Tensor, torch.Tensor, torch.Tensor]: ...

Build genuine power-of-two radix outer twists and cyclic-root powers.

The returned direction-specific outer tables have shape [prime, N-1]. Each digit is represented as a twisted cyclic radix-4/8/16 transform, rather than as a list of radix-2 stage twiddles. Root-power tables have shape [prime, radix] and contain powers of the fixed primitive radix root used by the digit-local butterfly.

Rows map exactly to the input moduli order. Every returned tensor uses integral dtype on device and standard residues; the runtime later converts all four tables to Montgomery representation in place.