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 N >1 is an integer, then an Nary FCSR of length r is a finite state device with a state (a;z) = (a_{0},a_{1},...,a_{r1};z) consisting of a vector of elements a_{i} in {0,1,...,N1}=S and an integer z^{[1]}^{[2]}^{[3]}^{[4]}. The state change operation is determined by a set of coefficients q_{1},...,q_{n} and is defined as follows: compute s = q_{r}a_{0}+q_{r1}a_{1}+..+q_{1}a_{r1} + z. Express s as s = a_{r}+Nz' with a_{r} in S. Then the new state is (a_{1},a_{2},...,a_{r};z'). By iterating the state change an FCSR generates an infinite, eventually period sequence of numbers in S.
FCSRs have been used in the design of stream ciphers (such as the FFCSR generator), in the cryptanalyis of the summation combiner stream cipher (the reason Goresky and Klapper invented them^{[1]}), and in generating pseudorandom numbers for quasiMonte Carlo (under the name Multiply With Carry (MWC) generator  invented by Couture and L'Ecuyer^{[2]}, generalizing work of Marsaglia and Zaman^{[5]}.
FCSRs are analyzed using number theory. Associated with the FCSR is a connection integer q = q_{r}N^{r} + ... + q_{1}N  1. Associated with the output sequence is the Nadic number a = a_{0} + a_{1}N + a_{2}N^{2}+.... The fundamental theorem of FCSRs says that there is an integer u so that a = u/q, a rational number. The output sequence is strictly periodic if and only if u is between q and 0. It is possible to express u as a simple quadratic polynomial involving the initial state and the q_{i}^{[1]}.
There is also an exponential representation of FCSRs: if g is the inverse of N modulo q, and the output sequence is strictly periodic, then a_{i} = (Ag^{i} mod q) mod N, where A is an integer. It follows that the period is at most the order of N in the multiplicative group of units modulo q. This is maximized when q is prime and N is a primitive element modulo q. Then the period is q1. In this case the output sequence is called an lsequence (for "long sequence")^{[1]}.
lsequences have many excellent statistical properties^{[1]}^{[4]} that make them candidates for use in applications^{[6]}, including near uniform distribution of subblocks, ideal arithmetic autocorrelations, and the arithmetic shift and add property. The are the withcarry analog of msequences 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^{[7]} and De Weger's^{[8]} lattice based analysis of Nadic numbers when N=2^{[1]}; by a variant of the Euclidean algorithm when N is prime; and in general by Xu's adaptation of the BerlekampMassey algorithm^{[9]}. If L is the size of the smallest FCSR that outputs the sequence (called the Nadic complexity of the sequence), then all these algorithms require a prefix of length about 2L to be successful and have quadratic time complexity. It follows that, as with LFSRs and linear complexity, any stream cipher whose Nadic 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 R and N is replaced by an arbitrary nonunit in R^{[10]}.
ReferencesEdit
 ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} ^{1.4} ^{1.5} A. Klapper and M. Goresky, Feedback Shift Registers, 2Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111147, 1997, [1]
 ↑ ^{2.0} ^{2.1} R. Couture and P. L’Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pp. 799–808, 1994, [2],
 ↑ M. Goresky and A. Klapper, Algebraic Shift Register Sequences, 2009, [3]
 ↑ ^{4.0} ^{4.1} M. Goresky and A. Klapper, Efficient MultiplywithCarry Random Number Generators with Optimal Distribution Properties, ACM Transactions on Modeling and Computer Simulation, vol 13, pp 310321, 2003, [4]
 ↑ G. Marsaglia and A. Zaman, A new class of random number generators, Annals of Applied Probability, vol 1, pp. 462–480, 1991
 ↑ B. Schneier, Applied Cryptography. John Wiley & Sons, New York, 1996
 ↑ K. Mahler, On a geometrical representation of p–adic numbers, Ann. of Math., vol. 41, pp. 8–56, 1940
 ↑ B. M. M. de Weger, Approximation lattices of p–adic numbers, J. Num. Th., vol 24, pp. 70–88, 1986
 ↑ A. Klapper and J. Xu, Register Synthesis for Algebraic Feedback Shift Registers Based on NonPrimes, Designs, Codes, and Cryptography vo. 31, pp. 227250", 2004
 ↑ A. Klapper and J. Xu, Algebraic Feedback Shift Registers, Theoretical Computer Science, vol. 226, pp. 6193, 1999, [5]
