In sequence design, a Feedback with Carry Shift Register is the arithmetic or with carry analog of a Linear feedback shift register. If is an integer, then an N-ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer. The state change operation is determined by a set of coefficients and is defined as follows: compute. Express s as with in. Then the new state is. By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in. FCSRs have been used in the design of stream ciphers, in the cryptanalysis of the summation combinerstream cipher, and in generating pseudorandom numbers for quasi-Monte Carlo generalizing work of Marsaglia and Zaman. FCSRs are analyzed using number theory. Associated with the FCSR is a connection integer. Associated with the output sequence is the N-adic number The fundamental theorem of FCSRs says that there is an integer so that, a rational number. The output sequence is strictly periodic if and only if is between and. It is possible to express u as a simple quadratic polynomial involving the initial state and the qi. There is also an exponential representation of FCSRs: if is the inverse of, and the output sequence is strictly periodic, then, where is an integer. It follows that the period is at most the order of in the multiplicative group of units modulo. This is maximized when is prime and is a primitive element modulo. In this case, the period is. In this case the output sequence is called an l-sequence. l-sequences have many excellent statistical properties that make them candidates for use in applications, including near uniform distribution of sub-blocks, ideal arithmetic autocorrelations, and the arithmetic shift and add property. They are the with-carry analog of m-sequences or maximum length sequences. There are efficient algorithms for FCSR synthesis. This is the problem: given a prefix of a sequence, construct a minimal length FCSR that outputs the sequence. This can be solved with a variant of Mahler and De Weger's lattice based analysis of N-adic numbers when ; by a variant of the Euclidean algorithm when is prime; and in general by Xu's adaptation of the Berlekamp-Massey algorithm. If L is the size of the smallest FCSR that outputs the sequence, then all these algorithms require a prefix of length about to be successful and have quadratic time complexity. It follows that, as with LFSRs and linear complexity, any stream cipher whose N-adic complexity is low should not be used for cryptography. FCSRs and LFSRs are special cases of a very general algebraic construction of sequence generators called Algebraic Feedback Shift Registers in which the integers are replaced by an arbitrary ring and is replaced by an arbitrary non-unit in. A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book.
