×

Sequences related to Legendre/Jacobi sequences. (English) Zbl 1142.11343

Summary: Two families of binary sequences are constructed from \(d\)th order cyclotomic generator and from \(d\)th order generalized cyclotomic generator with respect to two distinct primes respectively. By using estimates of certain exponential sums over rings or fields, the upper bounds of both the well-distribution measure and the order \(k\) (at least for small \(k\)) correlation measure of the resulting binary sequences are evaluated, and some lower bounds on the linear complexity profile of \(d\)-ary cyclotomic sequences and \(d\)-ary generalized cyclotomic sequences are presented. Our results indicate that such binary sequences possess “very good” local pseudo-randomness.

MSC:

11K36 Well-distributed sequences and other variations
11T22 Cyclotomy
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bai, E.; Fu, X.; Xiao, G., On the linear complexity of generalized cyclotomic sequences of order four over \(Z_{ pq } \), IEICE Trans. Fundamentals of Electron. Commun. Comput. Sci., E88-A, 1, 392-395 (2005)
[2] Bai, E.; Liu, X.; Xiao, G., Linear complexity of new generalized cyclotomic sequences of order two of length pq, Trans. Inf. Theory, 51, 5, 849-1853 (2005) · Zbl 1234.94019
[3] Caballero-Gil, P.; Fúster-Sabater, A., A wide family of nonlinear filter functions with a large linear span, Inf. Sci., 164, 1-4, 197-207 (2004) · Zbl 1073.94009
[4] Cassaigne, J.; Mauduit, C.; Sárközy, A., On finite pseudorandom binary sequences, VII: the measures of pseudorandomness, Acta Arithm., 103, 97-118 (2002) · Zbl 1126.11330
[5] Chen, Z.; Li, S.; Xiao, G., Construction of pseudo-random binary sequences from elliptic curves by using discrete logarithm, (Proc. Int. Conf. Sequences Appl. - SETA’06. Proc. Int. Conf. Sequences Appl. - SETA’06, LNCS, vol. 4086 (2006), Springer-Verlag: Springer-Verlag Berlin), 285-294 · Zbl 1152.94376
[6] Cusick, T. W.; Ding, C.; Renvall, A., Stream Ciphers and Number Theory (1998), Elsevier: Elsevier Amsterdam · Zbl 0930.11086
[7] Z.D. Dai, J.H. Yang, G. Gong, P. Wang, On the linear complexity of generalized Legendre sequences, http://www.cacr.math.uwaterloo.ca/; Z.D. Dai, J.H. Yang, G. Gong, P. Wang, On the linear complexity of generalized Legendre sequences, http://www.cacr.math.uwaterloo.ca/
[8] Z.D. Dai, G. Gong, H.Y. Song, Trace representation of binary Jacobi sequences, http://www.cacr.math.uwaterloo.ca/; Z.D. Dai, G. Gong, H.Y. Song, Trace representation of binary Jacobi sequences, http://www.cacr.math.uwaterloo.ca/ · Zbl 1201.05015
[9] Damgård, I., On the randomness of Legendre and Jacobi sequences, Adv. Cryptol.: CRYPTO’88. Adv. Cryptol.: CRYPTO’88, LNCS, vol. 403 (1990), Springer-Verlag: Springer-Verlag Berlin, pp. 163-172
[10] Ding, C., Binary cyclotomic generators, Fast Software Encrytion. Fast Software Encrytion, LNCS, vol. 1008 (1995), Springer-Verlag: Springer-Verlag Berlin, pp. 20-60 · Zbl 0939.94512
[11] Ding, C., Linear complexity of generalized cyclotomic binary sequences of order 2, Finite Fields Appl., 3, 2, 159-174 (1997) · Zbl 0908.11062
[12] Ding, C., New generalized cyclotomy and its applications, Finite Fields Appl., 4, 2, 140-166 (1998) · Zbl 0908.11058
[13] Ding, C., Pattern distributions of Legendre sequences, IEEE Trans. Inf. Theory, 44, 4, 1693-1698 (1998) · Zbl 0943.94007
[14] Ding, C., Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44, 4, 1699-1702 (1998) · Zbl 0943.94006
[15] Ding, C.; Helleseth, T., On cyclotomic generator of order \(r\), Inf. Process. Lett., 66, 1, 21-25 (1998) · Zbl 1078.94511
[16] Ding, C.; Helleseth, T.; Shan, W., On the linear complexity of Legendre sequences, IEEE Trans. Inf. Theory, 44, 3, 1276-1278 (1998) · Zbl 0912.94014
[17] Goubin, L.; Mauduit, C.; Sárközy, A., Construction of large families of pseudorandom binary sequences, J. Number Theory, 106, 1, 56-69 (2004) · Zbl 1049.11089
[18] Green, D. H.; Green, P. R., Modified Jacobi sequences, IEE Proc.: Comput. Digital Tech., 147, 4, 241-251 (2000)
[19] Green, D. H.; Choi, J., Linear complexity of modified Jacobi sequences, IEE Proc.: Comput. Digital Tech., 149, 3, 97-101 (2002)
[20] Gyarmati, K., On a family of pseudorandom binary sequences, Period. Math. Hungarica, 49, 2, 45-63 (2004) · Zbl 1072.11058
[21] Kim, J. H., Trace representation of Legendre sequences, Design, Codes Cryptogr., 24, 3, 343-348 (2001) · Zbl 0991.94031
[22] Kim, J. H.; Song, H. Y., On the linear complexity of Hall’s sextic residue sequences, IEEE Trans. Inf. Theory, 47, 5, 2094-2096 (2001) · Zbl 1016.94023
[23] J.H. Kim, H.Y. Song, G. Gong, Trace representation of Hall’s sextic residue sequences of period \(p \operatorname{\equiv;} 7\) http://www.cacr.math.uwaterloo.ca/; J.H. Kim, H.Y. Song, G. Gong, Trace representation of Hall’s sextic residue sequences of period \(p \operatorname{\equiv;} 7\) http://www.cacr.math.uwaterloo.ca/
[24] Lidl, R.; Niederreiter, H., Finite Fields (1983), Addison-Wesley: Addison-Wesley Reading, MA
[25] Mauduit, C.; Sárközy, A., On finite pseudorandom binary sequences I: measures of pseudorandomness, the Legendre symbol, Acta Arithm., 82, 365-377 (1997) · Zbl 0886.11048
[26] Mauduit, C.; Rivat, J.; Sárközy, A., Construction of pseudorandom binary sequences using additive characters, Mh. Math., 141, 3, 197-208 (2004) · Zbl 1110.11024
[27] Nina, B.; Winterhof, A., Some notes on the two-prime generator of order 2, Trans. Inf. Theory, 51, 10, 3654-3657 (2005) · Zbl 1282.94026
[28] Rivit, J.; Sárközy, A., Modular constructions of pseudorandom binary sequences with composite moduli, Period. Math. Hungarica, 51, 2, 75-107 (2005) · Zbl 1111.11041
[29] Sárközy, A., A finite pseudorandom binary sequence, Stud. Sci. Math. Hungarica, 38, 1-4, 377-384 (2001) · Zbl 0997.11062
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.