Abstract:
In this paper we construct a pseudorandom multisequence $(x_{n_1,...,n_r})$ based on $k$th-order linear recurrences modulo $p$, such that the discrepancy of the $s$-dimensional multisequence $(x_{n_1+i_1,...,n_r+i_r})_{1 \leq i_j \leq s_j, 1 \leq j \leq r}$ $1 \leq n_j \leq N_j, 1 \leq j \leq r$ is equal to $O((N_1 ... N_r)^{-1/2} \ln^{s+3r}(N_1 ... N_r))$, where $s=s_1 ... s_r$, for all $N_1,...,N_r$ with $1 < N_1 ... N_r \leq p^k

Abstract:
In this paper, we focus on analyzing the period distribution of the inversive pseudorandom number generators (IPRNGs) over finite field $({\rm Z}_{N},+,\times)$, where $N>3$ is a prime. The sequences generated by the IPRNGs are transformed to 2-dimensional linear feedback shift register (LFSR) sequences. By employing the generating function method and the finite field theory, the period distribution is obtained analytically. The analysis process also indicates how to choose the parameters and the initial values such that the IPRNGs fit specific periods. The analysis results show that there are many small periods if $N$ is not chosen properly. The experimental examples show the effectiveness of the theoretical analysis.

Abstract:
It is shown how correlations in the generalized feedback shift-register (GFSR) random-number generator are greatly diminished when the number of feedback taps is increased from two to four (or more) and the tap offsets are lengthened. Simple formulas for producing maximal-cycle four-tap rules from available primitive trinomials are given, and explicit three- and four-point correlations are found for some of those rules. A number of generators are also tested using a simple but sensitive random-walk simulation that relates to a problem in percolation theory. While virtually all two-tap generators fail this test, four-tap generators with offset greater than about 500 pass it, have passed tests carried out by others, and appear to be good multi-purpose high-quality random-number generators.

Abstract:
We report large systematic errors in Monte Carlo simulations of the tricritical Blume-Capel model using single spin Metropolis updating. The error, manifest as a $20\%$ asymmetry in the magnetisation distribution, is traced to the interplay between strong triplet correlations in the shift register random number generator and the large tricritical clusters. The effect of these correlations is visible only when the system volume is a multiple of the random number generator lag parameter. No such effects are observed in related models.

Abstract:
This paper investigates the impact of the changes of the characteristic polynomials and initial loadings, on behaviour of aliasing errors of parallel signature analyzer (Multi-Input Shift Register), used in an LFSR based digital circuit testing technique. The investigation is carried-out through an extensive simulation study of the effectiveness of the LFSR based digital circuit testing technique. The results of the study show that when the identical characteristic polynomials of order n are used in both pseudo-random test-pattern generator, as well as in Multi-Input Shift Register (MISR) signature analyzer (parallel type) then the probability of aliasing errors remains unchanged due to the changes in the initial loadings of the pseudo-random test-pattern generator.

Abstract:
This paper investigates the impact of the changes of the characteristic polynomials and initial loadings, on behaviour of aliasing errors of parallel signature analyzer (Multi-Input Shift Register), used in an LFSR based digital circuit testing technique. The investigation is carried-out through an extensive simulation study of the effectiveness of the LFSR based digital circuit testing technique. The results of the study show that when the identical characteristic polynomials of order n are used in both pseudo-random test-pattern generator, as well as in Multi-Input Shift Register (MISR) signature analyzer (parallel type) then the probability of aliasing errors remains unchanged due to the changes in the initial loadings of the pseudo-random test-pattern generator.

Abstract:
In a pioneering classic, Warren McCulloch and Walter Pitts proposed a model of the central nervous system; motivated by EEG recordings of normal brain activity, Chv\' atal and Goldsmith asked whether or not this model can be engineered to provide pseudorandom number generators. We supply evidence suggesting that the answer is negative.

Abstract:
We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length O(log (n/epsilon)) for error epsilon. Previously, only constructions with seed-length O(\log^{3/2} n) or O(\log^2 n) were known for these classes with polynomially small error. The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces.

Abstract:
Este artículo presenta un estudio sobre la construcción de generadores de secuencias pseudoaleatorias. Se muestra que al combinar un lenguaje de descripción de hardware, con el resultado que produce el algoritmo de Berlekamp-Massey, se puede dise ar e implementar en un circuito reprogramable la función de un Registro de Desplazamiento con Retroalimentación Lineal. Se presenta también el dise o del Generador Multivelocidad utilizando combinaciones de la función generada, así como también su simulación utilizando las herramientas que proporciona ALTERA TM. Inicialmente, se explica el uso de polinomios primitivos en la construcción de Registros de Desplazamiento con Retroalimentación Lineal y se muestra la debilidad de utilizar uno solo en la generación de secuencias pseudoaleatorias. Esto último justifica el uso de arreglos de Registros para su uso en cifradores de flujo. This article presents a study on the construction of pseudorandom sequence generators. It is shown that by combining a hardware description language and the result of the Berlekamp-Massey algorithm, the function of a linear feedback shift register can be produced and implemented in a reprogrammable chip. It also shows the design of the Multispeed Generator using combinations of the generated function, and its simulation using tools provided by ALTERA TM. Initially, we explain the use of primitive polynomials in the construction of linear feedback shift registers, and show the weakness of using only one in the generation of pseudorandom sequences. The latter justifies the use of registers on stream ciphers.

Abstract:
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/eps^{O(d)} fooling degree d PTFs with error at most eps. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error eps. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter eps and obtain a PRG with seed-length O(log n + log^2(1/eps)). Previously, only PRGs with seed length O(log n log^2(1/eps)/eps^2) were known for halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the n-dimensional unit sphere. The main theme of our constructions and analysis is the use of invariance principles to construct pseudorandom generators. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate eps for halfspaces. These techniques may be of independent interest.