GMW sequences over Galois rings and their linear complexities

Abstract

A new family of GMW sequences over an arbitrary Galois ring was defined by using the trace functions and permutations. This generalizes the concept of GMW sequences over finite fields. Utilizing the Fourier representation, we derived an estimate of the linear complexities of this family of GMW sequences. And the result shows that such sequences have large linear complexities.

Keywords

cryptography / GMW sequence / linear complexity / Galois ring

Introduction

With good interference-free ability, spread spectrum communications are used significantly in not only military communications but also civil communications. The performance of spread spectrum multiple-access communication systems are greatly influenced by the capabilities of spread sequences. One of the most important capabilities of the spread sequences is the linear complexity. A communication system will have good resistance to analysis if its spread sequences have large linear complexity. Consequently, constructing spread sequences with large linear complexities has become a hot research topic [1].

Utilizing trace functions, Scholtz and Welch [2] first constructed the GMW sequences over finite fields in 1984. Research shows that such sequences not only have two-level autocorrelation functions as m-sequences, but also have larger linear complexities and more cyclically inequivalent classes than m-sequences for the case that they have the same periods. Then the GMW sequences became a hot research focus, and a lot of results on the linear complexities of the GMW sequences have been achieved [3-8]. In 2000, Udaya and Siddiqi [9] extended Scholtz and Welch’s work to the case of Galois rings and constructed the GMW sequences over the Galois ring Z⁴. The result shows that the GMW sequences over Z⁴ have larger linear complexities and more sequence numbers than the GMW sequences over finite fields for the case that these sequences have the same periods. In this paper, we define a new family of GMW sequences over an arbitrary Galois ring, which generalizes the result of Udaya and Siddiqi for the case that the Galois ring is Z⁴. We also investigate the upper and lower bounds on the linear complexities of this family of GMW sequences, and the result shows that such sequences have large linear complexities.

Let p be a prime, e, r and u be positive integers. Let R and R′ denote the Galois rings of characteristic p^e, with sizes p^er and p^eru, respectively. The group R^* of units of R is a direct product of two subgroups G_C and G_A, where G_C is a cyclic group of order p^r-1 and G_A is an Abelian group of order p^(e-1)r with maximal element order p^e-1. Also, we use R′^* to denote the group of units of R′. Any element a in R can be expressed as a=pⁱw, where 0≤i≤e-1 and w∈R^*\cup{0}. Let Tr^ru_r denote the trace function from R′ to R, and Tr^r_l denote the trace function from R to Z_{p^e}. For the knowledge of Galois rings, please see Refs. [10,11].

GMW sequences over Galois rings

Now we define a new family of GMW sequences over Galois ring Z_p^e.

Permutation on R

Let b be an integer with 1≤b≤p^r-1 and (b,p)=(b,p^r-1)=1. For any element a=pⁱw in R, where 0≤i≤e-1 and w∈R^*\cup{0}, we define the map as \phi :R\to R as

\phi \left(a\right)=p^i{w}^b.

Lemma 1 The map \phiis a permutation on R.

Proof Let i be an integer with 0≤i≤e-1. It suffices to show that \phiis an injection on pⁱR^* . Let pⁱw₁, pⁱw₂ be any two elements of pⁱR^*, where w₁, w₂∈R^* . Assume that

\phi \left(p^i{w}_1\right)=p^i{w}_1^b=\phi \left(p^i{w}_2\right)=p^i{w}_2^b,

then we have

(1)w_1^b=w_2^b+p^{e-i}x,

where x∈R. Equation (1) implies that w_1^{b{p}^{e-1}}=w_2^{b{p}^{e-1}}, since the characteristic of R equals p^e. Suppose w₁=α₁β₁ and w₂=α₂β₂, where α₁α₂∈G_C, β₁β₂∈G_A, and applied to the equation w_1^{b{p}^{e-1}}=w_2^{b{p}^{e-1}}, we can conclude that {\alpha }_1^{b{p}^{e-1}}={\alpha }_2^{b{p}^{e-1}}. Note that the orders of α₁ and α₂ are both factors of p^r-1 and (p^r-1,bp^e-1), we obtain that α₁=α₂. Hence, we have pⁱβ^b₁=pⁱβ^b₂. It follows that β^b₁=β^b₂+p^e-iy, where y∈R. From (b,p^e-1)=1, we know that there exists an integer c which satisfies that bc≡1 (mod p^e-1), then

(2){\beta }_1={\left({\beta }_1^b\right)}^c={({\beta }_2^b+p^{e-i}y)}^c={\beta }_2+p^{e-i}y\prime ,

where y′∈R. Multiplying both sides of Eq. (2) by p′, we have pⁱβ₁=pⁱβ₂. This implies that pⁱw₁=pⁱw₂. The Lemma follows.

Construction of GMW sequences

Let α be an element of order p^ru-1 in R′ and v∈R′^* . Associated with the permutation \phi, we can define the GMW sequence S^v over Galois ring Z_{p^e}as

S^v={\{{\mathrm{Tr}}_1^r\{\phi [{T\mathrm{r}}_r^{ru}(v{\alpha }^i)]\}\}}_{i\ge 0}.

We also can define the GMW sequences family GGMW as

\mathrm{GGMW}=\{S^v:v\in R{\prime }^{*}\}.

Note that \phi is a permutation on R, the period of S^v is equal to p^ru-1.

Linear complexity

We employ the same techniques and notations as in the preceding sections.

Definition 1 We call polynomial C(x)=1+c_{1}x+c_2{x}^2+\cdots +c_m{x}^m\in Z_{p^e}[x] the associated connection polynomial of periodic sequence S={S_i}_i≥0 over Z_{p^e}, if the coefficients c₁,c₂,…,c_m satisfy

s_j=-{\displaystyle \sum _{i=1}^m{c}_i{s}_{j-i},\forall j\ge m.}

Definition 2 The linear complexity (LC) of periodic sequence S={s_i}_i≥0 over Z_{p^e} is equal to {deg(C(x))∶C(x) is an associated connection polynomial of S}.

Lemma 2 [12] Suppose S={s_i}_i≥0 is a sequence of period L. Let S(x)=s_0+s_{1}x+\cdots +s_{L-1}{x}^{L-1}.Then C(x) is an associated connection polynomial of S if and only if S(x)C(x)=0 (mod x^L-1).

Definition 3 [13] Suppose S={s_i}_i≥0 is a sequence of period p^ru-1 over Z_{p^e}. Let α be any primitive element of R′, then the Fourier representation of S is

where

Theorem 1 Suppose S={s_i}_i≥0 is a sequence of period p^ru-1 over Z_{p^e}. Then the linear complexity of S is equal to the number of nonzero terms appearing in the Fourier representation of S, i.e.,

\mathrm{LC}\left(S\right)=\left|\right\{{\hat{s}}_j:{\hat{s}}_j\ne 0,0\le j\le p^{ru}-2\left\}\right|.

Proof Assume that j₁,j₂,…,j_m are nonzero positions in the Fourier representation of S. This means that {\hat{s}}_{ji}\ne 0for i=1,2,…,m. Note that {\hat{s}}_j=nS({\alpha }^{-j}), we have

S({\alpha }^{-j})=\{\begin{array}{l}0,j\in \{0,1,\mathrm{...},p^{ru}-2\}/\{j_1,j_2,\mathrm{...},j_m\},\hfill \\ \mathrm{nonzero},j\in \{j_1,j_2,\mathrm{...},j_m\}.\hfill \end{array}

Now choose C(x)=(x-{\alpha }^{-j_1})(x-{\alpha }^{-j_2})\cdots (x-{\alpha }^{-j_m}). Then all the roots of x^{p^{ru}-1}-1,\mathrm{i}\mathrm{.e}\mathrm{.,}{\alpha }^0,{\alpha }^{-1},{\alpha }^{-2},\mathrm{...},{\alpha }^{2-p^{ru}}, are the roots of S(x)C(x). From Lemma 2, C(x) is an associated connection polynomial of S. It implies that LC(S)≤m. If LC(S)≠m, then there exists another associated connection polynomial C₀(x) of S with degree less than m. Also from Lemma 2, we obtain that the number of nonzero terms appearing in the Fourier representation of S is less than m. It is a contradiction. Thus, LC(S)=m. This completes the proof.

We assume from now on that b≥e. For any element a=pⁱw with 0≤i≤e-1 and w∈R^*\cup{0} in R, we define a map \hat{\phi }:R\to Ras

\hat{\phi }(a)=\{\begin{array}{l}0,i=0,\hfill \\ p^i{w}^b,i\ge 1.\hfill \end{array}

For any sequence S^v={s_i}_i≥1 of GGMW, where s_i=\mathrm{T}{\mathrm{r}}_1^r\{\phi [\mathrm{T}{\mathrm{r}}_r^{ru}(v{\alpha }^i)]\}, utilizing the map \hat{\phi }, we have

s_i={\mathrm{Tr}}_1^r\{{[\mathrm{T}{\mathrm{r}}_r^{ru}(v{\alpha }^i)]}^b\}+\mathrm{T}{\mathrm{r}}_1^r\{\hat{\phi }[\mathrm{T}{\mathrm{r}}_r^{ru}(v{\alpha }^i)]\}.

Let

$$\begin{gathered} S_1^v={\{\mathrm{T}{\mathrm{r}}_1^r\{{[\mathrm{T}{\mathrm{r}}_r^{ru}(v{\alpha }^i)]}^b\}\}}_{i\ge 0}, \\ {S}_2^v={\{\mathrm{T}{\mathrm{r}}_1^r\{\hat{\phi }[\mathrm{T}{\mathrm{r}}_r^{ru}(v{\alpha }^i)]\}\}}_{i\ge 0}, \end{gathered}$$

then we have

(3)S^v=S_1^v+S_2^v.

Using the p-adic expansion of b, we can write b in the form

b={\displaystyle \sum _{i=1}^H{b}_i{p}^{j_i}},

where 1≤b_i≤p-1, 0≤j_i≤r-1 and H is the number of nonzero terms appearing in the p-adic expansion of b.

Lemma 3 The linear complexity of S^v satisfies

\mathrm{LC}(S^v)\ge r{\displaystyle \prod _{i=1}^H\left(\begin{array}{c}u+b_i-1\\ b_i\end{array}\right).}

Proof It is clear that p^e-1S^v=p^e-1S^v₁ is isomorphic to some p-ary GMW sequence. Utilizing the result given by Zhu and Li (Theorem 2 in Ref. [6]), we obtain that LC(p^{e-1}{S}_1^v)=r{\displaystyle \prod _{i=1}^H\left(\begin{array}{c}u+b_i-1\\ b_i\end{array}\right)}. Hence, from the Fourier representation of S^v and Theorem 1, we have LC(S^v)\ge \mathrm{LC}(p^{e-1}{S}^v)=\mathrm{LC}(p^{e-1}{S}_1^v)=r{\displaystyle \prod _{i=1}^H\left(\begin{array}{c}u+b_i-1\\ b_i\end{array}\right)}.

Lemma 4 The linear complexity of S^v₁ satisfies

\mathrm{LC}(S_1^v)\le r{\displaystyle \prod _{i=1}^H\left(\begin{array}{c}eu+b-1\\ b\end{array}\right)}.

Proof Let \mathrm{\Gamma }=\{0,1,\alpha ,{\alpha }^2,\mathrm{...},{\alpha }^{p^{ru}-2}\}. Then v can be expressed as v=a_0+p{a}_1+\cdots +p^{e-1}{a}_{e-1}, where a₀,a₁,...,a_e-1∈Γ. This implies that v is a linear sum of at most e distinct powers of α. Moreover, each term Tr^r₁{[ Tr^ru_r (vαⁱ)]^b} (i≥0) of S^v₁ can be expressed as a linear sum of at most r\left(\begin{array}{c}eu+b-1\\ b\end{array}\right)distinct powers of α. From Theorem 1, we have

\mathrm{LC}(S_1^v)\le r\left(\begin{array}{c}eu+b-1\\ b\end{array}\right).

Let T=(p^ru-1)/(p^r-1). We need the following lemma.

Lemma 5 [6] Let S={Tr^ru_r(αⁱ)}_i≥0 be a field sequence, where α is primitive in GF(p^ru). Then every segment of T consecutive elements from S contains exactly (p^(u-1)r-1)/(p^r-1) zeros.

Lemma 6 For any v∈R′^*, let {\hat{S}}^v={\left\{s{\prime }_i\right\}}_{i\ge 0}be an intermediate sequence over R given by s′_i=Tr^ru_r (vαⁱ), where α is primitive in R′. Then every segment of T consecutive elements from {\hat{S}}^vcontains exactly (p^(u-1)r-1)/(p^r-1) elements from the ideal (p).

Proof Observe that p^{e-1}{\hat{S}}^vis isomorphic to some sequence defined in Lemma 5. Thus, from Lemma 5, every segment of T consecutive elements in p^{e-1}{\hat{S}}^vcontains exactly (p^(u-1)r-1)/(p^r-1) zeros. Since p^e-1s′_i is zero if and only if s′_i∈(p), the result follows.

Lemma 7 The linear complexity of S^v₂ satisfies

\mathrm{LC}\left(S_2^v\right)\le \mathrm{Tr}\mathrm{.}

Proof Assume that S^v₂ is nonzero and S_2^v={\left\{s_i\right\}}_{i\ge 0}. Let V(x)=v_0+v_{1}x+\cdots +v_{p^{ru}-2}{x}^{p^{ru}-2}, where v_i=\hat{\phi }[\mathrm{T}{\mathrm{r}}_r^{ru}(v{\alpha }^i)]. From the definition of \hat{\phi }and Lemma 6, v₀,v₁,…,v_T-1 are not all zeros. Let v_{i_1},v_{i_2},\mathrm{...},v_{i_t}be the nonzero terms in {v₀,v₁,…,v_T-1}. It is obvious that {\mathrm{Tr}}_r^{ru}(v{\alpha }^{i_j})(1\le j\le t)are zero divisors of R. From

we can conclude that the nonzero terms in \{v_0,v_1,\mathrm{...},v_{p^{ru}-2}\}follow the T periodicity. Let \hat{V}(x)=v_{i_1}{x}^{i_1}+v_{i_2}{x}^{i_2}+\cdots +v_{i_t}{x}^{i_t}, we have

$$\begin{gathered} V(x)={\displaystyle \sum _{m=0}^{p^r-2}(v_{mT+i_1}{x}^{mT+i_1}+v_{mT+i_2}{x}^{mT+i_2}+\cdots +v_{mT+i_t}{x}^{mT+i_t})} \\ ={\displaystyle \sum _{m=0}^{p^r-2}{x}^{mT}\left\{\hat{\phi }\right[{\mathrm{Tr}}_r^{ru}\left(v{\alpha }^{mT+i_1}\right)]x^{i_1}+\hat{\phi }[{\mathrm{Tr}}_r^{ru}\left(v{\alpha }^{mT+i_2}\right)]x^{i_2}+\cdots +\hat{\phi }[{\mathrm{Tr}}_r^{ru}\left(v{\alpha }^{mT+i_t}\right)\left]x^{i_t}\right\}} \\ ={\displaystyle \sum _{m=0}^{p^r-2}{x}^{mT}{\alpha }^{mTb}\left\{\hat{\phi }\right[{\mathrm{Tr}}_r^{ru}\left(v{\alpha }^{i_1}\right)]x^{i_1}+\hat{\phi }[{\mathrm{Tr}}_r^{ru}\left(v{\alpha }^{i_2}\right)]x^{i_2}+\cdots +\hat{\phi }[{\mathrm{Tr}}_r^{ru}\left(v{\alpha }^{i_t}\right)\left]x^{i_t}\right\}} \\ ={\displaystyle \sum _{m=0}^{p^r-2}{\alpha }^{mTb}{x}^{mT}\hat{V}\left(x\right)}. \end{gathered}$$

For any integer j with , V({\alpha }^{-j})=\delta {\displaystyle \sum _{m=0}^{p^r-2}{\alpha }^{mT(b-j)}}, where \mathit{\delta }=\hat{V}({\alpha }^{-j}). If j=b^{\prime }+n(p^r-1), where b′≠b, 0≤n<T, we have V({\alpha }^{-j})=\mathit{\delta }{\displaystyle \sum _{m=0}^{p^r-2}{\alpha }^{mT(b-b^{\prime })}}=0. If j=b+n(p^r-1), where 0≤n<T, we have V(α^-j)=(p^r-1)δ. Then V(α^-j)≠0 if and only if δ is nonzero. Hence, the number of j’s in {0,1,…,p^ru-2} which satisfy that V(α^-j)≠0 is at most T.

Now we prove by contradiction that the linear complexity of S^v₂ is at most Tr. Assume that the number of j’s in{0,1,…,p^ru-2} which satisfy that S(α^-j)≠0 is greater than Tr. Let j₀∈{0,1,…,p^ru-2} and satisfy S({\alpha }^{-j_0})={\displaystyle \sum _{i=0}^{p^{ru}-2}{s}_i{\alpha }^{-j_{0}i}}\ne 0. From the definition of v_i, s_i=Tr^r₁(v_i). Thus

{\displaystyle \sum _{i=0}^{p^{ru}-2}{s}_i{\alpha }^{-j_{0}i}}={\displaystyle \sum _{i=0}^{p^{ru}-2}{\mathrm{Tr}}_1^r(v_i){\alpha }^{-j_{0}i}}={\displaystyle \sum _{i=0}^{p^{ru}-2}{\displaystyle \sum _{k=0}^{r-1}{\sigma }^k(v_i){\alpha }^{-j_{0}i}}}={\displaystyle \sum _{k=0}^{r-1}{\displaystyle \sum _{i=0}^{p^{ru}-2}{\sigma }^k(v_i{\alpha }^{-j_{0}i{p}^{ru-k}})}}={\displaystyle \sum _{k=0}^{r-1}{\sigma }^k[V({\alpha }^{-j_0{p}^{ru-k}})]},

where σ is the Frobenius automorphism of R over Z_{p^e}[11]. From S({\alpha }^{-j_0})={\displaystyle \sum _{i=0}^{p^{ru}-2}{s}_i{\alpha }^{-j_{0}i}}\ne 0, {\displaystyle \sum _{k=0}^{r-1}{\sigma }^k[V({\alpha }^{-j_0{p}^{ru-k}})]}\ne 0. Then there k₀∈{0,1,…,r-1} satisfying that {\sigma }^{k_0}[V({\alpha }^{-j_0{p}^{ru-k_0}})]\ne 0. Moreover, we have V({\alpha }^{-j_0{p}^{ru-k_0}})\ne 0. This means that for any j with S(α^–j)≠0, there exists one k₀∈{0,1,…,r-1} satisfying that V({\alpha }^{-j_0{p}^{ru-k}})\ne 0. And we also can conclude that for any two distinct j_1,j_2\in \{0,1,\mathrm{...},p^{ru}-2\}, if there exists two corresponding k₁, k₂∈{0,1,…,r-1} satisfying that j_1{p}^{ru-k_1}\equiv j_2{p}^{ru-k_2}mod{p}^{ru}-1, then we must have k₁≠k₂. Hence, the number of j’s in {0,1,…,p^ru-2} which satisfy that V(α^-j)≠0 is greater than T. It is a contradiction. Then the number of j’s in {0,1,…,p^ru-2} which satisfies that S(α^-j)≠0 is at most Tr. From Theorem 1, we obtain that the linear complexity of S^v₂ is at most Tr. This completes the proof.

Utilizing Eq. (3), Lemmas 3, 4 and 7, we can finally obtain the following theorem.

Theorem 2 The linear complexities of sequences of GGMW satisfy

r{\displaystyle \prod _{i=1}^H\left(\begin{array}{c}u+b_i-1\\ b_i\end{array}\right)}\le \mathrm{LC}\le r\left(\begin{array}{c}eu+b-1\\ b\end{array}\right)+\mathrm{Tr}.

References

[1] Kumar P V. Frequency-hopping code sequence designs having large linear span. IEEE Transactions on Information Theory, 1988, 34(1): 146–151

[2] Scholtz R A, Welch L R. GMW sequences. IEEE Transactions on Information Theory, 1984, 30(3): 548–553

[3] Antweiler M, Bömer L. Complex sequences over GF (p^M) with a two-level autocorrelation function and a large linear span. IEEE Transactions on Information Theory, 1992, 38(1): 120–130

[4] Klapper A, Chan A H, Goresky M. Cascaded GMW sequences. IEEE Transactions on Information Theory, 1993, 39(1): 177–183

[5] Chung H, No J S. Linear span of extended sequences and cascaded GMW sequences. IEEE Transactions on Information Theory, 1999, 45(6): 2060–2065

[6] Zhu J K, Li S P. P-ary GMW sequences. Journal of China University of Science and Technology, 1991, 21(4): 433–446 (in Chinese)

[7] No J S. Generalization of GMW sequences and No sequences. IEEE Transactions on Information Theory, 1996, 42(1): 260–262

[8] Gong G. Q-ary cascaded GMW sequences. IEEE Transactions on Information Theory, 1996, 42(1): 263–267

[9] Udaya P, Siddiqi M U. Generalized GMW quadriphase sequences satisfying the Welch bound with equality. Applicable Algebra in Engineering, Communication and Computing, 2000, 10(3): 203–225

[10] McDonald B R. Finite Rings With Identity. New York: MarcelDekker, 1974

[11] Wan Z X. Lectures on Finite Fields and Galois Rings. Singapore: World Scientific Publisher, 2003

[12] Wan Z X. Algebra and Coding Theory. Beijing: Science Press, 1976 (in Chinese)

[13] Golomb S W, Gong G. Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar. Cambridge: Cambridge University Press, 2005

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg