FPGA素数域快速模乘

FPGA素数域快速模乘1、基2模乘，输入大数x、y、p，输出余数z=x×ymodp算法执行步骤取决于y的位宽，如果y为1024位二进制数，则需要1024步执行完成。算法中第4行与第5、6行可并行执行。2、基4模乘，使用booth编码，每次i+2，并判断y的3个二进制位，执行步骤减半，计算效率提高2倍。需要预计算R2=2xmodp。算法第6-10行与第11-13行，可并行执行。3、基8模乘，使用booth编码，每次i+3，并判断y的4个二进制位，执行步骤为基2的三分之一，计算效率提高3倍。需要预计算R2=2xmodp，R3=3xmodp，R4=4xmodp。算法第6-12行与第13-17行，可并行执行。下面给出基-4的256位FPGA串行代码，稍作修改，即可并行。IN_WIDTH位宽可自定义。moduleR4BIM#(parameterIN_WIDTH=256)(inputclk,inputrst,inputvi,input[IN_WIDTH-1:0]a,input[IN_WIDTH-1:0]b,input[IN_WIDTH-1:0]p,outputregvo,outputreg[IN_WIDTH-1:0]c);/////////////////////////////////////////////////////////////reg[IN_WIDTH-1:0]x;reg[IN_WIDTH+2:0]y;reg[IN_WIDTH-1:0]v;wire[IN_WIDTH-1:0]r;reg[IN_WIDTH-1:0]r1,r2;wire[IN_WIDTH-1:0]z1,z2;wire[IN_WIDTH:0]x1;wire[IN_WIDTH-1:0]x2,x3,x4,x5,x6;wirec1,c2;reg[2:0]y_LSB;reg[7:0]BIM_FSM;//////////////////////////////////////////////////////////////shift_mod#(.IN_WIDTH(IN_WIDTH))a_shift(.a(a),.p(p),.c(r));//预计算2xmodpr4_mod#(.IN_WIDTH(IN_WIDTH))r1_shift(.a(r1),.p(p),.c(z1));//求4R1modpr4_mod#(.IN_WIDTH(IN_WIDTH))r2_shift(.a(r2),.p(p),.c(z2));//求4R2modpassignx1=x+v;assign{c1,x2}=x1-p;assignx3=c1?x1:x2;assign{c2,x4}=x-v;assignx5=x4+p;assignx6=c2?x5:x4;/////////////////////////////////////////////////////////////always@(posedgeclk)beginif(rst)beginvo='b0;c='b0;BIM_FSM='b0;endelsebegincase(BIM_FSM)0:beginif(vi)beginx='b0;y={2'b00,b,1'b0};r1=a;r2=r;BIM_FSM=BIM_FSM+1'b1;endend1:beginy_LSB=y[2:0];BIM_FSM=BIM_FSM+1'b1;if(y==0)beginx=x;BIM_FSM=5;endend2:begincase(y_LSB)3'b000:beginv=0;end3'b001:beginv=r1;end3'b010:beginv=r1;end3'b011:beginv=r2;end3'b100:beginv=r2;end3'b101:beginv=r1;end3'b110:beginv=r1;end3'b111:beginv=0;endendcaseBIM_FSM=BIM_FSM+1'b1;end3:begincase(y_LSB)3'b000,3'b111:beginx=x;end3'b001,3'b010,3'b011:beginx=x3;end3'b100,3'b101,3'b110:beginx=x6;endendcaseBIM_FSM=BIM_FSM+1'b1;end4:beginy=y2;r1=z1;r2=z2;BIM_FSM=1;end5:beginvo=1'b1;c=x;enddefault:;endcaseendendendmodulemoduleshift_mod#(parameterIN_WIDTH=256)(input[IN_WIDTH-1:0]a,input[IN_WIDTH-1:0]p,output[IN_WIDTH-1:0]c);wire[IN_WIDTH:0]x;wire[IN_WIDTH+1:0]y;assignx={a,1'b0};assigny=x-p;assignc=y[IN_WIDTH+1]?x[IN_WIDTH-1:0]:y[IN_WIDTH-1:0];endmodulemoduler4_mod#(parameterIN_WIDTH=256)(input[IN_WIDTH-1:0]a,input[IN_WIDTH-1:0]p,output[IN_WIDTH-1:0]c);wire[IN_WIDTH-1:0]c1;shift_mod#(.IN_WIDTH(IN_WIDTH))u0_shift_mod(.a(a),.p(p),.c(c1));shift_mod#(.IN_WIDTH(IN_WIDTH))u1_shift_mod(.a(c1),.p(p),.c(c));程序仿真截图