I implement a serial baseline for polynomial multiplication in (_q[X] / (X^N + 1)), which is the core operation used by CKKS homomorphic encryption.
In CKKS, ciphertext and key operations repeatedly multiply polynomials modulo several NTT-friendly primes (RNS representation). This baseline models that by computing the same negacyclic polynomial product for multiple moduli.
The goal of this assignment is not full CKKS, but a realistic core kernel that is performance-critical and has clear parallelization opportunities.
File: code/ckks_ntt_baseline.cc
Parse command-line parameters:
--logn so that (N = 2^{})--mods number of RNS moduli--reps repetition count for timing--seed deterministic random seed--verify-coeffs number of coefficients checked by a
slow referenceChoose built-in NTT primes (q) such that ((q-1)) is divisible by (2N), then build one NTT context per modulus.
For each modulus, generate random polynomials a and
b.
Compute negacyclic product with NTT:
Time the main loop (reps times over all moduli)
using std::chrono::steady_clock.
Verify correctness by comparing the first
verify-coeffs coefficients with a direct (O(N^2))
negacyclic formula (for one modulus), and print:
--reps): repetitions can be batched.Potential limits to speedup: