Module rns 

Level 0 — ℤ. RNS integers and the core CRT reconstruction.

Representation

A number lives as a tuple of residues, one per prime channel. By the Chinese Remainder Theorem any integer in [0, M) (where M = ∏ moduli) is uniquely identified by its residue tuple. We use the symmetric residue system: residues are stored in [0, m), and on reconstruction a value U with 2U > M is interpreted as the negative number U - M. This lets the signed range be (-M/2, M/2) while keeping per-channel arithmetic a pure modular op — exactly the property that makes RNS embarrassingly parallel.

CPU vs GPU

Single RnsInt operations parallelize over channels with rayon only when k >= RAYON_CHANNEL_THRESHOLD; below that the task overhead dominates and we stay sequential. For batches of RnsInt, always go through crate::backend::executor, which auto-selects CPU rayon or the GPU based on the batch size. Never call a backend directly from the math layers.

Structs

Channels

A shared, immutable set of pairwise-coprime moduli (the RNS “channels”).

RnsInt

An exact integer in RNS form (Level 0 of the tower).

Constants

MAX_SAFE_MODULUS

Largest modulus for which (a*b) fits in u32 on the GPU (< 2^16).

Functions

garner_crt

Garner’s algorithm: reconstruct the unsigned integer in [0, M) from its residues. Never materializes the large basis elements M/m_i; all intermediates stay small (each fits within its own modulus).

gpu_add_channel

Reference implementation of one GPU thread’s add: (a + b) % m.

gpu_mul_channel

Reference implementation of one GPU thread’s multiply: (a * b) % m.