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 N > 1 {displaystyle N>1} is an integer, then an N-ary FCSR of length r {displaystyle r} is a finite state device with a state ( a ; z ) = ( a 0 , a 1 , … , a r − 1 ; z ) {displaystyle (a;z)=(a_{0},a_{1},dots ,a_{r-1};z)} consisting of a vector of elements a i {displaystyle a_{i}} in { 0 , 1 , … , N − 1 } = S {displaystyle {0,1,dots ,N-1}=S} and an integer z {displaystyle z} . The state change operation is determined by a set of coefficients q 1 , … , q n {displaystyle q_{1},dots ,q_{n}} and is defined as follows: compute s = q r a 0 + q r − 1 a 1 + ⋯ + q 1 a r − 1 + z {displaystyle s=q_{r}a_{0}+q_{r-1}a_{1}+dots +q_{1}a_{r-1}+z} . Express s as s = a r + N z ′ {displaystyle s=a_{r}+Nz'} with a r {displaystyle a_{r}} in S {displaystyle S} . Then the new state is ( a 1 , a 2 , … , a r ; z ′ ) {displaystyle (a_{1},a_{2},dots ,a_{r};z')} . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in S {displaystyle S} . 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 {displaystyle N>1} is an integer, then an N-ary FCSR of length r {displaystyle r} is a finite state device with a state ( a ; z ) = ( a 0 , a 1 , … , a r − 1 ; z ) {displaystyle (a;z)=(a_{0},a_{1},dots ,a_{r-1};z)} consisting of a vector of elements a i {displaystyle a_{i}} in { 0 , 1 , … , N − 1 } = S {displaystyle {0,1,dots ,N-1}=S} and an integer z {displaystyle z} . The state change operation is determined by a set of coefficients q 1 , … , q n {displaystyle q_{1},dots ,q_{n}} and is defined as follows: compute s = q r a 0 + q r − 1 a 1 + ⋯ + q 1 a r − 1 + z {displaystyle s=q_{r}a_{0}+q_{r-1}a_{1}+dots +q_{1}a_{r-1}+z} . Express s as s = a r + N z ′ {displaystyle s=a_{r}+Nz'} with a r {displaystyle a_{r}} in S {displaystyle S} . Then the new state is ( a 1 , a 2 , … , a r ; z ′ ) {displaystyle (a_{1},a_{2},dots ,a_{r};z')} . By iterating the state change an FCSR generates an infinite, eventually periodic sequence of numbers in S {displaystyle S} . 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 q = q r N r + ⋯ + q 1 N 1 − 1 {displaystyle q=q_{r}N^{r}+dots +q_{1}N^{1}-1} . Associated with the output sequence is the N-adic number a = a 0 + a 1 N + a 2 N 2 + … {displaystyle a=a_{0}+a_{1}N+a_{2}N^{2}+dots } The fundamental theorem of FCSRs says that there is an integer u {displaystyle u} so that a = u / q {displaystyle a=u/q} , a rational number. The output sequence is strictly periodic if and only if u {displaystyle u} is between − q {displaystyle -q} and 0 {displaystyle 0} . 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 g {displaystyle g} is the inverse of N ( mod q ) {displaystyle N{pmod {q}}} , and the output sequence is strictly periodic, then a i = ( A g i mod q ) mod N {displaystyle a_{i}=(Ag_{i}{mod {q}}){mod {N}}} , where A {displaystyle 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. In this case, the period is q − 1 {displaystyle q-1} . 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 N = 2 {displaystyle N=2} ; 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 2 L {displaystyle 2L} 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.