On the linear complexity of the power generator (Q5939679)

Let \(\vartheta, m\) and \(e\) be integers such that \(\text{gcd}(\vartheta,m) = 1\). Then one can define the sequence \((u_n)\) by \[ u_n \equiv u_{n-1}^e (\bmod m), \quad 0 \leq u_n \leq m-1, n = 1,2,\dots,\tag{pg} \] with the initial value \(u_0 = \vartheta\). This sequence is known as the power generator, and in the two special cases \(\text{gcd}(e,\varphi(m)) = 1\) -- where \(\varphi(m)\) is the Euler function -- and \(e = 2\) the sequence is known as the RSA generator and as the Blum-Blum-Shub generator, respectively. If \(\text{gcd}(e,\varphi) = 1\) then the sequence (pg) is always purely periodic. Otherwise a purely periodic shift of the original sequence is considered. We recall that the linear complexity of an infinite sequence \((s_n)\) with terms in a ring \(\mathcal{R}\) is the length \(L\) of the shortest linear recurrence relation \[ s_{n+L} = a_{L-1}s_{n+L-1}+ \ldots + a_0s_n, \quad n= 1,2,\ldots, \] with \(a_0, \ldots, a_{L-1} \in \mathcal{R}\), which is satisfied by the sequence \((s_n)\). For cryptographic applications a large linear complexity, close to the period length of the sequence, is desirable. For prime modulus \(m = p\) for the considered sequence (pg) with period \(t\) the author obtains the lower bound \(L \geq t^2/(p-1)\), and for the important case that \(m = pl\) where \(p\) and \(l\) are distinct primes (such integers are also called Blum integers) it is shown that the linear complexity of the sequence (pg) with period \(t\) is at least \(t/\varphi(m)^{-1/2}\). The paper is strongly related with [IEEE Trans. Inf. Theory 46, 2159-2162 (2000; Zbl 0997.94012)] by \textit{F. Griffin} and the author, where bounds on the linear complexity profile (i.e. the length of the shortest recurrence relation satisfied by the first \(n\) terms of the sequence) of the power generator are provided.