Rotating-table game and construction of periodic sequences with lightweight calculation

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 F_q (a finite field with q elements and characteristic p), the three depths are the same as its linear complexity if n = p^r (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)ⁱ(s)}_i≥0 are constructed with high probability over big alphabet using lightweight calculation. Furthermore, distributions of sequences s with period n = p^r-1 (r >; 0), are described in terms of the least ultimate periods of {(E-1)ⁱ (s)}_i≥0. In addition, we depict circulant matrix structure of the operator (E - 1)ⁱ for 0 <; i <; n and determine its rank. Some upper bounds on the ultimate period of {(E-1)ⁱ (s)}_i≥0 and 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).