Polynomial engine¶

Ren's core object is a polynomial over an RNS quotient ring. User code works with Poly, while the compiler/runtime lowers Node graphs into scheduled kernels and executable units.

Poly API
  -> Node DAG
  -> rewrite and scheduling passes
  -> scheduled kernels
  -> memory plan
  -> backend execution

Rings¶

A RingSpec describes a ring:

R_q = Z_q[X] / (X^n + 1)
q = q_0 * q_1 * ... * q_k

In code, RingSpec exposes:

Field	Meaning
`n`	Number of coefficients in each polynomial. Ren reduces polynomials modulo \(X^n + 1\). Must be a positive power of two.
`moduli`	RNS primes that make up the active modulus basis.
`dtype`	Unsigned integer dtype for the physical encoded coefficient storage, such as `uint32` or `uint64`.
`q`	Derived product of `moduli`; callers do not pass it to the constructor.

Each modulus must be compatible with the NTT shape. The constructor checks the degree, dtype, modulus size, pairwise coprimality, and the 1 mod 2n condition.

RNS limbs and Montgomery storage¶

Coefficient data is stored prime-major:

[
  coeffs mod q_0,
  coeffs mod q_1,
  ...
  coeffs mod q_k,
]

Ren Montgomery-encodes each limb row before it goes into a buffer. Raw buffer bytes are not ordinary integer coefficients. Use tolist() or to_centered_list() when you want decoded coefficients.

Domains¶

Ren represents polynomials over a ring in either coefficient domain or NTT domain:

Domain	Meaning	Typical use
`Domain.COEFF`	Coefficients in the polynomial basis.	Rescale, coefficient reads, serialization.
`Domain.NTT`	Values after the negacyclic NTT.	Multiplication and rotation-heavy paths.

The graph tracks domain through AS_RING metadata and conversion nodes. Callers do not need to insert each conversion; the scheduler injects NTT and INTT nodes where an operation requires a different domain.

Nodes¶

A Node has:

Field	Meaning
`op`	Operation, such as `ADD`, `MUL`, `NTT`, `RESCALE`, `STORE`.
`dtype`	Element dtype.
`src`	Source nodes.
`arg`	Op-specific payload.

Nodes form a DAG. Reused expressions can share producers, and Ren caches structurally identical nodes.

Constants¶

Poly.const(value, ring) creates a symbolic constant. It does not allocate a dense RNS buffer immediately. Late lowering gives constants their polynomial meaning:

in coefficient domain, the value sits in coefficient zero and every other coefficient is zero;
in NTT domain, the value broadcasts across every NTT slot.

The scheduler lowers constants after it knows the ring and domain of the surrounding computation.

For raw Poly arithmetic, x + 1 means x + Poly.const(1, x.ring). In coefficient domain that is the degree-zero polynomial [1, 0, 0, ...], not a per-coefficient offset [1, 1, 1, ...]. Build an explicit Poly from dense coefficients when every coefficient should change.

Views¶

Ren implements some ring changes as views. If a destination basis is a contiguous subset of a source basis and the layout/domain constraints allow it, TO_RING can become a BUFFER_VIEW over the same storage. If the view feeds elementwise compute, the scheduler can also fuse the view offset into indexed loads.

Use this rule of thumb:

eligible contiguous subset of moduli -> view
new, non-contiguous, or incompatible layout -> conversion/materialization

Engine overview maps where Poly sits in the execution path.
Execution pipeline explains how these graph pieces become scheduled backend work.
Scheduling gives the pass order and trace hook.
Runtime explains memory planning, backend lowering, copies, views, and JIT replay.