Feedback with Carry Shift Registers: Difference between revisions
KolbertBot (talk | contribs) m Bot: HTTP→HTTPS |
Upgrade the first few references. Still more to be done. |
||
Line 1: | Line 1: | ||
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>.<ref name="FCSR1"> |
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>.<ref name="FCSR1">{{cite journal |
||
|first1=Andrew |last1=Klapper |first2=Mark |last2=Goresky |
|||
|title=Feedback Shift Registers, 2-Adic Span, and Combiners With Memory |
|||
|journal=Journal of Cryptology |volume=10 |issue=2 |pages=111–147 |date=March 1997 |
|||
|url=http://cs.engr.uky.edu/~klapper/pdf/fcsr.pdf |
|||
|citeseerx=10.1.1.37.5637 |doi=10.1007/s001459900024 |
|||
}}</ref><ref name="LEcuyer">{{cite journal |
|||
|first1=Raymond |last1=Couture |first2=Pierre |last2=L’Ecuyer |
|||
|title=On the lattice structure of certain linear congruential sequences related to AWC/SWB generators |
|||
|journal=Mathematics of Computation |volume=62 |issue=206 |pages=799–808 |date=April 1994 |
|||
|doi=10.2307/2153540 |doi-access=free |
|||
|url=http://www.ams.org/journals/mcom/1994-62-206/S0025-5718-1994-1220826-X/S0025-5718-1994-1220826-X.pdf |
|||
}}</ref><ref name="efficient MWC">{{cite journal |
|||
|first1=Mark |last1=Goresky |first2=Andrew |last2=Klapper |
|||
|title=Efficient Multiply-with-Carry Random Number Generators with Optimal Distribution Properties |
|||
|journal=ACM Transactions on Modeling and Computer Simulation |volume=13 |issue=4 |pages=310–321 |date=October 2003 |
|||
|url=https://www.math.ias.edu/~goresky/pdf/p1-goresky.pdf |
|||
|citeseerx=10.1.1.22.9007 |doi= |
|||
}}</ref><ref name="AFSR book"/> The state change operation is determined by a set of coefficients <math>q_1,\dots,q_n</math> and is defined as follows: compute <math>s = q_r a_0+q_{r-1} a_1+\dots+q_1 a_{r-1} + z</math>. Express s as <math>s = a_r + N z'</math> with <math>a_r</math> in <math>S</math>. Then the new state is <math>(a_1,a_2,\dots,a_r; z')</math>. By iterating the state change an FCSR generates an infinite, eventually period sequence of numbers in <math>S</math>. |
|||
FCSRs have been used in the design of [[stream ciphers]] (such as the [[F-FCSR]] generator), in the cryptanalyis of the [[summation generator|summation combiner]] stream cipher (the reason Goresky and Klapper invented them<ref name="FCSR1" />), and in generating [[Pseudorandomness|pseudorandom numbers]] for [[Quasi-Monte Carlo method|quasi-Monte Carlo]] (under the name [[Multiply-with-carry|Multiply With Carry]] (MWC) generator - invented by Couture and L'Ecuyer,<ref name="LEcuyer"/>) generalizing work of Marsaglia and Zaman.<ref name="MZ">G. Marsaglia and A. Zaman, ''A new class of random number generators, Annals of Applied Probability, vol 1, pp. 462–480'', 1991</ref> |
FCSRs have been used in the design of [[stream ciphers]] (such as the [[F-FCSR]] generator), in the cryptanalyis of the [[summation generator|summation combiner]] stream cipher (the reason Goresky and Klapper invented them<ref name="FCSR1" />), and in generating [[Pseudorandomness|pseudorandom numbers]] for [[Quasi-Monte Carlo method|quasi-Monte Carlo]] (under the name [[Multiply-with-carry|Multiply With Carry]] (MWC) generator - invented by Couture and L'Ecuyer,<ref name="LEcuyer"/>) generalizing work of Marsaglia and Zaman.<ref name="MZ">G. Marsaglia and A. Zaman, ''A new class of random number generators, Annals of Applied Probability, vol 1, pp. 462–480'', 1991</ref> |
Revision as of 21:15, 30 October 2017
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 is an integer, then an N-ary FCSR of length is a finite state device with a state consisting of a vector of elements in and an integer .[1][2][3][4] The state change operation is determined by a set of coefficients and is defined as follows: compute . Express s as with in . Then the new state is . By iterating the state change an FCSR generates an infinite, eventually period sequence of numbers in .
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 . Associated with the output sequence is the N-adic number The fundamental theorem of FCSRs says that there is an integer so that , a rational number. The output sequence is strictly periodic if and only if is between and . 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 is the inverse of , and the output sequence is strictly periodic, then , where 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. In this case, the period is . In this case the output sequence is called an l-sequence (for "long sequence").[1]
l-sequences have many excellent statistical properties[1][3] 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. They 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 ;[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 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] A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book.[4]
References
- ^ a b c d e f Klapper, Andrew; Goresky, Mark (March 1997). "Feedback Shift Registers, 2-Adic Span, and Combiners With Memory" (PDF). Journal of Cryptology. 10 (2): 111–147. CiteSeerX 10.1.1.37.5637. doi:10.1007/s001459900024.
- ^ a b Couture, Raymond; L’Ecuyer, Pierre (April 1994). "On the lattice structure of certain linear congruential sequences related to AWC/SWB generators" (PDF). Mathematics of Computation. 62 (206): 799–808. doi:10.2307/2153540.
- ^ a b Goresky, Mark; Klapper, Andrew (October 2003). "Efficient Multiply-with-Carry Random Number Generators with Optimal Distribution Properties" (PDF). ACM Transactions on Modeling and Computer Simulation. 13 (4): 310–321. CiteSeerX 10.1.1.22.9007.
- ^ a b M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge University Press, 2012 ISBN 9781107014992
- ^ 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, [1]