The Discrete Logarithm (DL) of a vector of n bits is the ranking number of this vector in a maximum sequence generated by a Linear Feedback Shift Register (LFSR) defined by a logarithm base. In our application the base (dlb) is related to the primitive trinome P0+Pdlb+Pn =0.
By convention, the vector having all bits equal to 1, has a discrete logarithm equal to 0.
In a Linear Feedback Shift Register, the transformation of one vector to the next one is made by the shift of one position by each bit, the first bit being determined by an OR-exclusive function operated on 2 bits of this vector. It corresponds to the multiplication of the initial vector by its companion matrix.
In the maximum sequence, each vector of the 2n-1 space is part of the sequence and is always present one time only.
Lets take an example from a left LSFR in GF(2n=5) with the logarithm base dlb = 2 (P0+P2+P5=0).
Vector at time t+1 is calculated as follow:
Last column gives the decimal value of the calculated 5 bits vector.
The following table gives the discrete logarithm in base dlb = 2 (the rank is the discrete logarithm).
|
Rank |
bit5 |
bit4 |
bit3 |
bit2 |
bit1 |
decimal value of the 5 bits vector |
|
1 |
1 |
1 |
1 |
1 |
0 |
30 |
|
2 |
1 |
1 |
1 |
0 |
0 |
28 |
|
3 |
1 |
1 |
0 |
0 |
0 |
24 |
|
4 |
1 |
0 |
0 |
0 |
1 |
17 |
|
5 |
0 |
0 |
0 |
1 |
1 |
3 |
|
6 |
0 |
0 |
1 |
1 |
0 |
6 |
|
7 |
0 |
1 |
1 |
0 |
1 |
13 |
|
8 |
1 |
1 |
0 |
1 |
1 |
27 |
|
9 |
1 |
0 |
1 |
1 |
1 |
23 |
|
10 |
0 |
1 |
1 |
1 |
0 |
14 |
|
11 |
1 |
1 |
1 |
0 |
1 |
29 |
|
12 |
1 |
1 |
0 |
1 |
0 |
26 |
|
13 |
1 |
0 |
1 |
0 |
1 |
21 |
|
14 |
0 |
1 |
0 |
1 |
0 |
10 |
|
15 |
1 |
0 |
1 |
0 |
0 |
20 |
|
16 |
0 |
1 |
0 |
0 |
0 |
8 |
|
17 |
1 |
0 |
0 |
0 |
0 |
16 |
|
18 |
0 |
0 |
0 |
0 |
1 |
1 |
|
19 |
0 |
0 |
0 |
1 |
0 |
2 |
|
20 |
0 |
0 |
1 |
0 |
0 |
4 |
|
21 |
0 |
1 |
0 |
0 |
1 |
9 |
|
22 |
1 |
0 |
0 |
1 |
0 |
18 |
|
23 |
0 |
0 |
1 |
0 |
1 |
5 |
|
24 |
0 |
1 |
0 |
1 |
1 |
11 |
|
25 |
1 |
0 |
1 |
1 |
0 |
22 |
|
26 |
0 |
1 |
1 |
0 |
0 |
12 |
|
27 |
1 |
1 |
0 |
0 |
1 |
25 |
|
28 |
1 |
0 |
0 |
1 |
1 |
19 |
|
29 |
0 |
0 |
1 |
1 |
1 |
7 |
|
30 |
0 |
1 |
1 |
1 |
1 |
15 |
|
0 |
1 |
1 |
1 |
1 |
1 |
31 |
In the base dlb=2 (P0+P2+P5=0) , the discrete logarithm (DL) of 12 is 26 (26 is the rank from value 12 in the above serie of vectors). This results in the relation: DL2(12)=26.
The discrete logarithm with base dlb=3 (P0+P3+P5=0) can be calculated in the same way and can be summarised as follows :
|
Rank |
Dec. value |
|
Rank |
Dec. value |
|
Rank |
Dec. value |
|
1 |
30 |
|
11 |
4 |
|
21 |
14 |
|
2 |
28 |
|
12 |
8 |
|
22 |
29 |
|
3 |
25 |
|
13 |
16 |
|
23 |
27 |
|
4 |
19 |
|
14 |
1 |
|
24 |
22 |
|
5 |
6 |
|
15 |
2 |
|
25 |
12 |
|
6 |
13 |
|
16 |
5 |
|
26 |
24 |
|
7 |
26 |
|
17 |
10 |
|
27 |
17 |
|
8 |
20 |
|
18 |
21 |
|
28 |
3 |
|
9 |
9 |
|
19 |
11 |
|
29 |
7 |
|
10 |
18 |
|
20 |
23 |
|
30 |
15 |