FANDOM


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

ReferencesEdit

  1. 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. 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],
  3. M. Goresky and A. Klapper, Algebraic Shift Register Sequences, 2009, [3]
  4. 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]
  5. G. Marsaglia and A. Zaman, A new class of random number generators, Annals of Applied Probability, vol 1, pp. 462–480, 1991
  6. B. Schneier, Applied Cryptography. John Wiley & Sons, New York, 1996
  7. K. Mahler, On a geometrical representation of p–adic numbers, Ann. of Math., vol. 41, pp. 8–56, 1940
  8. B. M. M. de Weger, Approximation lattices of p–adic numbers, J. Num. Th., vol 24, pp. 70–88, 1986
  9. 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
  10. 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:Регистр сдвига с обратной связью по переносу

Community content is available under CC-BY-SA unless otherwise noted.