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 [math]\displaystyle{ N \gt 1 }[/math] is an integer, then an N-ary FCSR of length [math]\displaystyle{ r }[/math] is a finite state device with a state [math]\displaystyle{ (a;z) = (a_0,a_1,\dots,a_{r-1};z) }[/math] consisting of a vector of elements [math]\displaystyle{ a_i }[/math] in [math]\displaystyle{ \{0,1,\dots,N-1\}=S }[/math] and an integer [math]\displaystyle{ z }[/math]. The state change operation is determined by a set of coefficients [math]\displaystyle{ q_1,\dots,q_n }[/math] and is defined as follows: compute [math]\displaystyle{ s = q_r a_0+q_{r-1} a_1+\dots+q_1 a_{r-1} + z }[/math]. Express s as [math]\displaystyle{ s = a_r + N z' }[/math] with [math]\displaystyle{ a_r }[/math] in [math]\displaystyle{ S }[/math]. Then the new state is [math]\displaystyle{ (a_1,a_2,\dots,a_r; z') }[/math]. By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in [math]\displaystyle{ S }[/math].

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 [math]\displaystyle{ q = q_r N^r + \dots + q_1 N^1 - 1 }[/math]. Associated with the output sequence is the N-adic number [math]\displaystyle{ a = a_0 + a_1 N + a_2N^2+\dots }[/math] The fundamental theorem of FCSRs says that there is an integer [math]\displaystyle{ u }[/math] so that [math]\displaystyle{ a = u/q }[/math], a rational number. The output sequence is strictly periodic if and only if [math]\displaystyle{ u }[/math] is between [math]\displaystyle{ -q }[/math] and [math]\displaystyle{ 0 }[/math]. It is possible to express u as a simple quadratic polynomial involving the initial state and the q_i.

There is also an exponential representation of FCSRs: if [math]\displaystyle{ g }[/math] is the inverse of [math]\displaystyle{ N \pmod q }[/math], and the output sequence is strictly periodic, then [math]\displaystyle{ a_i = (A g_i \bmod q) \bmod N }[/math], where [math]\displaystyle{ A }[/math] 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. In this case, the period is [math]\displaystyle{ q-1 }[/math]. 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 [math]\displaystyle{ N=2 }[/math]; by a variant of the Euclidean algorithm when N 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 [math]\displaystyle{ 2L }[/math] 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 R and N is replaced by an arbitrary non-unit in R. A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book.