FallenSigh
39dd36994b
Phase 2.2: NTT-domain polynomial pointwise multiplication. - basecase_mul.v: degree-1 base-case multiply (c0,c1) with Barrett - poly_mul_zeta_rom.v: 128-entry zeta ROM for PolyMul - poly_mul_sync.v: FSM (IDLE→LOAD 256 cycles→COMPUTE 256 cycles→DONE) Verified: 5/5 vectors bit-exact vs Python PolyMul reference
46 lines
1.8 KiB
Verilog
46 lines
1.8 KiB
Verilog
// basecase_mul.v - NTT-domain degree-1 polynomial multiplication
|
|
//
|
|
// Computes pointwise product of two degree-1 NTT-domain polynomials:
|
|
// c0 = (a0*b0 + a1*b1*zeta) mod Q
|
|
// c1 = (a0*b1 + a1*b0) mod Q
|
|
//
|
|
// Uses three barrett_mul instances for modular multiplications
|
|
// and pure combinational modular addition for the final sums.
|
|
//
|
|
// All inputs/outputs are 12-bit values in [0, Q-1] where Q = 3329.
|
|
|
|
module basecase_mul (
|
|
input [11:0] a0, a1, // first polynomial: degree-0 and degree-1 coeffs
|
|
input [11:0] b0, b1, // second polynomial: degree-0 and degree-1 coeffs
|
|
input [11:0] zeta, // precomputed twiddle factor (zeta^2 * 17 mod Q)
|
|
output [11:0] c0, c1 // result polynomial coefficients
|
|
);
|
|
|
|
localparam Q = 3329;
|
|
|
|
// Barrett modular multiplication outputs
|
|
wire [11:0] t1; // a0 * b0 mod Q
|
|
wire [11:0] t2; // a1 * b1 mod Q
|
|
wire [11:0] t3; // a1 * b0 mod Q
|
|
wire [11:0] t4; // a0 * b1 mod Q
|
|
wire [11:0] t2_zeta; // (a1 * b1) * zeta mod Q
|
|
|
|
// Four Barrett multiplications for the scalar products
|
|
barrett_mul u_mul1 (.a(a0), .b(b0), .product(t1));
|
|
barrett_mul u_mul2 (.a(a1), .b(b1), .product(t2));
|
|
barrett_mul u_mul3 (.a(a1), .b(b0), .product(t3));
|
|
barrett_mul u_mul4 (.a(a0), .b(b1), .product(t4));
|
|
|
|
// Multiply t2 by zeta for the zeta term in c0
|
|
barrett_mul u_mul_zeta (.a(t2), .b(zeta), .product(t2_zeta));
|
|
|
|
// Combinational modular addition: each sum is in [0, 2Q-1)
|
|
// Subtract Q once if >= Q
|
|
wire [12:0] sum_c0 = {1'b0, t1} + {1'b0, t2_zeta};
|
|
wire [12:0] sum_c1 = {1'b0, t3} + {1'b0, t4};
|
|
|
|
assign c0 = (sum_c0 >= Q) ? sum_c0[11:0] - Q[11:0] : sum_c0[11:0];
|
|
assign c1 = (sum_c1 >= Q) ? sum_c1[11:0] - Q[11:0] : sum_c1[11:0];
|
|
|
|
endmodule
|