Construction of pseudorandom binary lattices based on multiplicative characters
- PDF / 115,656 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 104 Downloads / 227 Views
CONSTRUCTION OF PSEUDORANDOM BINARY LATTICES BASED ON MULTIPLICATIVE CHARACTERS ´szlo ´ Me ´rai La [Communicated by Attila Peth˝ o] E¨ otv¨ os Lor´ and University, Department of Algebra and Number Theory 1117 Budapest, P´ azm´ any P´eter s´et´ any 1/c, Hungary E-mail: [email protected] (Received February 25, 2009; Accepted April 19, 2009)
Abstract In this paper a large family of pseudorandom binary lattices is constructed by using the multiplicative characters of finite fields. This construction generalizes several one-dimensional constructions to arbitrary dimensions.
1. Introduction In a series of papers a constructive theory of finite pseudorandom binary sequences was developed. In particular, in [12] measures of pseudorandomness were introduced and it was shown that the Legendre symbol sequence ( p1 ), ( p2 ), . . . , ( p−1 p ) has strong pseudorandom properties in terms of these measures. In [1] a large family of sequences was constructed as a generalization of the Legendre symbol sequence. For prime p the sequence Ep = (e1 , . . . , ep ) was defined by f (n) ( p ) if p ∤ f (n), en = (1) +1 for p | f (n). It was shown that if f (x) ∈ Fp [x] satisfies certain conditions, then it also has strong pseudorandom properties. Later several constructions of large families with strong pseudorandom properties were studied: Let p be a prime and define the sequence Ep = (e1 , . . . , ep ) by +1 if 1 ≤ ind f (n) < p/2 for p ∤ f (n), en = (2) −1 otherwise, Mathematics subject classification number : 11K45. Key words and phrases: pseudorandom, binary sequence, binary lattice, finite field, character. 0031-5303/2009/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
44
´ L. MERAI
where ind a denotes the index or discrete logarithm of a modulo p with respect to a given primitive root of modulo p (see [4], [2], [3], [16]); +1 if arg(χ(f (n))) ∈ [0, π) for p ∤ f (n), en = (3) −1 otherwise, where χ is a multiplicative character modulo p, and arg z denotes the argument of z (see [13], [14], [15]). For other constructions see [8], [11] (see also the survey paper [17]). In [7] Hubert, Mauduit and S´ark¨ozy extended the definition of pseudorann domness to several dimensions. Let IN denote the set of the n-dimensional vectors all whose coordinates are selected from the set {0, . . . , N − 1}: n IN = {x = (x1 , . . . , xn ) : x1 , . . . , xn ∈ {0, . . . , N − 1}} .
We call this set the n-dimensional N -lattice or briefly (if n is fixed) the N -lattice. They defined the binary lattices as extensions of binary sequences: Definition 1. A function of type n η(x1 , . . . , xn ) = η(x): IN → {−1, +1}
is called the n-dimensional binary N -lattice or briefly the binary lattice. They extended the definition of measures of pseudorandomness in the following way: Let u1 , . . . , un be n linearly independent vectors, where the i-th coordinate of ui is a positive integer, and the others are zeros. Let t1 , . . . , tn be integers such that 0 ≤ t1 , . . . , tn < N . Then we call the set n BN = {x = x1
Data Loading...
