Construction of pseudorandom binary lattices using elliptic curves
Author:
László Mérai
Journal:
Proc. Amer. Math. Soc. 139 (2011), 407420
MSC (2010):
Primary 11K45
Published electronically:
September 30, 2010
MathSciNet review:
2736325
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In an earlier paper, Hubert, Mauduit and Sárközy introduced and studied the notion of pseudorandomness of binary lattices. Later constructions were given by using characters and the notion of a multiplicative inverse over finite fields. In this paper a further large family of pseudorandom binary lattices is constructed by using elliptic curves.
 1.
Zhixiong
Chen, Elliptic curve analogue of Legendre sequences, Monatsh.
Math. 154 (2008), no. 1, 1–10. MR 2395518
(2009b:11105), 10.1007/s006050080520x
 2.
Zhixiong
Chen, Shengqiang
Li, and Guozhen
Xiao, Construction of pseudorandom binary sequences from elliptic
curves by using discrete logarithm, Sequences and their
applications—SETA 2006, Lecture Notes in Comput. Sci.,
vol. 4086, Springer, Berlin, 2006, pp. 285–294. MR 2444692
(2009g:94050), 10.1007/11863854_24
 3.
A. Enge: Elliptic Curves and Their Application to Cryptography: An Introduction, Kluwer Academic Publisher, Dordrecht, 1999.
 4.
Louis
Goubin, Christian
Mauduit, and András
Sárközy, Construction of large families of pseudorandom
binary sequences, J. Number Theory 106 (2004),
no. 1, 56–69. MR 2049592
(2004m:11121), 10.1016/j.jnt.2003.12.002
 5.
P.
Hubert, C.
Mauduit, and A.
Sárközy, On pseudorandom binary lattices, Acta
Arith. 125 (2006), no. 1, 51–62. MR 2275217
(2007k:11124), 10.4064/aa12515
 6.
David
R. Kohel and Igor
E. Shparlinski, On exponential sums and group generators for
elliptic curves over finite fields, Algorithmic number theory (Leiden,
2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin,
2000, pp. 395–404. MR 1850620
(2003c:11094), 10.1007/10722028_24
 7.
Huaning
Liu, New pseudorandom sequences constructed
by quadratic residues and Lehmer numbers, Proc.
Amer. Math. Soc. 135 (2007), no. 5, 1309–1318. MR 2276639
(2007j:11099), 10.1090/S0002993906086308
 8.
Huaning
Liu, A large family of pseudorandom binary
lattices, Proc. Amer. Math. Soc.
137 (2009), no. 3,
793–803. MR 2457416
(2009i:11096), 10.1090/S0002993908097062
 9.
Huaning
Liu, Tao
Zhan, and Xiaoyun
Wang, Large families of elliptic curve pseudorandom binary
sequences, Acta Arith. 140 (2009), no. 2,
135–144. MR 2558449
(2010k:11121), 10.4064/aa14023
 10.
Christian
Mauduit and András
Sárközy, On large families of pseudorandom binary
lattices, Unif. Distrib. Theory 2 (2007), no. 1,
23–37. MR
2318530 (2008h:11079)
 11.
Christian
Mauduit and András
Sárközy, On finite pseudorandom binary sequences. I.
Measure of pseudorandomness, the Legendre symbol, Acta Arith.
82 (1997), no. 4, 365–377. MR 1483689
(99g:11095)
 12.
C.
Mauduit and A.
Sárközy, Construction of pseudorandom binary sequences
by using the multiplicative inverse, Acta Math. Hungar.
108 (2005), no. 3, 239–252. MR 2162562
(2006c:11092), 10.1007/s104740050222y
 13.
Christian
Mauduit and András
Sárközy, Construction of pseudorandom binary lattices
by using the multiplicative inverse, Monatsh. Math.
153 (2008), no. 3, 217–231. MR 2379668
(2009a:11159), 10.1007/s006050070479z
 14.
László
Mérai, Construction of large families of pseudorandom binary
sequences, Ramanujan J. 18 (2009), no. 3,
341–349. MR 2495552
(2010b:11096), 10.1007/s1113900891313
 15.
László
Mérai, A construction of pseudorandom binary sequences using
both additive and multiplicative characters, Acta Arith.
139 (2009), no. 3, 241–252. MR 2545928
(2010i:11118), 10.4064/aa13933
 16.
L. Mérai, Construction of pseudorandom binary sequences over elliptic curves using multiplicative characters, submitted.
 17.
László
Mérai, Construction of pseudorandom binary lattices based on
multiplicative characters, Period. Math. Hungar. 59
(2009), no. 1, 43–51. MR 2544619
(2010i:11119), 10.1007/s109980099043z
 18.
András
Sárközy, On finite pseudorandom binary sequences and
their applications in cryptography, Tatra Mt. Math. Publ.
37 (2007), 123–136. MR 2553412
(2010i:11121)
 19.
A.
Sárközy, A finite pseudorandom binary sequence,
Studia Sci. Math. Hungar. 38 (2001), 377–384. MR 1877793
(2003j:11082), 10.1556/SScMath.38.2001.14.28
 20.
Arne
Winterhof, Some estimates for character sums and applications,
Des. Codes Cryptogr. 22 (2001), no. 2, 123–131.
MR
1813781 (2002g:11128), 10.1023/A:1008300619004
 1.
 Z. Chen, Elliptic curve analogue of Legendre sequences, Monatsh. Math. 154 (2008), pp. 110. MR 2395518 (2009b:11105)
 2.
 Z. Chen, S. Li and G. Xiao, Construction of pseudorandom binary sequences from elliptic curves by using discrete logarithm, Lecture Notes in Comput. Sci., 4086, Springer, Berlin, (2006), pp. 285294. MR 2444692 (2009g:94050)
 3.
 A. Enge: Elliptic Curves and Their Application to Cryptography: An Introduction, Kluwer Academic Publisher, Dordrecht, 1999.
 4.
 L. Goubin, C. Mauduit and A. Sárközy, Construction of large families of pseudorandom binary sequences, J. Number Theory 106 (2004), pp. 5669. MR 2049592 (2004m:11121)
 5.
 P. Hubert, C. Mauduit and A. Sárközy, On pseudorandom binary lattices, Acta Arith. 125 (2006), pp. 5162. MR 2275217 (2007k:11124)
 6.
 D. Kohel and I. E. Shparlinski, On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields. Proc Algorithmic Number Theory Symposium, Leiden, 2000. Lecture Notes in Comput. Sci., 1838. SpringerVerlag, BerlinHeidelbergNew York (2000), pp. 395404. MR 1850620 (2003c:11094)
 7.
 H. Liu, New pseudorandom sequences constructed by quadratic residues and Lehmer numbers, Proc. Amer. Math. Soc. 135, no. 5 (2007), pp. 13091318. MR 2276639 (2007j:11099)
 8.
 H. Liu, A large family of pseudorandom binary lattices, Proc. Amer. Math. Soc. 137 (2009), pp. 793803. MR 2457416 (2009i:11096)
 9.
 H. Liu, T. Zhan, X. Wang, Large families of elliptic curve pseudorandom binary sequences, Acta Arith. 140 (2009), pp. 135144. MR 2558449
 10.
 C. Mauduit and A. Sárközy, On large families of pseudorandom binary lattices, Unif. Distrib. Theory 2 (2007), pp. 2337. MR 2318530 (2008h:11079)
 11.
 C. Mauduit and A. Sárközy, On finite pseudorandom binary sequences. I: Measures of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), pp. 365377. MR 1483689 (99g:11095)
 12.
 C. Mauduit and A. Sárközy, Construction of pseudorandom binary sequences by using the multiplicative inverse, Acta Math. Hungar. 108 (2005), pp. 239252. MR 2162562 (2006c:11092)
 13.
 C. Mauduit and A. Sárközy, Construction of pseudorandom binary lattices by using the multiplicative inverse, Monatsh. Math. 153 (2008), pp. 217231. MR 2379668 (2009a:11159)
 14.
 L. Mérai, Construction of large families of pseudorandom binary sequences, Ramanujan J. 18 (2009), pp. 341349. MR 2495552 (2010b:11096)
 15.
 L. Mérai, A construction of pseudorandom binary sequences using both additive and multiplicative characters, Acta Arith. 139 (2009), pp. 241252. MR 2545928
 16.
 L. Mérai, Construction of pseudorandom binary sequences over elliptic curves using multiplicative characters, submitted.
 17.
 L. Mérai, Construction of pseudorandom binary lattices based on multiplicative characters, Periodica Math. Hun. 59 (2009), pp. 4351. MR 2544619
 18.
 A. Sárközy, On finite pseudorandom binary sequences and their applications in cryptography, Tatra Mt. Math. Publ. 37 (2007), 123136. MR 2553412
 19.
 A. Sárközy, A finite pseudorandom binary sequence, Studia Sci. Math. Hungar. 38 (2001), pp. 377384. MR 1877793 (2003j:11082)
 20.
 A. Winterhof, Some estimates for character sums and applications, Des. Codes Crytogr. 22 (2001), pp. 123131. MR 1813781 (2002g:11128)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2010):
11K45
Retrieve articles in all journals
with MSC (2010):
11K45
Additional Information
László Mérai
Affiliation:
Alfréd Rényi Institute of Mathematics, Budapest, Pf. 127, H1364 Hungary
Email:
merai@cs.elte.hu
DOI:
http://dx.doi.org/10.1090/S000299392010106317
Keywords:
Pseudorandom,
binary sequence,
binary lattice,
elliptic curve,
character sum
Received by editor(s):
February 5, 2010
Published electronically:
September 30, 2010
Additional Notes:
This research was partially supported by the Hungarian National Foundation for Scientific Research, Grant No. K67676, and by the Momentum Fund of the Hungarian Academy of Sciences.
Communicated by:
Jim Haglund
Article copyright:
© Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
