Feedback with Carry Shift Registers
Encyclopedia
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) = (a0,a1,...,ar-1;z) consisting of a vector of elements ai in {0,1,...,N-1}=S and an integer z. The state change operation is determined by a set of coefficients q1,...,qn and is defined as follows: compute s = qra0+qr-1a1+..+q1ar-1 + z. Express s as s = ar+Nz' with ar in S. Then the new state is (a1,a2,...,ar;z'). By iterating the state change an FCSR generates an infinite, eventually period sequence of numbers in S.
FCSRs have been used in the design of stream ciphers (such as the F-FCSR
generator), in the cryptanalyis 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 = qrNr + ... + q1N - 1. Associated with the output sequence is the N-adic number
a = a0 + a1N + a2N2+.... 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.
There is also an exponential representation of FCSRs: if g is the inverse of N modulo q, and the output sequence is strictly periodic, then ai = (Agi mod q) mod N, where 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. Then the period is 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 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 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 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.
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
(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) = (a0,a1,...,ar-1;z) consisting of a vector of elements ai in {0,1,...,N-1}=S and an integer z. The state change operation is determined by a set of coefficients q1,...,qn and is defined as follows: compute s = qra0+qr-1a1+..+q1ar-1 + z. Express s as s = ar+Nz' with ar in S. Then the new state is (a1,a2,...,ar;z'). By iterating the state change an FCSR generates an infinite, eventually period sequence of numbers in S.
FCSRs have been used in the design of stream ciphers (such as the F-FCSR
F-FCSR
In cryptography, F-FCSR is a stream cipher developed by Thierry Berger, François Arnault, and Cédric Lauradoux. The core of the cipher is a Feedback with Carry Shift Register automaton, which is similar to a LFSR, but they perform operations with carries so their transition function is...
generator), in the cryptanalyis of the summation combiner
Summation generator
The summation generator, created in 1985, by Rainer Rueppel, was a cryptography and security front-runner in the late 1980s. It operates by taking the output of two LFSR's through an adder with carry. The operation's strength is that it is nonlinear. However, through the early 1990s various...
stream cipher (the reason Goresky and Klapper invented them), and in generating pseudorandom numbers
Pseudorandomness
A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process...
for quasi-Monte Carlo
Quasi-Monte Carlo method
In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral that is based on low-discrepancy sequences...
(under the name Multiply With Carry
Multiply-with-carry
In computer science, multiply-with-carry is a method invented by George Marsaglia for generating sequences of random integers based on an initial set of from two to many thousands of randomly chosen seed values...
(MWC) generator - invented by Couture and L'Ecuyer, generalizing work of Marsaglia and Zaman.
FCSRs are analyzed using number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
. Associated with the FCSR is a connection integer q = qrNr + ... + q1N - 1. Associated with the output sequence is the N-adic number
P-adic number
In mathematics, and chiefly number theory, the p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a way different from the extension of the rational number system to the real and complex number systems...
a = a0 + a1N + a2N2+.... 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.
There is also an exponential representation of FCSRs: if g is the inverse of N modulo q, and the output sequence is strictly periodic, then ai = (Agi mod q) mod N, where 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
Primitive root modulo n
In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...
modulo q. Then the period is 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 sequence
Maximum length sequence
A maximum length sequence is a type of pseudorandom binary sequence.They are bit sequences generated using maximal linear feedback shift registers and are so called because they are periodic and reproduce every binary sequence that can be reproduced by the shift registers...
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 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 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.