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:

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

Quick Start

1) Basic Polynomial Arithmetic

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)))

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

cargo run --example helpers_sampling
cargo run --example helpers_codec
cargo run --example rlwe_pke

Tests and Benchmarks

# 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.

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