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[1][2][3][4]. 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[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 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[1].
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")[1].
l-sequences have many excellent statistical properties[1][4] 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. The 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 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 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].
References[]
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 A. Klapper and M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111-147, 1997, [1]
- ↑ 2.0 2.1 R. Couture and P. L’Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pp. 799–808, 1994, [2],
- ↑ M. Goresky and A. Klapper, Algebraic Shift Register Sequences, 2009, [3]
- ↑ 4.0 4.1 M. Goresky and A. Klapper, Efficient Multiply-with-Carry Random Number Generators with Optimal Distribution Properties, ACM Transactions on Modeling and Computer Simulation, vol 13, pp 310-321, 2003, [4]
- ↑ G. Marsaglia and A. Zaman, A new class of random number generators, Annals of Applied Probability, vol 1, pp. 462–480, 1991
- ↑ B. Schneier, Applied Cryptography. John Wiley & Sons, New York, 1996
- ↑ K. Mahler, On a geometrical representation of p–adic numbers, Ann. of Math., vol. 41, pp. 8–56, 1940
- ↑ B. M. M. de Weger, Approximation lattices of p–adic numbers, J. Num. Th., vol 24, pp. 70–88, 1986
- ↑ A. Klapper and J. Xu, Register Synthesis for Algebraic Feedback Shift Registers Based on Non-Primes, Designs, Codes, and Cryptography vo. 31, pp. 227-250", 2004
- ↑ A. Klapper and J. Xu, Algebraic Feedback Shift Registers, Theoretical Computer Science, vol. 226, pp. 61-93, 1999, [5]
|
it:Registri a scorrimento a retroazione con riporto ru:Регистр сдвига с обратной связью по переносу