extended euclid algorithm

Status
Not open for further replies.

MaheshKS

Newbie level 3
Hiii all, am trying to do verilog coding for extended euclids algorithm.. i ve done the code but der is some problem in the code... it is not entering in to the else loop..(ie..if (B3!=1)).. plzzzz help me...

Code Verilog - [expand]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
module private_key(
input rst,clk,
input [7:0]e_in,n_in,
output reg [7:0]d_out);

reg [7:0]A1,A2,A3,B1,B2,B3,temp,temp1,temp2,temp3,quo,count,rem;

always @(posedge clk)
begin
if(rst)
begin
A1<=1;A2<=0;A3<=n_in;
B1<=0;B2<=1;B3<=e_in;
end

else
begin

if(B3)
d_out<=B2;

else
begin
temp <= A3;
if (temp>=B3)
begin
temp<=temp-B3;
count<= count+1;
end

else
begin
rem <= temp;
quo <= count;
end

temp1<=A1; temp2<=A2; temp3<=A3;

A1<=B1; A2<=B2; A3<=B3;

B1<=temp1-(quo*B1);
B2<=temp2-(quo*B2);
B3<=temp3-(quo*B3);

end

end
end
endmodule

Last edited by a moderator:

FvM

Super Moderator
Staff member
Did you check the algorithm in a testbench? You'll notice that several variables are undefined when they are used in the first iteration(s), e.g. quo.

The code doesn't look like a correct implementation of extended euclidian algorithm. http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

MaheshKS

MaheshKS

points: 2
Helpful Answer Positive Rating

MaheshKS

Newbie level 3
am trying obtain multiplicative modulo inverse using extended euclids method

ads-ee

Super Moderator
Staff member
Only if B3 is 8'd0 will the else branch be taken, every other value will evaluate as logically true for the if compare.

To paraphrase FvM... Where is your testbench?

I'd appreciate if you would nicely format and use white between operations, so I don't have to do it (just to read the code).

compare the readability of the following reformatted code to your post above.

Code Verilog - [expand]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
module private_key(
input             rst, clk,
input      [7:0]  e_in, n_in,
output reg [7:0]  d_out);

reg [7:0] A1, A2, A3;
reg [7:0] B1, B2, B3,
reg [7:0] temp, temp1, temp2, temp3,
reg [7:0] quo, count, rem;

always @(posedge clk) begin
if(rst) begin
A1 <= 1;
A2 <= 0;
A3 <= n_in;
B1 <= 0;
B2 <= 1;
B3 <= e_in;
end else begin
if (B3)
d_out <= B2;
else begin
temp <= A3;
if (temp >= B3) begin
temp <= temp - B3;
count <= count +1;
end else begin
rem <= temp;
quo <= count;
end
temp1 <= A1;
temp2 <= A2;
temp3 <= A3;
A1 <= B1;
A2 <= B2;
A3 <= B3;
B1 <= temp1 - (quo * B1);
B2 <= temp2 - (quo * B2);
B3 <= temp3 - (quo * B3);
end
end
end
endmodule

MaheshKS

Newbie level 3
no.. if B3 is greater than one the else branch should take place....... yea, i could see lot of difference

FvM

Super Moderator
Staff member
The discussion seems pointless. Have a testbench, check the code, come back with the results and related questions.

I presume that the testbench will reveal uninitialized variables in a first order, so be prepared to make a few corrections.

ads-ee

Super Moderator
Staff member
it is not entering in to the else loop..(ie..if (B3!=1))
no.. if B3 is greater than one the else branch should take place.
If you know Verilog so well then why doesn't it do what you say it is supposed to do?

Even with 12+ years of Verilog FPGA design experience, I suppose I still don't know how an if statement works.
Guess I better hand in my resignation where I work now, I'm obviously not qualified to do my job. ;-)

All joking aside....

Your code defines B3 as a 8-bit wide reg.

Code Verilog - [expand]1
reg [7:0]A1,A2,A3,B1,B2,B3,temp,temp1,temp2,temp3,quo,count,rem;

You then proceed to check if it's "true" i.e. 1, based on your question (ie..if (B3!=1)).

Code Verilog - [expand]1
2
3
4
if(B3)
// code you think only executes when B3 = 1
else
// code you think only executes when B3 != 1

Unfortunately, that is NOT how Verilog interprets a 8-bit wide vector in an if statement. Instead a multi-bit vector is false only when the vector is all 0's or a combination of Z's, X's, and 0's.

But if you still don't believe me then run the following code in a simulator for 100 ns.

Code Verilog - [expand]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
timescale 1ps/1ps
module test;

reg [7:0] B3;
initial begin
B3 = 1; // you claim only this line should evaluate as "TRUE"
# 10000;
B3 = 0;
# 10000;
B3 = 8'b1000_0000;
# 10000;
B3 = 8'b0000_000Z;
# 10000;
B3 = 8'b0000_00X0;
# 10000;
B3 = 8'b0000_0001;
# 10000;
B3 = 5;
# 10000;
B3 = 8'b0000_0000;
# 10000;
B3 = 8'bzzzz_xxxx;
# 10000;
B3 = 8'b1111_1111;
# 10000;
end

always @* begin
if (B3) $display ("B3 is TRUE => %b", B3); else$display ("B3 is FALSE => %b", B3);
end

endmodule`

vGoodtimes

Advanced Member level 4
The main issues that I see:
1.) it isn't clear if you expect an input-output per cycle, or after "a long enough time". You use reset to load inputs, which is uncommon, and have no "output is valid" indicator.
2.) ads_ee is right. I don't know any language where "if (B3)" would mean that B3 is specifically equal to 1.
3.) You clearly are expecting the non-blocking "<=" to have the blocking "=" semantics. I suggest you read up on this topic, as it is important and there are several posts and articles on the subject.

As secondary items:
1.) I avoid the "if (x) y;" with no begin/end. This is more of a style choice, but you can run into issues. ads_ee's coding style with "end else begin" might look odd (with "end" at the beginning of a line) at first, but I think it is the best choice possible.
2.) I don't do enough collaborative verilog designs to know the opinion on this: http://stackoverflow.com/questions/...ables-be-given-local-scope-to-an-always-block . It seems like what you want -- VHDL-style variables -- but I get the feeling co-workers would become annoyed by this style.

Status
Not open for further replies.