×

Autocorrelations of \(l\)-sequences with prime connection integer. (English) Zbl 1172.94602

Summary: The autocorrelations of \(l\)-sequences with prime connection integer are discussed. Let \(\underline{a}\) be an \(l\)-sequence with connection integer \(p\) and period \(T=p-1\), we show that the autocorrelation \(C_{\underline{a}}(\tau )\) of \(\underline{a}\) with shift \(\tau\) satisfies: \[ \left| C_{\underline{a}}(\tau)-\frac{p-1}{p^{2}}\cdot \sum_{c=1}^{p-1} \tan \left( \frac{\pi c2^{-\tau }}{p}\right) \tan \left( \frac{\pi c}{p}\right) \right| =O(\ln ^{2}p). \] Thus by calculating this triangular sum, an estimate of \(C_{\underline{a}}(\tau)\) can be obtained. Particularly, for any shift \(\tau\) with \(2^{-\tau }(\text{mod}\;p)=(p-3)/2\) or \((p+3)/2\), the autocorrelation \(C_{\underline{a}}(\tau)\) of \(\underline{a}\) with shift \(\tau\) satisfies \(C_{\underline{a}}(\tau )=O(\ln^{2}p)\), thus when \(p\) is sufficiently large, the autocorrelation is low. Such result also holds for the decimations of \(l\)-sequences.

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnault, F., Berger, T.P.: Design and properties of a new pseudorandom generator based on a filtered FCSR automaton. IEEE Trans. Comput. 54(11), 1374–1383 (2005) · doi:10.1109/TC.2005.181
[2] Arnault, F., Berger, T.P.: F-FCSR, design of a new class of stream ciphers. In: Fast Software Encryption. LNCS 3557, pp. 83–97. Springer, New York (2005) · Zbl 1140.68381
[3] Arnault, F., Berger, T.P., Lauradoux, C.: Update on F-FCSR stream cipher. ECRYPT Stream Cipher Project Report 2006/025. http://www.ecrypt.eu.org/stream (2006)
[4] Couture, R., L’Ecuyer, P.: On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Math. Comput. 62, 799–808 (1994) · Zbl 0803.65005 · doi:10.1090/S0025-5718-1994-1220826-X
[5] Golomb, S.W.: Shift Register Sequences. Holden-Day, San Francisco (1967) (reprinted by Aegean Park Press, 1982) · Zbl 0267.94022
[6] Goresky, M., Klapper, A.: Arithmetic crosscorrelations of feedback with carry shift register sequences. IEEE Trans. Inf. Theory 43(7), 1342–1345 (1997) · Zbl 0878.94047 · doi:10.1109/18.605605
[7] Goresky, M., Klapper, A.: Periodicity and distribution properties of combined FCSR sequences. In: Sequnces and their Applications–SETA. LNCS 4086, pp. 334–341. Springer, New York (2006) · Zbl 1152.94384
[8] Klapper, A., Goresky, M.: 2-adic shift registers. In: Fast Software Encryption. LNCS 809, pp. 174–178. Springer, Berlin (1994) · Zbl 0943.94515
[9] Klapper, A., Goresky, M.: Large period nearly deBrujin FCSR sequences. In: Advances in Cryptology–Eurocrypt 1995. LNCS 921, pp. 263–273. Springer, New York (1995) · Zbl 0973.94510
[10] Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10, 111–147 (1997) · Zbl 0874.94029 · doi:10.1007/s001459900024
[11] Lidl, R., Niedereiter, H.: Finite Field. Addison-Wesley, Toronto (1983)
[12] Marsaglia, G., Zaman, A.: A new class of random number generators. Ann. Appl. Probab. 1(3), 462–480 (1991) · Zbl 0733.65005 · doi:10.1214/aoap/1177005878
[13] Xu, H., Qi, W.-F.: Autocorrelations of maximum period FCSR sequences. SIAM J. Discrete Math. 20(3), 568–577 (2006) · Zbl 1128.94006 · doi:10.1137/050633974
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.