C.7 Examples for Chapter 10
Let’s solve the discrete log problem 2 x ≡ 71 ( m o d 131 ) 2 x ≡ 71 ( m o d 131 ) by the Baby Step-Giant Step method of Subsection 10.2.2 . We take N = 12 N = 12 since N 2 > p − 1 = 130 N 2 > p − 1 = 130 and we form two lists. The first is 2 j ( mod 1 ) 31 2 j ( mod 1 ) 31 for 0 ≤ j ≤ 11 0 ≤ j ≤ 11 :
>> for k=0:11;z=[k, powermod(2,k,131)];disp(z);end;
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 125
9 119
10 107
11 83
The second is 71 ⋅ 2 − j ( mod 1 ) 31 71 ⋅ 2 − j ( mod 1 ) 31 for 0 ≤ j ≤ 11 0 ≤ j ≤ 11 :
>> for k=0:11;z=[k, mod(71*invmodn(powermod(2,12*k,131),131),131)]; disp(z);end;
0 71
1 17
2 124
3 26
4 128
5 86
6 111
7 93
8 85
9 96
10 130
11 116
The number 128 is on both lists, so we see that 2 7 ≡ 71 ⋅ 2 − 12 ∗ 4 ( mod 131 ) 2 7 ≡ 71 ⋅ 2 − 12 ∗ 4 ( mod 131 ) . Therefore,
..................Content has been hidden....................
You can't read the all page of ebook, please click
here login for view all page.