In 1997, Mauduit and Sárközy first introduced the measures of pseudorandomness for binary sequences. Since then, many pseudorandom binary sequences have been constructed and studied. In particular, Gyarmati presented a large family of pseudorandom binary sequences using the discrete logarithms. Ten years later, to satisfy the requirement from many applications in cryptography (e.g., in encrypting "bit-maps'' and watermarking), the definition of binary sequences is extended from one dimension to several dimensions by Hubert, Mauduit and Sárközy. They introduced the measure of pseudorandomness for this kind of several-dimension binary sequence which is called binary lattices. In this paper, large families of pseudorandom binary sequences and binary lattices are constructed by both discrete logarithms and multiplicative inverse modulo $ p $. The upper estimates of their pseudorandom measures are based on estimates of either character sums or mixed exponential sums.
Citation: Yuchan Qi, Huaning Liu. Binary sequences and lattices constructed by discrete logarithms[J]. AIMS Mathematics, 2022, 7(3): 4655-4671. doi: 10.3934/math.2022259
In 1997, Mauduit and Sárközy first introduced the measures of pseudorandomness for binary sequences. Since then, many pseudorandom binary sequences have been constructed and studied. In particular, Gyarmati presented a large family of pseudorandom binary sequences using the discrete logarithms. Ten years later, to satisfy the requirement from many applications in cryptography (e.g., in encrypting "bit-maps'' and watermarking), the definition of binary sequences is extended from one dimension to several dimensions by Hubert, Mauduit and Sárközy. They introduced the measure of pseudorandomness for this kind of several-dimension binary sequence which is called binary lattices. In this paper, large families of pseudorandom binary sequences and binary lattices are constructed by both discrete logarithms and multiplicative inverse modulo $ p $. The upper estimates of their pseudorandom measures are based on estimates of either character sums or mixed exponential sums.
| [1] |
C. Mauduit, A. Sárközy, On finite pseudorandom binary sequencs I: Measure of pseudorandomness, the Legendre symbol, Acta Arith., 82 (1997), 365–377. https://doi.org/10.4064/aa-82-4-365-377 doi: 10.4064/aa-82-4-365-377
|
| [2] |
H. Liu, A family of elliptic curve pseudorandom binary sequences, Des. Codes Cryptogr., 73 (2014), 251–265. https://doi.org/10.1007/s10623-013-9822-7 doi: 10.1007/s10623-013-9822-7
|
| [3] |
C. Mauduit, J. Rivat, A. Sárközy, Construction of pseudorandom binary sequences using additive characters, Monatsh. Math., 141 (2004), 197–208. https://doi.org/10.1007/s00605-003-0112-8 doi: 10.1007/s00605-003-0112-8
|
| [4] |
C. Mauduit, A. Sárközy, Construction of pseudorandom binary sequences by using the multiplicative inverse, Acta Math. Hung., 108 (2005), 239–252. https://doi.org/10.1007/s10474-005-0222-y doi: 10.1007/s10474-005-0222-y
|
| [5] |
L. Mérai, Remarks on pseudorandom binary sequences over elliptic curves, Fund. Inform., 114 (2012), 301–308. https://doi.org/10.3233/FI-2012-630 doi: 10.3233/FI-2012-630
|
| [6] |
J. Rivat, A. Sárközy, Modular constructions of pseudorandom binary sequences with composite moduli, Period. Math. Hung., 51 (2006), 75–107. https://doi.org/10.1007/s10998-005-0031-7 doi: 10.1007/s10998-005-0031-7
|
| [7] |
K. Gyarmati, On a family of pseudorandom binary sequences, Period. Math. Hung., 49 (2005), 45–63. https://doi.org/10.1007/s10998-004-0522-y doi: 10.1007/s10998-004-0522-y
|
| [8] | L. Mérai, A construction of pseudorandom binary sequences using rational functions, Unif. Distrib. Theory, 4 (2009), 35–49. |
| [9] |
P. Hubert, C. Mauduit, A. Sárközy, On pseudorandom binary lattices, Acta Arith., 125 (2006), 51–62. https://doi.org/10.4064/aa125-1-5 doi: 10.4064/aa125-1-5
|
| [10] |
K. Gyarmati, C. Mauduit, A. Sárközy, Pseudorandom binary sequences and lattices, Acta Arith., 135 (2008), 181–197. https://doi.org/10.4064/aa135-2-6 doi: 10.4064/aa135-2-6
|
| [11] | K. Gyarmati, C. Mauduit, A. Sárközy, Constructions of pseudorandom binary lattices, Unif. Distrib. Theory, 4 (2009), 59–80. |
| [12] |
K. Gyarmati, On new measures of pseudorandomness of binary lattices, Acta Math. Hung., 131 (2011), 346–359. https://doi.org/10.1007/s10474-010-0041-7 doi: 10.1007/s10474-010-0041-7
|
| [13] |
K. Gyarmati, C. Mauduit, A. Sárközy, Measures of pseudorandomness of finite binary lattices, II. (The symmetry measures), Ramanujan J., 25 (2011), 155–178. https://doi.org/10.1007/s11139-010-9255-0 doi: 10.1007/s11139-010-9255-0
|
| [14] |
K. Gyarmati, C. Mauduit, A. Sárközy, On finite pseudorandom binary lattices, Discrete Appl. Math., 216 (2017), 589–597. https://doi.org/10.1016/j.dam.2015.07.012 doi: 10.1016/j.dam.2015.07.012
|
| [15] |
H. Liu, Large families of pseudorandom binary lattices by using the multiplicative inverse modulo $p$, Int. J. Number Theory, 15 (2019), 527–546. https://doi.org/10.1142/S1793042119500271 doi: 10.1142/S1793042119500271
|
| [16] |
C. Mauduit, A. Sárközy, Construction of pseudorandom binary lattices by using the multiplicative inverse, Monatsh. Math., 153 (2008), 217–231. https://doi.org/10.1007/s00605-007-0479-z doi: 10.1007/s00605-007-0479-z
|
| [17] |
L. Goubin, C. Mauduit, A. Sárközy, Construction of large families of pseudorandom binary sequences, J. Number Theory, 106 (2004), 56–69. https://doi.org/10.1016/j.jnt.2003.12.002 doi: 10.1016/j.jnt.2003.12.002
|
| [18] | L. Mérai, A construction of pseudorandom binary sequences using both additive and multiplicative characters, Acta Arith., 139 (2009), 241–252. |
Yuchan Qi, Huaning Liu. Binary sequences and lattices constructed by discrete logarithms[J]. AIMS Mathematics, 2022, 7(3): 4655-4671. doi: 10.3934/math.2022259
DownLoad: