On the linear complexity of the power generator

DOI10.1023/A:1011264815860MaRDI QIDQ5939679zbMATH OpenOpenAlexFDO

Authors Igor E. Shparlinski

Publication date 23 April 2003

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1011264815860

zbMATH Keywords

Blum-Blum-Shub generatorcryptographylinear complexitypower generatorRSA generator

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Review text

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.

Recommendations

• On the linear complexity profile of the power generator
• The linear complexity of binary sequences with period (2/sup n/-1)/sup k/
• On the periods of the linear congruential and power generators
• On the distribution of the power generator
• Period of the power generator and small values of Carmichael's function

Cited in

(13)

• On the elliptic curve endomorphism generator
• On the cycle structure of repeated exponentiation modulo a prime
• On the linear complexity profile of nonlinear congruential pseudorandom number generators with Rédei functions
• On the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials
• On the uniformity of distribution of the RSA pairs
• On the linear complexity profile of the power generator
• On the distribution of the power generator
• Period of the power generator and small values of Carmichael's function
• scientific article; zbMATH DE number 4132085 (Why is no real title available?)
• On the linear complexity profile of some sequences derived from elliptic curves
• Attacking power generators using unravelled linearization: when do we output too much?
• On the power generator and its multivariate analogue
• On the periods of the linear congruential and power generators

This page was built for publication: On the linear complexity of the power generator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5939679)