Linear Complexity of Several New Classes Sequences Based on Euler Quotient Modulo pmqn With Different Periods

Pseudorandom sequences with large linear complexity are widely employed in practical secure communication systems, such as stream ciphers, spread-spectrum communications, and wireless networks. They play a critical role in enhancing resistance against linear cryptanalysis. Motivated by practical cryptographic requirements, in this work, we investigate binary and r-ary sequences derived from Euler quotients modulo pmqn, where p and q are distinct odd prime numbers. Under the condition that gcdpq,p−1q−1=1, we construct a binary sequence with period pm+1qn+1 and determine its linear complexity. Furthermore, according to the ring theory of residue classes, we construct a new class of binary sequence with period pmqn+1 when p divides q−1. By analyzing the roots of the characteristic polynomial of this sequence over F2, the linear complexity of the sequence is obtained. To extend the construction for broader cryptographic deployment, we generalize the binary sequence of period pmqn+1 to an r-ary sequence for an odd prime r and present its linear complexity under the conditions r∤p−1 and rq−1≢1 modq2. It is shown that the linear complexity of these sequences is at least half of their period, implying strong resistance to the Berlekamp–Massey algorithm. The proposed sequences are suitable for stream cipher design, secure random number generation, and other communication security engineering scenarios that require long period, high linear complexity pseudorandom signals. This is an open access article under the terms of the Creative Commons Attribution-Noncommercial License, which permits use, distribution, and reproduction in any medium, provided that the original work is properly cited and is not used for commercial purposes.