Linear Complexity of Several New Classes Sequences Based on Euler Quotient Modulo p m q n With Different Periods
Meng Lü, Chunying Zhang, Jiang Ma, Qun Wei, Jinghong Fu · Journal of Mathematics · 2026
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 p m q n , where p and q are distinct odd prime numbers. Under the condition that gcd( p q , ( p − 1)( q − 1)) = 1, we construct a binary sequence with period p m +1 q n +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 p m q n +1 when p divides q − 1. By analyzing the roots of the characteristic polynomial of this sequence over , the linear complexity of the sequence is obtained. To extend the construction for broader cryptographic deployment, we generalize the binary sequence of period p m q n +1 to an r ‐ary sequence for an odd prime r and present its linear complexity under the conditions r ∤ p − 1 and r q −1 ≢1 (mod q 2 ). 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.