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 (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 . 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 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 .

There are efficient 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.

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.

Source

http://wikipedia.org/

See Also on BitcoinWiki