如果a,b GF(P),則加法運算a+b=r (mod p),其中r滿足0<r<p-1,即a+b除以p的餘數,該操作成為模p加法。對於模减運算可以視為另類的模加運算,即a+(-b)=k (mod p)。本模塊將模加和模减集中在同一模塊中,由外部信號控制選擇使用模减或者模减運算。

信號名 |
方向 |
比特寬 |
端口定義 |
clk |
Input |
1 |
時鐘 |
reset |
Input |
1 |
複比特信號 |
add_en |
Input |
1 |
運算使能信號 |
op |
Input |
1 |
模加减選擇信號 |
a |
Input |
256 |
整數a輸入 |
b |
Input |
256 |
整數b輸入 |
sum |
Output |
256 |
運算結果 |
mod_add_done |
Output |
1 |
模加减完成標識 |
代碼如下:
// op = 1, a-b mod p // op = 0, a+b mod p module mod_add( input clk, input reset, input en, input [255:0] a, input [255:0] b, input op, output reg [255:0] sum, output reg mod_add_done ); parameter params_p=256'd15424654874903; //parameter params_p = 256'hFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F; reg [256:0] temp1;//temp2; //the [256] is the sign bit reg [1:0] cs,ns; parameter idle = 0; parameter s1 = 1; parameter s2 = 2; parameter s3 = 3; always@(posedge clk) begin if(reset) cs <= idle; else cs <= ns; end always@(*) begin case(cs) idle: ns <= s1; s1: ns <= s2; s2: if(temp1[256]) ns <= s2; else if(temp1 >= params_p) ns <= s2; else ns <= s3; s3: ns <= en ? idle : s3; endcase end always@(*) begin case(cs) idle: begin sum <= 0; mod_add_done <= 0; end s1: if(op) begin temp1 <= a - b; //temp2 = temp1 + params_p; end else begin temp1 <= a + b; //temp2 = temp1 - params_p; end s2: if(op) begin if(temp1[256]) begin //if temp1[256] is 1, 'a<b', 'a-b mod p' = 'params_p+(b-a)' temp1 <= temp1 + params_p; end else if(temp1 >= params_p) temp1 <= temp1 - params_p; end else begin if(temp1 >= params_p) //if temp1[256] is 1, 'a<b', 'a-b mod p' = 'params_p-(b-a)' temp1 <= temp1 - params_p; //else //temp2 = temp1; end s3: begin sum <= temp1[255:0]; mod_add_done <= 1; end endcase end endmodule
選用的曲線參數如下:https://blog.csdn.net/cccchhhh6819/article/details/100660139
testbeach:
`timescale 1ns/1ns module mod_add_tb(); reg clk, reset,en; reg [255:0] a, b; wire [255:0] sum; reg op; wire mod_add_done; mod_add add0( .clk(clk), .reset(reset), .en(en), .a(a), .b(b), .sum(sum), .op(op), .mod_add_done(mod_add_done) ); always #5 clk = ~clk; initial begin clk = 0; reset = 1'b1; en = 0; #20 reset = 1'b0; op = 1;//P=29 a = 256'd15424654874903; b =256'd15424654874906;
#10000 $stop;
end endmodule
本次仿真計算的是a-b(mod p) 也即15424654874903 - 15424654874906(mod 15424654874903 )的結果,相當於是-3 mod 15424654874903 。
仿真結果如下:為15424654874900。負數模運算規則 比如-2 mod 5 = -2+5=3 。-6 mod 5 = -6+5+5=4。所有結論正常。
當然我們更關注的是整個算法消耗的資源,這裏博主還沒學到綜合那裏去,後續會跟進這部分。當然該算法應該會占用較大的資源,畢竟用到了兩個比特寬的寄存器直接相加,會延遲寄存器之間的關鍵路徑,導致最後時鐘頻率跑不上去。