A REDUCED TABLEOF THE ZECH´S LOGARITHM

  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