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.**Zhixiong Chen,*Elliptic curve analogue of Legendre sequences*, Monatsh. Math.**154**(2008), no. 1, 1–10. MR**2395518**, https://doi.org/10.1007/s00605-008-0520-x**2.**Zhixiong Chen, Shengqiang Li, and Guozhen Xiao,*Construction of pseudo-random 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**, https://doi.org/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**, https://doi.org/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**, https://doi.org/10.4064/aa125-1-5**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**, https://doi.org/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**, https://doi.org/10.1090/S0002-9939-06-08630-8**8.**Huaning Liu,*A large family of pseudorandom binary lattices*, Proc. Amer. Math. Soc.**137**(2009), no. 3, 793–803. MR**2457416**, https://doi.org/10.1090/S0002-9939-08-09706-2**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**, https://doi.org/10.4064/aa140-2-3**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****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**, https://doi.org/10.4064/aa-82-4-365-377**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**, https://doi.org/10.1007/s10474-005-0222-y**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**, https://doi.org/10.1007/s00605-007-0479-z**14.**László Mérai,*Construction of large families of pseudorandom binary sequences*, Ramanujan J.**18**(2009), no. 3, 341–349. MR**2495552**, https://doi.org/10.1007/s11139-008-9131-3**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**, https://doi.org/10.4064/aa139-3-3**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**, https://doi.org/10.1007/s10998-009-9043-z**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****19.**A. Sárközy,*A finite pseudorandom binary sequence*, Studia Sci. Math. Hungar.**38**(2001), 377–384. MR**1877793**, https://doi.org/10.1556/SScMath.38.2001.1-4.28**20.**Arne Winterhof,*Some estimates for character sums and applications*, Des. Codes Cryptogr.**22**(2001), no. 2, 123–131. MR**1813781**, https://doi.org/10.1023/A:1008300619004

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.