Linear Complexity of r-ary Sequences with Period \(p^2\)\(q^2\) from Euler Quotients
Meng Lu *
School of Science, North China University of Science and Technology, Hebei, China.
*Author to whom correspondence should be addressed.
Abstract
Aims: Sequences based on the Euler quotients possess good pseudorandom properties and are widely used in cryptography
and communications. This paper aims to construct a new family of r-ary sequences based on Euler quotients modulo pq,
and to investigate the linear complexity and minimal polynomials.
Methodology: A class of r-ary sequences of period p2q2 is introduced, where p and q are distinct odd primes satisfying gcd(pq, (p−1) (q−1))=1 and r is an odd integer distinct from p and q. By analyzing the common roots of the generating polynomial and xp2q2−1 over suitable extension fields of \(\mathbb{F}\)r, the minimal polynomial and linear complexity of the sequence are determined under the conditions rq−1 \(\not\equiv\) 1 (modq2) and rp−1 \(\not\equiv\) 1 (modp2).
Results: Explicit expressions for the minimal polynomials and linear complexity are obtained in several cases. In particular, if r \(\nmid\) (p−1) and r \(\nmid\) (q−1), the minimal polynomial and linear complexity of the sequence are m(x) = \(\sum_{j=0}^{pq-1}\) x jpq and L(( fu)) = p2q2 − pq, respectively. If r | (p−1) and r | (q−1), the minimal polynomial and linear complexity of the
sequence are m(x)= Φ p2q (x) Φ pq2 Φ p2q Φ p2q2 (x) and L(( fu))= ϕ (p2q2) +ϕ (p2q) +ϕ (pq2) = p2q2−p2−q2−pq+p+q.
Conclusion: The proposed r-ary sequence derived from Euler quotients modulo pq exhibit high linear complexity, which
suggests strong resistance to the Berlekamp-Massey algorithm. Therefore, they have potential applications in cryptography.
These sequences also have potential applications in stream ciphers, pseudorandom number generation, spread spectrum communication, and code-division multiple access systems.
Keywords: Pseudorandom sequences, Euler quotient, stream cipher, r-ary sequences, linear complexity