In this paper, the authors continue a program to find arithmetic, or “with-carry,” analogs of polynomial-based phenomena that appear in the design and analysis of cryptosystems and other branches of digital computation and communications. They construct arithmetic analogs of the Walsh-Hadamard transform and correlation functions of Boolean functions. These play central roles in the cryptographic analysis of block ciphers and stream ciphers. After making basic definitions and constructing various algebraic tools they: 1) show how to realize arithmetic correlations as cardinalities of intersections of hypersurfaces; 2) show that the arithmetic Walsh spectrum characterizes a Boolean function; 3) study the average behavior of arithmetic Walsh transforms; and 4) find the arithmetic Walsh transforms of linear and affine functions.

Over the past half century, various statistical properties of pseudorandom sequences have played important roles in a variety of applications. Among these properties are Golomb's randomness conditions: (R1) balance, (R2) run property, and (R3) ideal autocorrelations, as well as the closely related properties (R4) shift and add, and (R5) de Bruin (uniform distribution of subblocks). The purpose of this paper is to describe the relationships among these conditions, and to introduce a new method for generating sequences with all these properties, using algebraic feedback shift registers.

Maximal length feedback with carry shift register sequences have several remarkable statistical properties. Among them is the property that the arithmetic correlations between any two cyclically distinct decimations are precisely zero. It is open, however, whether all such pairs of decimations are indeed cyclically distinct. In this paper we show that the set of distinct decimations is large and, in some cases, all decimations are distinct.

A feedback-with-carry shift register (FCSR) with "Fibonacci" architecture is a shift register provided with a small amount of memory which is used in the feedback algorithm. Like the linear feedback shift register (LFSR), the FCSR provides a simple and predictable method for the fast generation of pseudorandom sequences with good statistical properties and large periods. In this paper, we describe and analyze an alternative architecture for the FCSR which is similar to the "Galois" architecture for the LFSR. The Galois architecture is more efficient than the Fibonacci architecture because the feedback computations are performed in parallel. We also describe the output sequences generated by the d-FCSR, a slight modification of the (Fibonacci) FCSR architecture in which the feedback bit is delayed for d clock cycles before being returned to the first cell of the shift register. We explain how these devices may be configured so as to generate sequences with large periods. We show that the d-FCSR also admits a more efficient "Galois" architecture.

An arithmetic or with-carry analog of Blahut's (1979) theorem is presented. This relates the length of the smallest feedback with-carry shift register to the number of nonzero classical Fourier coefficients of a periodic binary sequence.

An arithmetic version of the crosscorrelation of two sequences is defined, generalizing Mandelbaum's (1967) arithmetic autocorrelations. Large families of sequences are constructed with ideal (vanishing) arithmetic crosscorrelations. These sequences are decimations of the 2-adic expansions of rational numbers p/q such that 2 is a primitive root module q.

For a binary pseudorandom sequence {S/sub i/} with period N, the partial period autocorrelation function A/sub S/(/spl tau/,k,D) is defined by correlating the portion of the sequence within a window of size D, and start position k, with the portion in another window of the same size but starting /spl tau/ steps later in the sequence. A distribution of possible partial period autocorrelation values is obtained by allowing the start position K to vary over all possible values O/spl les/k>

Pseudorandom binary sequences with high linear complexity and low correlation function values are sought in many applications of modern communication systems. A new family of pseudorandom binary sequences, cascaded GMW sequences, is constructed. These sequences are shown to share many desirable correlation properties with the GMW sequences of B. Gordon, W.A. Mills, and L.R. Welch (1962)-for example, high-shifted autocorrelation values and, in many cases, three-valued cross-correlation values with m-sequences. It is shown, moreover, that in many cases the linear complexities of cascaded GMW sequences are far greater than those of GMW sequences.>

Sequences generated by arbitrary feedback registers (not necessarily feedback shift registers) with arbitrary feedforward functions are studied. The definition of linear complexity of a sequence is generalized to the notions of strong and weak linear complexity of feedback registers. A technique for finding upper bounds for the strong linear complexities of such registers is developed. This technique is applied to several classes of registers. It is shown that a feedback shift register in which the feedback function is of the form x/sub 1/+h(x/sub 2/, . . . , x/sub n/) can generate long periodic sequences with high linear complexities only if its linear and quadratic terms have certain specific forms.>