simu
Junior Member level 3
Hi
I have written codings for the following algorithmfor Montgomery modular division which performs Modular division by finding modular inverse first and then performing multiplication with an operand. the code seems to get compiled but output is not obtained.. can any one help me?
The algorithm and the corresponding code follows...
ALGORITHM
Inputs: X, M, b, n, where a is odd, a > b > 0, and n is the number of bits in M
Output: Z: Z = X r 2-nmod M, r is the inverse of M and |Z| < M
1st phase
u = M, X = a,v = b, r = 0, s = 1, k = 0
while u > 0 do
if u is even then u = u/2, s = 2s
else if u is even then u = v / 2 , r = 2r
else if u > u then u = (u-v)/2, r = r+s, s = 2s
else v = (v - u)/2, s = r + s, r = 2r
k = k + l
if u ≠ 1 then
if r ≥ M then r = r - M
Second phase
for i = 1 to k - n do
if r is even then r = r/2
else r = (r + M)/2
return r = M – r;
while n! = 0 do
if a mod 2 =0 then q : = 0 else
q: = 1;
r:=( r-q)/2; u1=( u1 + qa)/2 mod M;
n: = n-1;
end while
if u1 ≥ M then Z: = u1- M;
else
Z: = u1;
the code follows..
module montdiv( r, z);
output [4:0] z;
output [4:0]r;
reg [4:0] r;
reg [4:0]z;
reg [4:0]u, v, s, k, a, u1, t, l, q, m, b, n;
initial
begin
assign r = 0;
assign m = 5'b10001;
assign n = 5'b00101;
assign s = 5'b00001;
assign k = 0;
assign u = 5'b10001;
assign a = 5'b00011;
assign u1 = 0;
assign l = 5'b00001;
assign v = 5'b01010;
while (v > 0)
begin
if (u == 0)
begin
u = u >> 1;
s = s << 1;
end
else if (v == 0)
begin
v = v >> 1;
r = r << 1;
end
else if (u > v)
begin
u = (u -v);
u = u >> 1;
r = r + s;
s = s << 1;
end
else
begin
v = (v-u);
v = v >> 1;
s = s + r;
r = r << 1;
end
k = k + 1;
end
if (u != 1)
begin
if (r >= m)
r = r - m;
end
else
begin
if (r == 0)
r = r >> 1;
else
r = (r + m) >> 1;
end
while(n!= 0) begin
begin
if (r << 2 == 0)
q = 0;
else
q = 1;
r = (r - q) >> 1;
t = (u1 + q * a);
if (t << 2 == 0)
u1 = t >> 1;
else
begin
u1 = (t + (l * m));
u1 = u1 >> 1;
l = -l;
end
assign u1 = t;
assign n = n-1;
end
if (u1 >= m)
z = u1-m;
else
z = u1;
end
endmodule
I have written codings for the following algorithmfor Montgomery modular division which performs Modular division by finding modular inverse first and then performing multiplication with an operand. the code seems to get compiled but output is not obtained.. can any one help me?
The algorithm and the corresponding code follows...
ALGORITHM
Inputs: X, M, b, n, where a is odd, a > b > 0, and n is the number of bits in M
Output: Z: Z = X r 2-nmod M, r is the inverse of M and |Z| < M
1st phase
u = M, X = a,v = b, r = 0, s = 1, k = 0
while u > 0 do
if u is even then u = u/2, s = 2s
else if u is even then u = v / 2 , r = 2r
else if u > u then u = (u-v)/2, r = r+s, s = 2s
else v = (v - u)/2, s = r + s, r = 2r
k = k + l
if u ≠ 1 then
if r ≥ M then r = r - M
Second phase
for i = 1 to k - n do
if r is even then r = r/2
else r = (r + M)/2
return r = M – r;
while n! = 0 do
if a mod 2 =0 then q : = 0 else
q: = 1;
r:=( r-q)/2; u1=( u1 + qa)/2 mod M;
n: = n-1;
end while
if u1 ≥ M then Z: = u1- M;
else
Z: = u1;
the code follows..
module montdiv( r, z);
output [4:0] z;
output [4:0]r;
reg [4:0] r;
reg [4:0]z;
reg [4:0]u, v, s, k, a, u1, t, l, q, m, b, n;
initial
begin
assign r = 0;
assign m = 5'b10001;
assign n = 5'b00101;
assign s = 5'b00001;
assign k = 0;
assign u = 5'b10001;
assign a = 5'b00011;
assign u1 = 0;
assign l = 5'b00001;
assign v = 5'b01010;
while (v > 0)
begin
if (u == 0)
begin
u = u >> 1;
s = s << 1;
end
else if (v == 0)
begin
v = v >> 1;
r = r << 1;
end
else if (u > v)
begin
u = (u -v);
u = u >> 1;
r = r + s;
s = s << 1;
end
else
begin
v = (v-u);
v = v >> 1;
s = s + r;
r = r << 1;
end
k = k + 1;
end
if (u != 1)
begin
if (r >= m)
r = r - m;
end
else
begin
if (r == 0)
r = r >> 1;
else
r = (r + m) >> 1;
end
while(n!= 0) begin
begin
if (r << 2 == 0)
q = 0;
else
q = 1;
r = (r - q) >> 1;
t = (u1 + q * a);
if (t << 2 == 0)
u1 = t >> 1;
else
begin
u1 = (t + (l * m));
u1 = u1 >> 1;
l = -l;
end
assign u1 = t;
assign n = n-1;
end
if (u1 >= m)
z = u1-m;
else
z = u1;
end
endmodule