ISSN 2347-1921 Volume 12 Number 07 Journal of Advances in Mathematics
6417 |
Page council for Innovative Research January 2016 www.cirworld.com
A REDUCED TABLEOF THE ZECH´S LOGARITHM
O. C. Justiz
1
, E. M. Capó
2
, P. F. Arrozarena
3
, G. S. Gómez
4
Departament of Mathematics. Central University “Marta Abreu”
of Las Villas. Cuba
oristela@uclv.edu.cu
Departament of Mathematics.
Central University “Marta Abreu” of Las Villas. Cuba
evaristoj@uclv.cu
Habana University. Cuba
pfreyre@matcom.uh.cu
Center ofMathematics Research. Guanajuato. México
guillermo.sosa@cimat.mx
ABSTRACT
In this work we will solve the problem of expression of the sum of two given elements of a finite field, as power of the primitive element of the field. We obtain a reduced table of the Zech's logarithm from our proposal that relate the Zech'slogarithm with the partition of the exponents of the powers of elements over finite field
(
)
in p-cyclotomic cosets modulo
(
−
)
. This reduces, in a significant way, the quantity of information to store and it facilitates its use in several cryptographic algorithms, specifically in asimetric cryptography. It is illustrated the computationof the Zech'slogarithm of any element thatdoesn't appear in the obtained reduced table.
Indexingterms/Keywords
Finite field; Zech's logarithm; cyclotomiccoset.
Academic Discipline And Sub-Disciplines
Discipline: Matthematics, Computer Science.Sub-Disciplines: Cryptology, Theoretical Computer Science.
MATHEMATICS SUBJECTCLASSIFICATION
MSC 2010:12E30, 11T22, 11T71
INTRODUCTION
The study of finite fields has made great progress in recent years because they are applied in areas as diverse as cryptography [1, 2, 3], coding theory [4, 5, 6], among other areas [7, 8]. By working with finite fields, arithmetic operations with its elements are performed, so you need to have efficient algorithms to perform such operations, this being a major problem today. Considering that multiplication of elements of a finite field is a polynomial multiplication it is convenient express the elements of the field as powers of a primitive element, so that the multiplication of them is reduced to the sum of their exponents. Also is necessary have a procedure to perform efficiently the sum of two elements of the field expressed as a power of the primitive element, since this operation under the above condition is not trivial. To solve this the so-called Zech´s logarithm table [6] is used. Another related problem with the above is when there are two binary finite fields
(2
)
and
(2
)
with primitive elements is
and
respectively (GF, denote Galois Field). All elements of
(2
)
and
(2
)
can be expressed as powers of
and
respectively. The elements of both fields can also be expressed as a binary digit sequence of n and m respectively. If we add
−
bits to the right of the elements
we obtain
2
−
sequences of m digits .An interesting question is ¿How to determine wichpower of the primitive element
, over the field
(2
)
, representthese new sequences? In this paper a proposal that significantly reduces the Zech's logarithm table is presented.
APPROACH PROBLEMS
Problem 1
Let the finite field
(2
)
which is an algebraic extension of degree n of the prime field
(
)
.We want to find the pairs
(
,
)
satisfying, 1+
=
(1) Considering that in any finite field of characteristic p [8].
(1+
)
p
=
(
)
⇒
1 +
=
(2)
(1+
)
p
=
(
)
p
⇒
1+
=
(3)
ISSN 2347-1921 Volume 12 Number 07 Journal of Advances in Mathematics
6418 |
Page council for Innovative Research January 2016 www.cirworld.com
is satisfied. Then if the pair
(
,
)
satisfies the relation (1) then the pair
(
×
,
×
)
also satisfies. The
×
y
×
elements are reduced modulo
n
−
1
.How to find these pairs?
Problem 2
Suppose we have the finite field
(
)
=
(
)
where
is a prime number and
is a positive integer. Let
a primitive element of the field
(
)
.If there are two elements of a finite field expressed as powers of the primitive element, how to express their sum as a power of the primitive element ?. In other words. If
,
,
are non-negative integers such numbers that
≠
≠
y
≠
≠
0
,if
+
=
. How to find
?. If in the expression
+
we extract the common factor under the powers we can reduce the problem to the previous case. Suppose that
<
, we have, with
=
−
mod (p
−
1)
,
+
=
(
1 +
) then,
1+
=
→
∙
=
+r
mod (p
−
1)
To answer this questions these problems for
(
)
and
= 2,8
fields were resolved. The results enabled us to detect regularities that allow us to build a reduced table ofZech'slogarithm, considering the p
–
cyclotomiccosetsmodulo
p
−
1
.
Let α a generator element of the multiplic
ative group of the field
(
)
, the product of two elements of the finite field are represented by
∙
=
(
+j)mod
p
−
1
and the addition of the elements of the finite field expressed as powers ofprimitive element is facilitated if the calledZech'slogarithm table is built [6], where for each integer
,
0
≤
≤
−
2
, the integer
=
(
)
such that
1+
=
=
z(i)
(4) is determined. Then,
+
=
∙
(
1 +
)=
∙
z(j
−
i)
=
i+z(v)
, where
(
)
is taken from the Zech's logarithm table. Given (4) and the analysis in the problem statement,the expressions (2) and (3) can be rewritten as follows
(1+
)
p
=
z(i)
⇒
1+
=
p×z(i)
(1+
)
p
=
z(i)
⇒
1+
=
p
×z(i)
RELATIONSHIP BETWEEN THEZECH'S LOGARITHMAND THE CYCLOTOMIC COSETS
We began recall that the q-cyclotomiccosets[9] [10] of
modulo
is defined by the set
={
,
,
2
,
⋯
,
−
1
}
, where
is the smallest positive integer such that
r
≡
(mod
). In particular, the2
–
cyclotomiccoset[9] [10]modulo
is the set
={
,
2 ,
2
2
,
⋯
,
2
−
1
}
, where
is the smallest positive integer such that
2
≡
(mod
). We noted earlier thatif the pair
(
,
)
satisfies the relation(1) then the pair
(
×
,
×
)
also satisfies it .The expression
×
(
(p
−
1))
where
∈
[
0,
]represents all the elements that arein the same p-cyclotomiccosetmodulo
p
−
1
.Thereforeknowing the Zech'slogarithm of an integer
we can find the Zech's logarithm ofallintegers of the form
×
(
(p
−
1))
. We illustrate the above taking a particular finite field. Let the finite field
(2
8
)
we take primitive polynomial
8
+
4
+
3
+
2
+1
as the defining polynomial. Let
be a root of this polynomialand hence a primitive field element. The2
–
cyclotomiccosets [9] modulo 255 are as follows C
0
= {0} C
1
={1,2,4,8,16,32,64,128} C
3
={3,6,12,24,48,96,192,129} C
5
={5,10,20,40,80,160,65,130} C
7
={7,14,28,56,112,224,193,131} C
9
={9,18,36,72,144,33,66,132} C
11
={11,22,44,88,176,97,194,133} C
13
={13,26,52,104,208,161,67,134} C
15
={15,30,60,120,240,225,195,135} C
17
={17,34,68,136} C
19
={19,38,76,152,49,98,196,137} C
21
={21,42,84,168,81,162,69,138} C
23
={23,46,92,184,113,226,197,139} C
25
={25,50,100,200,145,35,70,140}
ISSN 2347-1921 Volume 12 Number 07 Journal of Advances in Mathematics
6419 |
Page council for Innovative Research January 2016 www.cirworld.com
C
27
={27,54,108,216,177,99,198,141} C
29
={29,58,116,232,209,163,71,142} C
31
={31,62,124,248,241,227,199,143} C
37
={37,74,148,41,82,164,73,146} C
39
={39,78,156,57,114,228,201,147} C
43
={43,86,172,89,178,101,202,149} C
45
={45,90,180,105,210,165,75,150} C
47
={47,94,188,121,242,229,203,151} C
51
={51,102,153,204} C
53
={53,106,212,169,83,166,77,154} C
55
={55,110,220,185,115,230,205,155} C
59
={59,118,236,217,179,103,206,157} C
61
={61,122,244,233,211,167,79,158} C
63
={63,126,252,249,243,231,207,159} C
85
={85,170} C
87
={87,174,93,186,117,234,213,171} C
91
={91,182,109,218,181,107,214,173} C
95
={95,190,125,250,245,235,215,175} C
111
={111,222,189,123,246,237,219,183} C
119
= {119,238,221,187} C
127
={127,254,253,251,247,239,223,191} The cosetsC
17
,C
51
,C
85
,C
119
are the regular cyclotomiccosets [10] .In this case we have 35 cyclotomiccosetsdenoted by C
i
where
is the coset leaders
0 ≤
≤ 127
. So,
is a positive integer that takes values in the range from 0 to
p
−
12
. Thetable of Zech's logarithm for the field
(2
8
)
with defining polynomial
8
+
4
+
3
+
2
+1
,grouping the values of
according to the cyclotomic coset that they belong, appears in the Annex. Here are some examples of computation the sum of two elements of a finite field using Zech's logarithm table.
Example1:
a.
7
+
47
=
7
∙
(1+
40
)=
7
∙
(1+
5 × 2
3
)=
7
∙
(1+
5
)
2
3
=
7
∙
5
× 8 (
255)
=
7
∙
138 × 8 (
255)
=
7+84
=
91
b.
37
+
103
=
37
∙
(1+
66
)=
37
∙
(1+
33×2
)=
37
∙
(1+
33
)
2
=
37
∙
33
× 2 (
255)
=
37
∙
15 × 2 (
255)
=
67
c.
219
+
135
=
135
∙
(1+
84
)=
135
∙
(1+
21×2
2
)=
135
∙
(1+
21
)
2
2
=
135
∙
21
× 4 (
255)
=
135
∙
40
=
175
Now we buildthe table of theZech's logarithm given the partition of the set of non-negative integers
{0,1,2,3,
⋯
,254}
in 2
–
cyclotomiccosetsmodulo
255
. This allows us not store the entire table but only the values of the Zech's logarithm for the coset leaders. The Zech´s logarithm for the finite field
(2
8
)
with defining primitive polynomial
8
+
4
+
3
+
2
+1
,considering onlythe coset leaders, is showed in the following table.
Table 1: 2
–
cyclotomiccosets modulo 255 j z(j) j z(j) j z(j) j z(j)
0
∞
15 33 39 106 63 55 17 68 43 121 85 170 1 25 19 92 45 31 87 167
3 223 21 10 47 101 91 209 5 138 23 196 51 238 95 176 7 112 25 1 53 147 111 246 9 120 27 104 55 63 119 153 11 245 31 45 59 82 127 12 13 99 37 179 61 186
Using the table of coset leaders to calculate Zech’s logarithm of a value of
that is not on the table. The following cases may arise: 1. The number
is the product of a power of the characteristic field and an odd number which is a coset leader.
ISSN 2347-1921 Volume 12 Number 07 Journal of Advances in Mathematics
6420 |
Page council for Innovative Research January 2016 www.cirworld.com
2. The number
is an odd number that is not a coset leader. 3. The number
is the product of a power of the characteristic field and an odd number which that is not a coset leader.
Case 1:
If
=
×
then
(
)
=
(
)×
(mod(
−
))
Case 2:
We add (
−
) to
and expressed as the product of the largest possible power of thecharacteristicfieldand an odd number,
+ (
−
)=
→
=
×
→
+ (
−
)=
→
=
×
→
⋯
Suppose that for
is obtained :
−
=
×
where
is a coset leader.Stop the process and
=
×
×
×
⋯
×
=
×
being
=
+
+
⋯
+
, with
,
,
⋯
,
∈
[0,
−
].
(
)
=
(
)×
(mod(
−
))=
(
)×
(mod(
−
)) for same cosetleader
.
Case 3:
If
=
×
, we proceed to
similarly to Case 2.
Example 2:
Compute in
(2
8
)
, a) z(168) = z(21)
×2
3
(mod 255)= 10
×
8 = 80 b) z(197) 197 is an odd number that is not a coset leader
197+255=452→452=113
×2
2
→113+255=368→368=23
×2
4
As23 is a cosetleader then
197≡23
×2
2
×2
4
(mod255)=23
×2
6
(mod255)≡226
z(197)=z(23
×2
6
(mod255))=z(23)
×2
6
(mod255)=196
×
64(mod255)≡49
c) z(228) 228=57
×2
2
→57 + 255=312→312=
39
×2
3
39 is a cosetleader
228≡39
×2
2
×2
3
(mod255)=39
×2
5
(mod255)
z(228)≡z(39)
×2
5
(mod255)=106
×
32 (mod255)=77
CONCLUSIONS
In this paper a modification to the table of Zech´s logarithm for the field
(2
8
)
, applicable to any given field, consisting of a considerable reduction of the number of elements to be stored is proposed. For this the called p-cyclotomic cosets were used. This result is essential to perform the addition operation between two elements of a finite field represented as powers of a primitive element of this field. It also has various applications in cryptography, especially in the implementation of cryptographic algorithms.
REFERENCES
1. Didier F., M. and Laigle-ChapuyY.2007. Finding low-weight polynomial multiples using discrete logarithm. 2. Johansson T.2014.Low weight polynomials in crypto.
ISSN 2347-1921 Volume 12 Number 07 Journal of Advances in Mathematics
6421 |
Page council for Innovative Research January 2016 www.cirworld.com
3. Kiihn G. J. and W. Penzhorn T. 1994. Using Zech's Logarithm to Find Low-Weight Parity Checks for Linear Recurring Sequences. Communications and cryptography. 4. Elsenhans A.-S., KohnertA. and Wassermann A. 2010. Construction of Codes for Network Coding. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems
–
MTNS 2010. 5. LiJ. 2004. Combinatorially Designed LDPC Codes Using Zech Logarithms and Congruential Sequences.Coding, Cryptographyand Combinatorics. 6. Huber K.1990.
Some Comments on Zech’s Logarithms
. IEEE Transactions on Information Theory. 7. Meyer-Baese U. 2004. Digital Signal Processing with Field Programmable Gate Arrays. SecondEdition. 8. MullenG. L.and Panario D.2013. Handbook of Finite Fields, CRC Pres.Taylor& Francis Group. 9. Golomb S. W. 1981. Shift Register Sequences, Aegean Park Press. Laguna Hills, CA, USA. 10. Rani M. J. 2013 Cyclic Codes of length N over GF(q)q- ciclotomiccosets modulo N and application of Burnside´s lemma. InternationalJournal of Scientific and Research Publications.
ANEX
Table of the Zech´slogarithm forthe finite field
(2
8
)
with definingprimitive polynomial
8
+
4
+
3
+
2
+1
1+
=
z(i)
(
)
(
)
(
)
(
) 1
25
3 223 5
138
7
112
2
50
6
191
10
21
14
224
4
100
12
127
20
42
28
193
8
200
24
254
40
84
56
13
1 16
145
48
253
80
168
112
7
32
35
96
251
160
81
224
14
64
70
192
247
65
162
193
28
128
140
129
239
130
69
131
56
(
)
(
)
(
)
z
(
)
9
120
11
245
13
99
15 33 18
240
22
235
26
198
30 66 36
225
44
215
52
141
60 132 72
195
88
175
104
27
120 68
144
135
176
95
208
54
240 136
33
15
97
190
161
108
225 17
66
30
194
125
67
216
195
34
132
60
133
250
134
177
135 68
17
68
51
238
85
170
119
153
34
136
102
221
170
85
238
51
68
17
204
187
∞
0 221
102
136
34
153
119
0
∞
187
204
19
92
21
10
23
196
25
1
38
184
42
20
46
137
50
2