# Feedback with Carry Shift Registers

This is the approved revision of this page, as well as being the most recent.
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 N-ary FCSR of length $r$ is a finite state device with a state $(a;z) = (a_0,a_1,\dots,a_{r-1};z)$ consisting of a vector of elements $a_i$ in $\{0,1,\dots,N-1\}=S$ and an integer $z$.
FCSRs are analyzed using number theory. Associated with the FCSR is a connection integer $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_2N^2+\dots$ 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 qi. 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$; 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 $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.