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 ${\displaystyle N>1}$ is an integer, then an N-ary FCSR of length ${\displaystyle r}$ is a finite state device with a state ${\displaystyle (a;z)=(a_{0},a_{1},\dots ,a_{r-1};z)}$ consisting of a vector of elements ${\displaystyle a_{i}}$ in ${\displaystyle \{0,1,\dots ,N-1\}=S}$ and an integer ${\displaystyle z}$.[1][2][3][4] The state change operation is determined by a set of coefficients ${\displaystyle q_{1},\dots ,q_{n}}$ and is defined as follows: compute ${\displaystyle s=q_{r}a_{0}+q_{r-1}a_{1}+\dots +q_{1}a_{r-1}+z}$. Express s as ${\displaystyle s=a_{r}+Nz'}$ with ${\displaystyle a_{r}}$ in ${\displaystyle S}$. Then the new state is ${\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 ${\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[1]), and in generating pseudorandom numbers for quasi-Monte 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 ${\displaystyle q=q_{r}N^{r}+\dots +q_{1}N^{1}-1}$. Associated with the output sequence is the N-adic number ${\displaystyle a=a_{0}+a_{1}N+a_{2}N^{2}+\dots }$ The fundamental theorem of FCSRs says that there is an integer ${\displaystyle u}$ so that ${\displaystyle a=u/q}$, a rational number. The output sequence is strictly periodic if and only if ${\displaystyle u}$ is between ${\displaystyle -q}$ and ${\displaystyle 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 ${\displaystyle g}$ is the inverse of ${\displaystyle N{\pmod {q}}}$, and the output sequence is strictly periodic, then ${\displaystyle a_{i}=(Ag_{i}{\bmod {q}}){\bmod {N}}}$, where ${\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 ${\displaystyle q-1}$. In this case the output sequence is called an l-sequence (for "long sequence").[1]

l-sequences have many excellent statistical properties[1][3] that make them candidates for use in applications,[6] 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[7] and De Weger's[8] lattice based analysis of N-adic numbers when ${\displaystyle N=2}$;[1] by a variant of the Euclidean algorithm when N is prime; and in general by Xu's adaptation of the Berlekamp-Massey algorithm.[9] 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 ${\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.[10] A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book.[4]

References

1. Klapper, Andrew; Goresky, Mark (March 1997). "Feedback Shift Registers, 2-Adic Span, and Combiners With Memory" (PDF). Journal of Cryptology. 10 (2): 111–147. CiteSeerX 10.1.1.37.5637. doi:10.1007/s001459900024. S2CID 206885831.
2. Couture, Raymond; L’Ecuyer, Pierre (April 1994). "On the lattice structure of certain linear congruential sequences related to AWC/SWB generators" (PDF). Mathematics of Computation. 62 (206): 799–808. doi:10.2307/2153540. JSTOR 2153540.
3. Goresky, Mark; Klapper, Andrew (October 2003). "Efficient Multiply-with-Carry Random Number Generators with Maximal Period" (PDF). ACM Transactions on Modeling and Computer Simulation. 13 (4): 310–321. CiteSeerX 10.1.1.22.9007. doi:10.1145/945511.945514. S2CID 13334372.
4. Goresky, Mark; Klapper, Andrew (2012). Algebraic Shift Register Sequences. Cambridge University Press. ISBN 978-1-107-01499-2. Table of contents.
5. Marsaglia, George; Zaman, Arif (August 1991). "A new class of random number generators" (pdf). Annals of Applied Probability. 1 (3): 462–480. doi:10.1214/aoap/1177005878.
6. Schneier, Bruce (1996). Applied Cryptography. New York: John Wiley & Sons.
7. Mahler, Kurt (January 1940). "On a geometrical representation of p-adic numbers" (PDF). Annals of Mathematics. 2. 41 (1): 8–56. doi:10.2307/1968818. JSTOR 1968818. MR 0001772.
8. de Weger, B. M. M. (September 1986). "Approximation lattices of p–adic numbers" (PDF). Journal of Number Theory. 24 (1): 70–88. doi:10.1016/0022-314X(86)90059-4.
9. Klapper, Andrew; Xu, Jinzhong (March 2004). "Register Synthesis for Algebraic Feedback Shift Registers Based on Non-Primes" (PDF). Designs, Codes, and Cryptography. 31 (3): 227–250. doi:10.1023/B:DESI.0000015886.71135.e1. S2CID 13138878.
10. Klapper, Andrew; Xu, Jinzhong (17 September 1999). "Algebraic Feedback Shift Registers" (PDF). Theoretical Computer Science. 226 (1–2): 61–93. CiteSeerX 10.1.1.36.8645. doi:10.1016/S0304-3975(99)00066-3.