EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 7, No. 3, 2014, 256-266 ISSN 1307-5543 – www.ejpam.com On the Linear Complexity of Ding-Helleseth Generalized Cyclotomic Binary Sequences of Order Four and Six Vladimir Edemskiy ∗, Olga Antonova Department of Applied Mathematics and Informatics, Novgorod State University, Veliky Novgorod, Russia Abstract. We propose a new computation method for the linear complexity and the minimal polyno- mial of Ding-Helleseth-generalized cyclotomic sequences. We will find the linear complexity of Ding- Helleseth-generalized cyclotomic sequences of order four and six and make the results of Tongjiang Yan et. al [19] about the sequences of order four more specific. 2010 Mathematics Subject Classifications: 11B50, 94A55, 94A60 Key Words and Phrases: Stream ciphers, Sequences, Generalized cyclotomy, Linear complexity, Mini- mal polynomial 1. Introduction Pseudo-random sequences are widely used in many fields, in particular in stream ciphers [3]. The linear complexity of a sequence s∞ is an important characteristic of its quality. It is defined to be the length of the shortest linear feedback shift register that can generate the sequence [14]. Sequences with high linear complexity (L(s∞) > N/2, where N denotes the period of the sequence) are important for cryptographic applications. Using classical cyclotomic classes and generalized cyclotomic classes to construct binary sequences, which are called classical cyclotomic sequences and generalized cyclotomic se- quences respectively, is an important method for sequence design [3]. As we all know, certain classical cyclotomic sequences, such as Legendre sequences and Hall sextic residue sequences, possess good linear complexity and autocorrelation properties (see [8, 11, 13, 16]). A gen- eralized cyclotomy with respect to pq was introduced by Whiteman [17]. New generalized cyclotomic sequences (D-GCS2k, where 2k is the order) including classical as particular, were defined by Ding and Helleseth in [7]. They predicted that they may be applied in cryptography and coding [5, 6]. Further it was shown that such sequences might have poor autocorrelation properties. It makes them difficult to use in Engineering [2, 15]. ∗Corresponding author. Email address: Vladimir.Edemsky@novsu.ru (V. Edemskiy) http://www.ejpam.com 256 c© 2014 EJPAM All rights reserved. V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 257 The D-GCS2 with period pq (where p and q are distinct odd primes) have high linear complexity [1, 4]. Later, the linear complexity of the D-GCS4 with period pq was calculated in [19]. However there are some technical errors in [19], (Lemma 4), which led to wrong results in some parts of the Theorem 2 in [19] and casting doubt on the method of this article (see appendix). Note that in [18] T. Yan mentions his previous work [19] has an error, but does not indicate exactly where it is and how to correct it. The purpose of this paper is to propose a new computation method for the linear complexity and the minimal polynomial of Ding-Helleseth-generalized cyclotomic sequences. We show that computation of the linear complexity of generalized cyclotomic sequences with period pq reduces to exploration of the classical cyclotomic sequences polynomial and obtain the linear complexity of Ding-Helleseth-generalized sequences of order four and six. We retain notation used in [19]. Let p and q be two odd primes with gcd(p−1, q−1) = d. Define N = pq, e = (p− 1)(q− 1)/d. The Chinese Remainder Theorem guarantees that there exists a common primitive root, g, of both p and q, and the order of g modulo N is e. Let x be an integer satisfying x ≡ g(mod p), and x ≡ 1(mod q). Thus, we can get a subgroup of the residue ring, ZN , with its multiplication [17], as the following: Z∗N = {g i x j : i = 0,1, . . . e− 1; j = 0, 1, . . . , d − 1}. Ding-Helleseth generalized cyclotomic classes of order d with respect to p and q are defined as Di = {g i+d t x j : t = 0,1, . . . e/d − 1; j = 0,1, . . . , d − 1}, where i = 0,1, . . . d − 1 [7]. Then Z∗N = ⋃d−1 i=0 Di , Di ∩ Dj = ∅ for i 6= j, where ∅ denotes the empty set. By definition, put D(p)i = {gd t+i : t = 0, 1, . . . (p− 1)/d − 1}, D(q)i = {g d t+i : t = 0,1, . . . (q− 1)/d − 1} and Pi = pD(q)i , Q i = qD(p)i , where i = 0,1, . . . d − 1. Let C0 = ⋃d/2−1 i=0 � Di ∪ Pi ∪Q i � ∪ {0}, C1 = ⋃d−1 i=d/2 � Di ∪ Pi ∪Q i � then Zpq = C0 ∪ C1 and C0 ∩ C1 =∅. Ding-Helleseth-generalized cyclotomic sequence of order d (D-GCSd), with s∞ = {s0, s1, . . . , si , . . .} is defined as si = ¨ 1, if i mod N ∈ C1, 0, otherwise. . Then s∞ possesses the minimum period pq, and the almost balance of the symbols 1s and 0s. 2. A Computation Method for Linear Complexity of Ding-Helleseth-Generalized Cyclotomic Sequences with Period pq For a binary sequence, s∞, with period N , if SN (x) = s0 + s1 x + . . .+ sN−1 xN−1, then its minimal polynomial and linear complexity can be calculated by the following equations [14]: m(x) = (xN − 1)/[gcd(xN − 1, SN (x))]. (1) V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 258 L(s∞) = N − deg[gcd(xN − 1, SN (x))]. (2) Let α be a primitive N -th root of unity over the field GF(2m) that is the splitting field of xN −1. Then, by (2), we have L(s∞) = N − � �{ j � �S(α j) = 0, j = 0,1, . . . , N − 1} � � . (3) where S(x) is defined by S(x) = ∑ i∈C1 x i . So, the computation of the linear complexity and the minimal polynomial of the sequence s∞ turns into the computation of roots of its polynomial. Let β = αq and γ = αp, then β and γ are primitive p-th and q-th roots of unity in the extension of field GF(2). There exist integers a, b [12], such that aq+ bp = 1. (4) Then α= βaγb. (5) Let ind(q)g c be discrete logarithm of c in the field GF(q) relative to the basis g. By definition of the discrete logarithm p ≡ g ind(q)g p(modq), hence from (4) we have b ≡ g−ind(q)g p(modq). (6) To explore the properties of the polynomial S(x), let us introduce auxiliary polynomials Sd(x) = ∑ u∈D(p)0 xu and Td(x) = ∑ v∈D(q)0 x v . Properties of polynomials Sd(x) and Td(x) are ob- tained in [9, 10] (see also [8, 13]). In particular from [9] we have ∑ u∈D(p)j βu = Sd(β g j ), ∑ v∈D(q)i γv = Td(γ g i ) (7) and Sd(β) + Sd(β g) + . . .+ Sd(β gd−1 ) = 1, Td(γ) + Td(γ g) + . . .+ Td(γ gd−1 ) = 1. (8) The following Lemmas 1 - 3 are needed to prove Theorem 1. By definition, put Dj,i = {g i+td x j−i : t = 0,1, . . . e/d − 1}, where j, i = 0, 1, . . . , d − 1. Lemma 1. Let the symbols be the same as before. For i, j = 0,1, . . . , d − 1 and k = 1, 2, . . . , pq− 1 we have ∑ u∈Dj,i αku = Sd(β akg j )Td(γ bkg i ). Proof. By (5), definitions of Dj,i and x we have ∑ u∈Dj,i αku = e/d−1 ∑ t=0 βakg j+d t γbkg i+d t . By definition gcd(p − 1, q − 1) = d, then Ze/d ∼= Z(p−1)/d × Z(q−1)/d relatively to isomorphism ϕ(a) = (a mod (p − 1)/d), a mod (q − 1)/d) [12]. Hence ∑ u∈Dj,i αku = ∑ v∈D(p)j βakv ∑ w∈D(q)i γbkw. Application of (7) concludes the proof of Lemma 1. V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 259 Lemma 2. Let the symbols be the same as before. For i = 0,1, . . . , d − 1 and k = 1,2, . . . , pq− 1 we have ∑ u∈Pi αku = Td(γ kg i ). Proof. By definition of Pi we have ∑ u∈Pi αku = ∑ v∈D(q)i αkpv . Using (7) and definition γ = αp, we obtain ∑ v∈D(q)i αkpv = Td(γkg i ). Lemma 2 is proved. Lemma 3 can be shown in a similar way. Lemma 3. Let the symbols be the same as before. For j = 0,1, . . . , d − 1 and k = 1,2, . . . , pq− 1 we have ∑ u∈Q j αku = Sd(β kg j ). Now we can prove the basic theorem about the linkage of the linear complexity of Ding- Helleseth-generalized cyclotomic sequences with the values of the polynomials of the classical sequences. Theorem 1. Let the symbols be the same as before. If k = 1, 2, . . . , pq− 1, then S(αk) = d−1 ∑ i=d/2 � Td � γkg i−ind(q)g p � δ+ Td(γ kg i ) + Sd(β kg i ) � , where δ = ¨ 1, if k 6≡ 0(modp), 0, if k ≡ 0(modp). . Proof. By definition of the sequence s∞ we have S(αk) = d−1 ∑ i=d/2 ∑ u∈Di αku + ∑ u∈Pi αku + ∑ u∈Q i αku ! . (9) We consider the first item of this sum. By definition Di = ⋃d−1 j=0 Dj,i , hence ∑ u∈Di αku = d−1 ∑ j=0 ∑ t∈Dj,i αkt ! , then by Lemma 1 we have ∑ u∈Di αku = d−1 ∑ j=0 Sd(β kag j )Td(γkbg i ). V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 260 If k 6≡ 0(modp), then from (8) we obtain ∑d−1 f=0 Sd(β kag f ) = 1. Yet, if k ≡ 0(modp), then d−1 ∑ f=0 Sd(β kag f ) = p − 1 and p − 1 ≡ 0(mod2). Thus, the first item of (9) is equal to δ d−1 ∑ i=d/2 Td(γkbg i ). The sum of the second and the third items is d−1 ∑ i=d/2 � Td(γkg i ) + Sd(β kg i � by Lemmas 2 and 3. Application of (6) concludes the proof of Theorem 1 . To sum up, we can note, that by Theorem 1, the computation of the values of the sequence polynomial S(x) and, therefore, the computation of the linear complexity of the sequence s∞ turns into the computation of the values Sd(x) and Td(x) for cyclotomic classes members. By Theorem 1, for fixed j and i, the values of S(αk) are the same for all k ∈ Dj,i; for fixed i, the values of S(αk) are same for all k ∈ Pi; for fixed i, the values of S(αk) are same for all k ∈ Q i . Then the matrix S = (si j) of order d + 1 is well defined, where s ji = S(αk), if k ∈ Dj,i and sd j = S(αk), if k ∈ Pj ; sid = S(αk), if k ∈ Q i; i, j = 0, 1, . . . , d − 1, sdd = S(1). Let us note that in order to compute the linear complexity of sequences s∞ and m(x) it suffices to define the zero elements of the matrix S. Additionally we note that Theorem 1 also allows to evaluate the linear complexity of the sequence s∞ as it was done in [18]. Later on, for the convenience of computations of the matrix S we introduce the following notations: Sd(x) = � Sd(x), Sd(x g), . . . , Sd(x gd−1 ), Sd(1) � , Td(x) = � Td(x), Td(x g), . . . , Td(x gd−1 ), Td(1) � . Let Ad(x) = d−1 ∑ i=d/2 Sd(x g i ) and Bd(x) = d−1 ∑ i=d/2 Td(x g i ). Then immediately from Theorem 1 we obtain the following: Lemma 4. Let the symbols be the same as before. Then we have S= � 1 . . . 1 0 �T Bd � γg−ind(q)g p � + � 1 1 . . . 1 �T Bd(γ) +AT d (β) � 1 . . . 1 � , (10) where AT is a transposed matrix A. The method of computation Sd(β) and Td(γ) by using explicit formulas for computation of cyclotomic numbers was proposed in [9, 10]. Using Theorem 1 in the next sections we will obtain new results of the linear complexity of Ding-Helleseth-generalized sequences of order four and six. V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 261 3. The Linear Complexity and the Minimal Polynomial of D-GCS4 For d = 4 there is an expansion p = x2 + 4y2, where x , y are integers and x ≡ 1(mod4) [12]. In [9] the values of the polynomial S4(β) � T4(γ) � are computed depending on x , y . Let � 2 p � 4 and � 2 p � 2 denote the symbols of the 4th residues and 2th residues of p respectively. The following Lemma 5 is needed to prove Theorem 2. Lemma 5. Let the symbols be the same as before. (i) If � 2 p � 4 = 1, then A4(β) = (0,0, 1,1, 0) or A4(β) = (1, 1,0, 0,0). (ii) If � 2 p � 2 = 1 and � 2 p � 4 6= 1, then A4(β) = (µ,µ + 1,µ + 1,µ, 0), where µ meets the rule µ2 +µ+ 1= 0. (iii) If � 2 p � 2 6= 1, then A4(β) = (η,η2,η4,η8, 0) or A4(β) = (η,η8,η4,η2, 0), where η meets the condition η4 +η+ 1= 0. Proof. By definition A4(β) = S4(β g2 ) + S4(β g3 ). Consequently, to prove Lemma 5 it is sufficient to give the values of S4(β) for each option. (i) If � 2 p � 4 = 1, then y ≡ 0(mod4) [12]. In this case, by [9] we have S4(β) = (1, 1,0, 1,0) for x ≡ 5(mod8) or S4(β) = (1, 0,0, 0,0) for x ≡ 1(mod8). (ii) If � 2 p � 2 = 1 and � 2 p � 4 6= 1, then S4(β) = (µ, 0,µ+ 1,0, 0) for x ≡ 5(mod8) or S4(β) = (µ, 1,µ+ 1,1, 0) for x ≡ 1(mod8), where µ meets the rule µ2 +µ+ 1= 0 [9]. (iii) If � 2 p � 2 6= 1, then S4(β) = (ζ,ζ2,ζ4,ζ8, 1) or S4(β) = (ζ,ζ8,ζ4,ζ2, 1), where ζ meets the condition ζ8 + ζ4 + ζ2 + ζ+ 1= 0. In this case η= ζ4 + ζ8 or η= ζ4 + ζ2 [9]. After summing of we obtain the statement of Lemma 5 for all cases. If � 2 p � 4 = 1 or � 2 q � 4 = 1, then by Lemmas 2, 3 S(αq) ∈ {0,1}, S(αp) ∈ {0, 1} [9]. We can change α and without loss of generality assume that S(αq) = S(αqg) = 0, if � 2 p � 4 = 1 and S(αp) = S(αpg) = 0, if � 2 q � 4 = 1. Let Di(x) = ∏ i∈Di (x−αi), Pi(x) = ∏ i∈Pi (x−αi) and Q i(x) = ∏ i∈Q i (x−αi); i = 0,1, 2,3. Theorem 2. Let the symbols be the same as before. (i) If � p q � 2 = 1 and � 2 p � 4 = 1, then L(s∞) = q(p+ 1)/2− 1, m(x) = (x pq − 1)/ � (x − 1)D0(x)D1(x)Q0(x)Q1(x) � . (ii) If � p q � 2 6= 1 and � 2 p � 4 = 1, then L(s∞) = pq− (p+ 1)/2, m(x) = (x pq − 1)/ � (x − 1)Q0(x)Q1(x) � . V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 262 (iii) If � 2 q � 4 = 1, then L(s∞) = pq− (q+ 1)/2, m(x) = (x pq − 1) � (x − 1)P0(x)P1(x) � . (iv) If � 2 p � 4 6= 1 and � 2 q � 4 6= 1, then L(s∞) = pq− 1, m(x) = (x pq − 1)/(x − 1). V. Edemskiy and O. Antonova / Eur. J. Pure Appl. Math, 7 (2014), 256-266 263 Proof. We will employ Theorem 2 to determine the values of the matrix S. (i) By assumption gcd(p − 1, q − 1) = 4, consequently � 2 q � 2 6= 1 for � 2 p � 4 = 1 [12]. In this case by Lemma 6 we have A4(β) = (0,0, 1,1, 0) or A4(β) = (1,1, 0,0, 0) and B4(γ) = (η,η2,η4,η8, 0) or B4(γ) = (η,η8,η4,η2, 0). Now, if � p q � 2 = 1, then ind(q)g p ≡ 0(mod4) or ind(q)g p ≡ 2(mod4). In the first case Bd � γg−ind(q)g p � +Bd(γ) = (0,0, 0,0, 0,0) and in the second case Bd � γg−ind(q)g p � + Bd(γ) = (1, 1,1, 1,0). Thus, by Lemma 5 we can deduce that the first two rows of the matrix S consist of zeros, also s44 = 0, and all other entries are non-zero. Hence, � �{ j � �S(α j) = 0, j = 0,1, . . . , N − 1} � �= 2 � �Di � �+ 2 � �Q i � �+ 1= q(p− 1)/2+ 1 and by (3) L(s∞) = q(p+ 1)/2− 1. From (1) we have m(x) = (x pq − 1)/ � (x − 1)D0(x)D1(x)Q0(x)Q1(x) � by the choice of α. (ii) In this case the expressions for A4(β) and B4(γ) are the same as in (1), but when � p q � 2 6= 1 we have ind(q)g p ≡ 1(mod4) or ind(q)g p ≡ 3(mod4). Hence Bd � γg−ind(q)g p � + Bd(γ) = (b0, b1, b2, b3, 0) and b j 6= 0, b j 6= 1 for j = 1,2, 3,4. Then by Lemma 4 we have s04 = s14 = s44 = 0, and all other entries of S are non-zero. Therefore, � �{ j � �S(α j) = 0, j = 0,1, . . . , N − 1} � �= 2 � �Q i � �+1= (p+1)/2. From (1) and (3), it follows that L(s∞) = pq− (p+ 1)/2 and m(x) = (x pq − 1)/ � (x − 1)Q0(x)Q1(x) � . Statements of (iii) and (iv) can be proved in the same way. From Theorem 2 we can obtain that if � 2 p � 4 = 1, then the linear complexity of D-GCS4 depends on value � p q � 2 . For example, if p = 73, q = 5 or p = 73, q = 101, then �73 5 � 2 6= 1 and � 73 101 � 2 6= 1, hence L(s∞) = pq − (p + 1)/2 = 328 or L(s∞) = 7336, respectively. Yet, if p = 89, q = 5 or p = 73, q = 173, then �89 5 � 2 = 1 and � 73 173 � 2 = 1 hence L(s∞) = q(p + 1)/2 − 1 = 224 or L(s∞) = 6400 respectively. These facts can be easily obtained by means of calculation of the linear complexity of D-GCS4 using, for example, the Berlekamp-Massey algorithm [14]. Thus, Theorem 2 from [19] is not true. 4. The Linear Complexity of D-GCS6 Let d = 6, the values of the polynomial S6(β) � T6(γ) � are computed in [9]. Similar to the proof of Theorem 2, we can prove the following Theorem 3. REFERENCES 264 Theorem 3. Let the symbols be the same as before. (i) If � 2 p � 6 = 1 and � 2 q � 6 = 1, then L(s∞) = (pq+ 1)/2−∆; (ii) If � 2 p � 6 = 1; � 2 q � 6 6= 1 and � p q � 3 = 1 or � 2 p � 6 = 1; � 2 q � 3 = 1 and � 2 q � 2 6= 1; � p q � 3 6= 1, then L(s∞) = (p+ 1)q/2−∆, where ∆= ¨ 1, if S(1) = 0, 0, otherwise ; (iii) If � 2 p � 6 = 1; � 2 q � 3 6= 1 and � p q � 3 6= 1 then L(s∞) = pq− (p− 1)/2−∆; (iv) If � 2 q � 6 = 1 and � 2 p � 6 6= 1 then L(s∞) = pq− (q− 1)/2−∆; (v) If � 2 p � 2 = 1; � 2 p � 3 6= 1; � 2 q � 3 6= 1 and � p q � 3 6= 1, then L(s∞) = pq− (p− 1)(q− 1)/6−∆; (vi) If conditions (i)-(v) are not true, then L(s∞) = pq−∆. Also we can obtain the minimal polynomial of DCS6. Additionally we can note that for the case of (ii) the linear complexity of D-GCS6 does not depend on the value � p q � 3 , but for the minimal polynomial this is not the case. Our examples p = 31, q = 127; p = 31, q = 19 or p = 31, q = 43; p = 31, q = 7; p = 7, q = 31; p = 7, q = 79; p = 13, q = 7 shows that all the cases of Theorem 3 are possible. 5. Conclusion For additive stream ciphering, the linear span of the keystream sequence must be large enough. This paper shows that almost all Ding-Helleseth-generalized cyclotomic sequences of order four or six with period pq have high linear complexity and almost ideal balance property. Long periods can also be obtained easily. References [1] E. Bai, X. Liu, and G. Xiao. Linear complexity of new generalized cyclotomic sequences of order two of length pq. IEEE Transactions on Information Theory, 51:1849–1853, 2005. [2] Z. Chen and S. Li. Some Notes on Generalized Cyclotomic Sequences of Length pq. Journal of Computer Science and Technology, 23(5):843–850, 2008. [3] T. W. Cusick, C. Ding, and A. Renvall. Stream Ciphers and Number Theory. North-Holland Mathematical Library, North-Holland Publishing Co., Amsterdam, 1998. [4] C. Ding. Linear complexity of generalized cyclotomic binary sequences of order 2. Finite Fields and Their Applications, 3(2):159–174, 1997. [5] C. Ding. Autocorrelation values of generalized cyclotomic sequences of order two. IEEE Transactions on Information Theory, 44(5):1699–1702, 1998. REFERENCES 265 [6] C. Ding. New generalized cyclotomy and its applications. Finite Fields and Their Appli- cations, 4(2):140–166, 1998. [7] C. Ding and T. Helleseth. Generalized cyclotomic codes of length pe1 1 . . . pet t . IEEE Trans- actions on Information Theory, 45(2):467–474, 1999. [8] C. Ding, T. Helleseth, and W. Shan. On the linear complexity of Legendre sequences. IEEE Transactions on Information Theory, 44:1276–1278, 1998. [9] V.A. Edemskii. On the linear complexity of binary sequences on the basis of biquadratic and sextic residue classes. Discrete Mathematics and Applications, 20(1):75–84, 2010. [10] V.A. Edemskiy. Linear complexity of ternary sequences formed on the basis of power residue classes. Problems of Information Transmission., 44(4):287–294, 2008. [11] M. Hall. A survey of difference sets. Proceedings of the American Mathematical Society, 7:975–986, 1056. [12] K. Ireland and M. Rosen. A Classical introduction to modern number theory. Springer- Verlag, North-Holland Publishing Co., Amsterdam, 1982. [13] J.H. Kim and H.Y. Song. On the linear complexity of halls sextic residue sequences. IEEE Transactions on Information Theory, 47(5):2094–2096, 2001. [14] R. Lidl and H. Niederreiter. Finite Fields. Addison-Wesley Press, Massachusetts, 1983. [15] W. Meidl. Remarks on a cyclotomic sequence. Designs, Codes, and Cryptography, 51(1):33–44, 2009. [16] W. Meidl and A. Winterhof. On the autocorrelation of cyclotomic generators. In Lecture Notes in Computer Science., volume 2948. Springer, Berlin, 2004. [17] A.L. Whiteman. A family of difference sets. Illinois Journal of Mathematics, 6:107–121, 1962. [18] T Yan. Linear complexity of ding-helleseth generalized cyclotomic binary sequences of any order. eprint arXiv 1108.4450, 2011. [19] T. Yan, L. Hong, and G. Xiao. The linear complexity of new generalized cyclotomic binary sequences of order four. Information Sciences, 178(3):2094–2096, 2008. Appendix Let as in [19] SQ j( j+1) = ∑ i∈Q j ⋃ Q j+1 αi and SPD j( j+1) = ∑ i∈Pj ⋃ Pj+1 ⋃ Dj ⋃ Dj+1 αi Then S(α) = SQ 23+SPD 23 and the values of S(αk) are given in Table 1 [19]. In particular, authors argue that S(αk) = SQ 23 + SPD 23 + 1, if k ∈ D2 and k(mod p) ∈ D(p)0 . We argue that this is not true. REFERENCES 266 By definition we have S(αk) = ∑ i∈Q2 + ∑ i∈Q3 + ∑ i∈P2 + ∑ i∈P3 + ∑ i∈D2 + ∑ i∈D3 ! αki or S(αk) = ∑ j∈kQ2 + ∑ j∈kQ3 + ∑ j∈kP2 + ∑ j∈kP3 + ∑ j∈kD2 + ∑ j∈kD3 ! α j . If k ∈ D2 and k(mod p) ∈ D(p)0 , then by Lemma 2 [19] we have kQ2 = Q2; kQ3 = Q3; kP2 = P0; kP3 = P1; kD2 = D0; kD3 = D1, hence S(αk) = SQ 23 + SPD 01 . By Lemma 3 [19] we note that ∑ i∈P0 ⋃ P1 αi = ∑ i∈P2 ⋃ P3 αi +1 and ∑ i∈D0 ⋃ D1 αi = ∑ i∈D2 ⋃ D3 αi +1, then S(αk) = SQ 23 + SPD 23 . The other errors in the Table can be shown in the same way. It is easy to test for p = 5, q = 13. The technical errors in Lemma 4 led to wrong results in Lemma 7. If 2 ∈ D1 and 2(modp) ∈ D(p)0 , then 4 ∈ D2, 4(modp) ∈ D(p)0 and S(α4) = S4(α) = S(α) . In [19] S(α4) = S4(α) = S(α) + 1 and authors draw a conclusion that S(α) /∈ {0, 1}. This is not true. Thus, proof of the main theorems in [19] is not complete.