Feedback with Carry Shift Registers - Revision history

Admin: Created page with "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$
2019-03-21T03:38:03Z

Created page with "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>N >1</..."

New page
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>N >1</math> is an integer, then an N-ary FCSR of length <math>r</math> is a finite state device with a state <math>(a;z) = (a_0,a_1,\dots,a_{r-1};z)</math> consisting of a vector of elements <math>a_i</math> in <math>\{0,1,\dots,N-1\}=S</math> and an integer <math>z</math>.

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

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>N=2</math>; 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>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.

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Cryptography]]
[[Category:Cryptographic algorithms]]