On the Pseudorandomness of the Power Generator with Squarefree Composite Moduli

Finite binary sequences with strong pseudorandom properties are essential for secure cryptographic systems. The power generator, defined by a modular exponentiation recurrence, is a widely used method for creating such sequences. While its pseudorandomness has been extensively analysed for prime moduli, real-world cryptographic applications like the RSA and Blum–Blum–Shub generators rely heavily on composite moduli. This paper bridges that gap by investigating the power generator’s behaviour when the modulus is a product of distinct primes. Building upon Gyarmati’s exponential sum estimates for prime moduli, we demonstrate that the generator retains its strong pseudorandom characteristics in the composite case. The approach is based on the Chinese Remainder Theorem, enabling the generalization of character sum bounds. Ultimately, we establish new upper bounds for the pseudorandom measures introduced by Mauduit and Sárközy, specifically the well-distribution and correlation measures.