Sidelnikov sequences, a kind of cyclotomic sequences with many desired properties such as low correlation and variable alphabet sizes, can be employed to construct a polyphase sequence family that has many applications in high-speed data communications. Recently, cyclotomic numbers have been used to investigate the linear complexity of Sidelnikov sequences, mainly about binary ones, although the limitation on the orders of the available cyclotomic numbers makes it difficult. This paper continues to study the linear complexity over$\mathbb {F}_{M}$of$M$-ary Sidelnikov sequence of period$q-1$using Hasse derivative, which implies$q=p^{m}$,$m\geq 1$and$M|(q-1)$. The$t$th Hasse derivative formulas are presented in terms of cyclotomic numbers, and some upper bounds on the linear complexity for$M=2$and 3 are obtained only with some additional restrictions on$q$. Furthermore, concrete illustrations for several families of these sequences, such as$q\equiv 1\pmod {2}$and$q\equiv 1\pmod {3}$, show these upper bounds are tight and reachable; especially for$q=2\times 3^{\lambda }+1 (1\leq \lambda \leq 20)$, the exact linear complexities over$\mathbb {F}_{3}$of the ternary Sidelnikov sequences are determined; and it turns out that all the linear complexities of the sequences considered are very close to their periods.

Min Zeng, Yisen Wang, Yuan Luo. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

The linear complexity is a measure for the unpredictability of a sequence over a finite field. Sequences with good pseudo-random properties and large linear complexity are widely used in the CDMA spread spectrum communication and cryptography. In recent years, many researchers have focused on the linear complexity of cyclotomic sequences such as Sidel'nikov sequence. This paper studies the FM-linear complexity of M-ary Sidel'nikov sequence of period p-1 using the Hasse derivative of its generating function, where M|(p-1). The tth Hasse derivative formulas are generalized in terms of cyclotomic numbers, and then the exact F3-linear complexities of the ternary Sidel'nikov sequences are determined for p = 2·3λ+1(1 ≤ λ ≤ 20). It turns out that all of the linear complexities of the considered sequences are very close to their periods.

An important and well-studied problem with many applications in communication systems is to find sequences with good correlation property that means auto- and cross-correlations of the sequences are all very small comparing with their periods. This paper focuses on sequences of period 2r- 1(r>> 1) with infinite third depth and shows that the difference operator really works with the interleaving technique on producing sequences with good correlation property and long period N = 22r-2r+1+1, which are constructed from 2-level autocorrelation sequences of period 2r- 1 except m-sequences. The method is lightweight since the computational complexity is O(p√N) and only the XOR logical operator is used.

In practice, sequences with long period but lightweight generation are always welcome in the applications of communication systems; however, the generation is not easy. From a certain angle of very high probability, this paper presents a solution, which is performed using cyclic difference sequences. As an application, the generated sequences can be interleaved to obtain good correlation properties. Furthermore, synchronization with blind detection is often required but difficult to be achieved. Even harder, periodic sequences may be affected to be ultimately periodic sequences with overhead because of device switching or noise. The determinations of the ultimate periods of above sequences and corresponding distributions are also investigated in this paper.

A well-known operator of vectors over finite field is the derivative, which is used to investigate the complexity of vectors in game theory, communication theory and cryptography. According to the operator, a corresponding complexity of the vector is called (the first) depth, which also contributes to two other definitions (the second and the third depths) by using polynomial factor and high order difference, respectively. For an n-dimensional vector over Fq(a finite field with q elements and characteristic p), the three depths are the same as its linear complexity if n = pr(r ≥ 0). In this paper, by investigation on vectors s of length n (or equivalent sequences of period n) with infinite third depth, and the cyclic-left-shift-difference operator E-1 on s, long least ultimate period sequences {(E-1)i(s)}i≥0are constructed with high probability over big alphabet using lightweight calculation. Furthermore, distributions of sequences s with period n = pr-1 (r >; 0), are described in terms of the least ultimate periods of {(E-1)i(s)}i≥0. In addition, we depict circulant matrix structure of the operator (E - 1)ifor 0i(s)}i≥0and a method to determine the least ultimate period are provided. The least ultimate period presents an adversary a sufficient condition to win the rotating-table game with rapid counteraction (RGRC).