# 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 calls and executable units.

```text
Poly API
  -> Node DAG
  -> rewrite and scheduling passes
  -> scheduled calls
  -> memory plan
  -> backend execution
```

## Rings

A `RingSpec` describes a ring:

```text
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:

```text
[
  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:

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

## Related pages

- [Engine overview](<https://ren-docs.pages.dev/engine/overview/index.md>) maps where `Poly` sits in the execution path.
- [Execution pipeline](<https://ren-docs.pages.dev/engine/execution/index.md>) explains how these graph pieces become scheduled backend work.
- [Scheduling](<https://ren-docs.pages.dev/engine/scheduling/index.md>) gives the pass order and trace hook.
- [Runtime](<https://ren-docs.pages.dev/engine/runtime/index.md>) explains memory planning, backend lowering, copies, views, and JIT replay.
