Feedback with Carry Shift Registers. In sequence design, a Feedback with Carry Shift Register (or FCSR) is the arithmetic or with carry analog of a linear-feedback shift register (LFSR).  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 (such as the F-FCSR generator), in the cryptanalysis of the summation combiner stream cipher (the reason Goresky and Klapper invented them), and in generating pseudorandom numbers for quasi-Monte Carlo (under the name Multiply With Carry (MWC) generator - invented by Couture and L'Ecuyer,) 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 (for "long 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 (called the N-adic complexity of 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 (AFSRs) 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.

References

Stream ciphers
Digital registers
Cryptographic algorithms
Pseudorandom number generators