Construction of pseudorandom binary lattices using elliptic curves

Author:
László Mérai

Journal:
Proc. Amer. Math. Soc. **139** (2011), 407-420

MSC (2010):
Primary 11K45

DOI:
https://doi.org/10.1090/S0002-9939-2010-10631-7

Published electronically:
September 30, 2010

MathSciNet review:
2736325

Full-text 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.**Z. Chen, Elliptic curve analogue of Legendre sequences,*Monatsh. Math.*154 (2008), pp. 1-10. MR**2395518 (2009b:11105)****2.**Z. Chen, S. Li and G. Xiao, Construction of pseudo-random binary sequences from elliptic curves by using discrete logarithm,*Lecture Notes in Comput. Sci.*, 4086, Springer, Berlin, (2006), pp. 285-294. 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. 56-69. MR**2049592 (2004m:11121)****5.**P. Hubert, C. Mauduit and A. Sárközy, On pseudorandom binary lattices,*Acta Arith.*125 (2006), pp. 51-62. 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. Springer-Verlag, Berlin-Heidelberg-New York (2000), pp. 395-404. 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. 1309-1318. MR**2276639 (2007j:11099)****8.**H. Liu, A large family of pseudorandom binary lattices,*Proc. Amer. Math. Soc.*137 (2009), pp. 793-803. MR**2457416 (2009i:11096)****9.**H. Liu, T. Zhan, X. Wang, Large families of elliptic curve pseudorandom binary sequences,*Acta Arith.*140 (2009), pp. 135-144. MR**2558449****10.**C. Mauduit and A. Sárközy, On large families of pseudorandom binary lattices,*Unif. Distrib. Theory*2 (2007), pp. 23-37. 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. 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), pp. 239-252. 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. 217-231. MR**2379668 (2009a:11159)****14.**L. Mérai, Construction of large families of pseudorandom binary sequences,*Ramanujan J.*18 (2009), pp. 341-349. 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. 241-252. 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. 43-51. MR**2544619****18.**A. Sárközy,*On finite pseudorandom binary sequences and their applications in cryptography*, Tatra Mt. Math. Publ. 37 (2007), 123-136. MR**2553412****19.**A. Sárközy, A finite pseudorandom binary sequence,*Studia Sci. Math. Hungar.*38 (2001), pp. 377-384. MR**1877793 (2003j:11082)****20.**A. Winterhof, Some estimates for character sums and applications,*Des. Codes Crytogr.*22 (2001), pp. 123-131. MR**1813781 (2002g:11128)**

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, H-1364 Hungary

Email:
merai@cs.elte.hu

DOI:
https://doi.org/10.1090/S0002-9939-2010-10631-7

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.