nc-polynomial 0.2.0

Polynomial arithmetic over Z_q[x] with NTT support and validated ring contexts
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

# nc-polynomial

[![Crates.io](https://img.shields.io/crates/v/nc-polynomial.svg)](https://crates.io/crates/nc-polynomial)

Polynomial arithmetic over `Z_q[x]` with validated ring contexts for lattice-style cryptography experiments.

## What This Crate Provides

- Dense polynomial type: `Polynomial`
- Arithmetic in `Z_q[x]`:
  - `add`, `sub`, `neg`, `scalar_mul`
  - `mul` (schoolbook), `mul_ntt`, `mul_truncated`
- Quotient-ring operations modulo a polynomial:
  - `rem_mod_poly`, `add_mod_poly`, `sub_mod_poly`, `mul_mod_poly`
- Utilities:
  - `evaluate`, `derivative`, `div_rem`
- Validated ring configuration:
  - `Params`, `RingContext`, `RingElem`

## Security Scope

This crate includes cryptography-oriented building blocks and runnable examples, but the example encryption code is educational and **not production-hardened**.

In particular, side-channel protections, serialization hardening, and operational key-management safeguards are not complete.

## Installation

Local path dependency:

```toml
[dependencies]
nc-polynomial = { path = "/path/to/polynomial" }
```

## Quick Start

### 1) Basic Polynomial Arithmetic

```rust
use nc_polynomial::Polynomial;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let a = Polynomial::new(8, 17, &[1, 2, 3])?;
    let b = Polynomial::new(8, 17, &[4, 5])?;

    let sum = a.add(&b)?;
    let product = a.mul(&b)?;

    assert_eq!(sum.trimmed_coefficients(), vec![5, 7, 3]);
    assert_eq!(product.trimmed_coefficients(), vec![4, 13, 5, 15]);
    Ok(())
}
```

### 2) Use a Validated Ring Context (`R_q = Z_q[x]/(f(x))`)

```rust
use nc_polynomial::RingContext;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // f(x) = x^32 + 1
    let mut modulus_poly = vec![0_u64; 33];
    modulus_poly[0] = 1;
    modulus_poly[32] = 1;

    let ctx = RingContext::from_parts(32, 998_244_353, &modulus_poly, 3)?;

    let a = ctx.element(&[1, 2, 3])?;
    let b = ctx.element(&[4, 5, 6])?;

    let c = a.mul(&b)?;
    println!("{:?}", c.trimmed_coefficients());
    Ok(())
}
```

## Project Layout

- `src/lib.rs`: crate exports
- `src/polynomial.rs`: core polynomial arithmetic and tests
- `src/params.rs`: `Params`, `RingContext`, `RingElem`
- `benches/multiplication_speed.rs`: schoolbook vs NTT benchmark
- `examples/`: runnable Rust examples
  - `examples/helpers_sampling.rs`
  - `examples/helpers_codec.rs`
  - `examples/rlwe_pke.rs`
  - shared example code under `examples/common/`

## Run Examples

```bash
cargo run --example helpers_sampling
cargo run --example helpers_codec
cargo run --example rlwe_pke
```

## Tests and Benchmarks

```bash
# library tests
cargo test

# example tests (unit tests embedded in examples/common modules)
cargo test --examples

# check example builds
cargo check --examples

# multiplication benchmark
cargo bench --bench multiplication_speed
```

## NTT Notes

`mul_ntt` requires parameters compatible with NTT length derived from operand degrees.

Practical requirements include:

- transform length must divide `q - 1`
- provided primitive root must induce a valid root of unity for that length

If these are not satisfied, NTT-specific errors are returned.

## License

MIT, see [`LICENSE`](LICENSE).

Copyright (c) 2026 Raja Lehtihet & Wael El Oraiby.