FCSR序列的伪随机性及线性复杂度
|
摘要
带进位反馈移位寄存器序列简称FCSR序列，其中最重要的是极大周期FCSR序列，即l-序列．它有许多类似于m-序列的伪随机性质．令q=p~e，若2为模q的本原元，则以q为联接数的极大周期FCSR序列是l-序列，周期为T=φ(q)．
本文首先研究了l-序列在部分周期中(即一个周期内任意连续一段)的0、1分布，给出了估计值，指出当寄存器的级数较大时，其0、1个数大约各占一半．特别的，若联接数为素数p，则l-序列在长为μT(0＜μ＜1)的任意一段中出现1的个数所占的比例(?)(1)满足：
其次讨论了l-序列的线性复杂度，指出它有紧的上界T／2+1，并给出了一个下界．特别当e≥2时，其线性复杂度有下界2~(t-1)+1+T／p，其中2~t‖(p-1)．
FCSR sequences are the abbreviation for feedback with carry shift register sequences. Among these, the most important are maximum-period FCSR sequences, that is, l-sequences. They have many good pseudorandom properties similar to m-sequences. Set q =pe, if 2 is a primitive element modulo q, then the maximum-period sequence generated by a FCSR with connection integer q is an l-sequence, with period T= (q).
In this paper, the distribution of 0 and 1 in a partial period of l-sequences, that is, in a segment shorter than the period, is estimated. It was showed that the 0.'s and 1 's are almost equal when the size of the register is large enough. In particular, if the connection integer is a prime number p, then the proportion of 1's in a segment of l-sequence with length T(0< <1) satisfies
Next the linear complexity of l-sequences is discussed. A tight upper bound (772 + 1) and a lower bound are presented. It is showed that if e 2, then the linear complexity of the l-sequence
is at least 2t-1 +l + T/p, where 2t|| (p-1).
本文首先研究了l-序列在部分周期中(即一个周期内任意连续一段)的0、1分布，给出了估计值，指出当寄存器的级数较大时，其0、1个数大约各占一半．特别的，若联接数为素数p，则l-序列在长为μT(0＜μ＜1)的任意一段中出现1的个数所占的比例(?)(1)满足：
其次讨论了l-序列的线性复杂度，指出它有紧的上界T／2+1，并给出了一个下界．特别当e≥2时，其线性复杂度有下界2~(t-1)+1+T／p，其中2~t‖(p-1)．
FCSR sequences are the abbreviation for feedback with carry shift register sequences. Among these, the most important are maximum-period FCSR sequences, that is, l-sequences. They have many good pseudorandom properties similar to m-sequences. Set q =pe, if 2 is a primitive element modulo q, then the maximum-period sequence generated by a FCSR with connection integer q is an l-sequence, with period T= (q).
In this paper, the distribution of 0 and 1 in a partial period of l-sequences, that is, in a segment shorter than the period, is estimated. It was showed that the 0.'s and 1 's are almost equal when the size of the register is large enough. In particular, if the connection integer is a prime number p, then the proportion of 1's in a segment of l-sequence with length T(0< <1) satisfies
Next the linear complexity of l-sequences is discussed. A tight upper bound (772 + 1) and a lower bound are presented. It is showed that if e 2, then the linear complexity of the l-sequence
is at least 2t-1 +l + T/p, where 2t|| (p-1).
引文
[1] David M. Mandelbaum, Arithmetic codes with large distance, IEEE Trans. on Information Theory, vol. 38, No.5, April 1967, pp. 237-242.
[2] A. Klapper and M. Goresky, 2-adic shift registers, Fast Software Encryption, LNCS 809, Springer Verlag, N.Y.,1994, pp. 174-178.
[3] M. Goresky and A. Klapper, Feedback registers based on ramified extensions of the 2-adic numbers, Advances in Cryptology - Eurocrypt 1994, LNCS 718, Springer Verlag, N.Y., 1994, pp. 215-222.
[4] A. Klapper, Feedback with carry shift registers over finite fields, Fast Software Encryption, LNCS 1008, Springer Verlag, N.Y., 1995, pp. 170-178.
[5] A. Klapper and M. Goresky, Large period nearly deBrujin FCSR sequences. Advances in Cryptology - Eurocrypt 1995, LNCS 921, Springer Verlag, N.Y., 1995, pp. 263-273.
[6] A. Klapper and M. Goresky, Cryptanalysis based on 2-adic rational approximation, Advances in Cryptology - Crypto 1995, LNCS 963, Springer Verlag, N.Y., 1995, pp. 262-273.
[7] A. Kiapper and M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptology 10 (1997), pp. 111-147.
[8] A. Kiapper and M. Goresky, Arithmetic cross-correlation of FCSR Sequences, IEEE Trans. on Information Theory, vol. 36 (1997), pp. 1142-1146.
[9] A. Klapper and J. Xu, Algebric feedback shift registers, Theoretical Computer Science, 226(1999), pp. 61-93.
[10] M. Goresky and A. Klapper, Fourier transforms and the 2-adic span of periodic binary sequences, IEEE Trans. on Information Theory, vol. 46, No.2, March 2000, pp. 687-691.
[11] C.Seo, S.Lee, Y.Sung, K.Han and S.Kim, A lower bound on the linear span of an FCSR, IEEE Trans. on Information Theory, vol.46, No.2, March 2000, pp. 691-693.
[12] Mark Goresky, Andrew Klapper, Periodicity, correlation, and distribution properties of d-FCSR sequences, see http://www.math.ias.edu/～goresky/Ramif2.pdf.
[13] M. Goresky and A. Klapper, Fibonacci and Galois representations of feedback-with-carry
shift registers, IEEE Trans. on Information Theory, vol.48 (2002), pp.2826-2836.
[14] M. Goresky, A. Ktapper, R. Murty, On the distinctness of decimations of/-sequences, Discrete Mathematics and Computer Science, Springer-Verlag, New York, 2002.
[15] Mark Goresky, Andrew Klapper, Ram Murty, and Igor Shparlinski, On decimations of l-sequences, http://www.math.ias.edu/～goresky/pdf/decimations.pdf.
[16] EV.Kumar and V.K.Wei, Minimum distance of logarithmic and fractional partial m-sequences, IEEE Trans. on Information Theory, vol. 38, No.5, Sep. 1992, pp. 1474-1482.
[17] J.B.Friedlander, D.Lieman and I.E.Shparlinski, On the distribution of the RSA generator. Proc. Inter. Conf. on Sequences and Their Applications (SETA'98), Singapore, Springer-Verlag, London, 1999, pp. 205-212.
[18] J.B.Friedlander and I.E.Shparlinski, On the distribution of the power generator, Mathematics of Computation, vol. 70, Oct. 2001, pp. 1575-1589.
[19] I.E.Shparlinski, On the linear complexity of the power generator, Designs, Codes and Cryptography, 2001, vol.23, pp. 5-10.
[20] R.Lidl and H.Niederreiter, Finite Fields, Encyclopaedia of mathematics and its applications 20, Cambridge University Press, 1983.
[21] N.Koblitz, p-adic Numbers, p-adic analysis, and zeta functions, Springer-Verlag, New York, 1984.
[22] B.M.M. de Weger, Approximation lattices of p-adic numbers, J. Number Theory, 24(1986), pp.70-88.
[23] R.Rueppel, Analysis and Design of Stream Ciphers, Springer Verlag, New York, 1986.
[24] M.J.B. Robshaw, Stream Ciphers, RSA Laboratories Technical Report, TR-701, July 25,1995.
[1] Partial Period Distribution of FCSR Sequences, IEEE Trans. on Information Theory, vol.49, March 2003, pp. 761-765.
[2] On the Linear Complexity of FCSR Sequences, Applied mathematics-A journal of Chinese universities,已被录用。
[2] A. Klapper and M. Goresky, 2-adic shift registers, Fast Software Encryption, LNCS 809, Springer Verlag, N.Y.,1994, pp. 174-178.
[3] M. Goresky and A. Klapper, Feedback registers based on ramified extensions of the 2-adic numbers, Advances in Cryptology - Eurocrypt 1994, LNCS 718, Springer Verlag, N.Y., 1994, pp. 215-222.
[4] A. Klapper, Feedback with carry shift registers over finite fields, Fast Software Encryption, LNCS 1008, Springer Verlag, N.Y., 1995, pp. 170-178.
[5] A. Klapper and M. Goresky, Large period nearly deBrujin FCSR sequences. Advances in Cryptology - Eurocrypt 1995, LNCS 921, Springer Verlag, N.Y., 1995, pp. 263-273.
[6] A. Klapper and M. Goresky, Cryptanalysis based on 2-adic rational approximation, Advances in Cryptology - Crypto 1995, LNCS 963, Springer Verlag, N.Y., 1995, pp. 262-273.
[7] A. Kiapper and M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptology 10 (1997), pp. 111-147.
[8] A. Kiapper and M. Goresky, Arithmetic cross-correlation of FCSR Sequences, IEEE Trans. on Information Theory, vol. 36 (1997), pp. 1142-1146.
[9] A. Klapper and J. Xu, Algebric feedback shift registers, Theoretical Computer Science, 226(1999), pp. 61-93.
[10] M. Goresky and A. Klapper, Fourier transforms and the 2-adic span of periodic binary sequences, IEEE Trans. on Information Theory, vol. 46, No.2, March 2000, pp. 687-691.
[11] C.Seo, S.Lee, Y.Sung, K.Han and S.Kim, A lower bound on the linear span of an FCSR, IEEE Trans. on Information Theory, vol.46, No.2, March 2000, pp. 691-693.
[12] Mark Goresky, Andrew Klapper, Periodicity, correlation, and distribution properties of d-FCSR sequences, see http://www.math.ias.edu/～goresky/Ramif2.pdf.
[13] M. Goresky and A. Klapper, Fibonacci and Galois representations of feedback-with-carry
shift registers, IEEE Trans. on Information Theory, vol.48 (2002), pp.2826-2836.
[14] M. Goresky, A. Ktapper, R. Murty, On the distinctness of decimations of/-sequences, Discrete Mathematics and Computer Science, Springer-Verlag, New York, 2002.
[15] Mark Goresky, Andrew Klapper, Ram Murty, and Igor Shparlinski, On decimations of l-sequences, http://www.math.ias.edu/～goresky/pdf/decimations.pdf.
[16] EV.Kumar and V.K.Wei, Minimum distance of logarithmic and fractional partial m-sequences, IEEE Trans. on Information Theory, vol. 38, No.5, Sep. 1992, pp. 1474-1482.
[17] J.B.Friedlander, D.Lieman and I.E.Shparlinski, On the distribution of the RSA generator. Proc. Inter. Conf. on Sequences and Their Applications (SETA'98), Singapore, Springer-Verlag, London, 1999, pp. 205-212.
[18] J.B.Friedlander and I.E.Shparlinski, On the distribution of the power generator, Mathematics of Computation, vol. 70, Oct. 2001, pp. 1575-1589.
[19] I.E.Shparlinski, On the linear complexity of the power generator, Designs, Codes and Cryptography, 2001, vol.23, pp. 5-10.
[20] R.Lidl and H.Niederreiter, Finite Fields, Encyclopaedia of mathematics and its applications 20, Cambridge University Press, 1983.
[21] N.Koblitz, p-adic Numbers, p-adic analysis, and zeta functions, Springer-Verlag, New York, 1984.
[22] B.M.M. de Weger, Approximation lattices of p-adic numbers, J. Number Theory, 24(1986), pp.70-88.
[23] R.Rueppel, Analysis and Design of Stream Ciphers, Springer Verlag, New York, 1986.
[24] M.J.B. Robshaw, Stream Ciphers, RSA Laboratories Technical Report, TR-701, July 25,1995.
[1] Partial Period Distribution of FCSR Sequences, IEEE Trans. on Information Theory, vol.49, March 2003, pp. 761-765.
[2] On the Linear Complexity of FCSR Sequences, Applied mathematics-A journal of Chinese universities,已被录用。