History

Please fill in your query. A complete syntax description you will find on the General Help page.
On pseudorandom sequences and their application. (English)
Ahlswede, Rudolf (ed.) et al., General theory of information transfer and combinatorics. Berlin: Springer (ISBN 978-3-540-46244-6/pbk). Lecture Notes in Computer Science 4123, 343-361 (2006).
The authors analyze a family of finite binary sequences $E_N$ of length $N$. Two measures of pseudorandomness have been introduced by {\it C. Mauduit} and {\it A. Sárközy} in [Acta Arith. 82, 365‒377 (1997; Zbl 0886.11048)]: the well-distribution measure $W(E_N)$ and the correlation measure of order $k$, $C_k(E_N)$. A construction of sequences $E_N$ has been proposed in the same article. It depends on a parameter $p$ (an odd prime) and uses the Legendre symbol. An extended construction (called $Q$-sequences) has been given by Goubin, {\it C. Mauduit} and {\it A. Sárközy} in [J. Number Theory 106, 56‒69 (2004; Zbl 1049.11089)]: it depends on a polynomial seed $f(x) \in \mathbb{F}_p [x]$. In the same article, the measures $W(E_p)$ and $C_{\ell}(E_p)$ (for some integer $\ell$) of a $Q$-sequence have been bounded. Five basis tests of randomness are well known (see for instance [{\it A. J. Menezes, P. C. van Oorschot} and {\it S. A. Vanstone}, Handbook of applied cryptography. CRC Press Series on Discrete Mathematics and its Applications. Boca Raton, FL: CRC Press (1997; Zbl 0868.94001)]): frequency test, serial test, poker test, runs test, and autocorrelation test. Four of the five statistics used $X_i$, $i \in \{1,2,4,5 \}$ are bounded in the present article, for all binary sequences: the upper bounds use the measures $W(E_N)$ and $C_k(E_N)$, for some integer $k$. Bounds for $Q$-sequences can then be derived. Optimal choices of the parameters $p$ and $f(x)$ are discussed. It is shown that the selected family is reasonably large for cryptographic applications. A running time analysis is performed and the result of a numerical example for a small $p$ and a polynomial $f(x)$ of small degree is given.
Reviewer: Christian Lecot (Le Bourget-du-Lac)