Construction of pseudorandom binary sequences using additive characters over GF(2 k )
- PDF / 135,927 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 43 Downloads / 245 Views
CONSTRUCTION OF PSEUDORANDOM BINARY SEQUENCES USING ADDITIVE CHARACTERS OVER GF(2k ) ´nos Folla ´th Ja [Communicated by Andr´ as S´ ark¨ ozy] Faculty of Computer Science, University of Debrecen Egyetem t´er 1, H-4032 Debrecen, Hungary E-mail: [email protected] (Received February 3, 2008; Accepted May 16, 2008)
Abstract In a series of papers Mauduit and S´ ark¨ ozy (partly with coauthors) studied finite pseudorandom binary sequences and they constructed sequences with strong pseudorandom properties. In these constructions fields with prime order were used. In this paper a new construction is presented, which is based on finite fields of order 2k .
1. Introduction Mauduit and S´ ark¨ ozy studied pseudorandom binary sequences of EN = {e1 , . . . , eN } ∈ {−1, +1}N and introduced the following measures of pseudorandomness of binary sequences [7]: Definition 1. The well-distribution measure of EN is defined as t−1 X ea+jb , W (EN ) = max a,b,t
j=0
where the maximum is taken over all a, b, t with a, b, t ∈ N, 1 ≤ a + b ≤ a + tb ≤ N . Mathematics subject classification numbers: 68P25, 11T23. Key words and phrases: binary sequence, character sums, normality measure, pseudorandom. 0031-5303/2008/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
74
´ J. FOLLATH
Definition 2. The correlation measure of order k of EN is M X en+d1 en+d2 . . . en+dk , Ck (EN ) = max M,D
n=1
where the maximum is taken over all D = (d1 , . . . , dk ) (d1 < · · · < dk are nonnegative integers) and M ∈ N with M + dk ≤ N . Definition 3. The combined (well-distribution-correlation) PR-measure of order k of EN is defined as Qk (EN ) = max |Z(a, b, t, D)|, a,b,t,D
where
t X ea+jb+d1 ea+jb+d2 . . . ea+jb+dk . Z(a, b, t, D) =
(1.1)
j=0
Definition 4. The combined PR-measure of EN : Q(EN ) = max Qk (EN ). k≤log N
A pseudorandom sequence is considered good if both W (EN ) and Ck (EN ) (at least for small k) are small in terms of N : both of them are o(N ) as N → ∞. Later Cassaigne, Mauduit and S´ark¨ozy [5] showed that this terminology is justified since for almost all EN ∈ {−1, +1}N , both W (EN ) and Ck (EN ) are less than N 1/2 (log N )c . Moreover, in [7] it was shown that {( np )}, 0 < n < p, where ( np ) is the Legendre symbol, forms a good pseudorandom sequence. Later in [9] and [14] this construction was extended to a large family of good pseudorandom sequences. The later construction and its pseudorandom measures are described in the following theorem (proved in [14]): Theorem 1. Let p be an odd prime, λ ∈ F∗p be of multiplicative order T and f (x) ∈ Fp [x] be of degree k and not of the form cxα (g(x))2 with c ∈ Fp , α ∈ N, g(x) ∈ Fp [x]. Define the sequence ET = {e1 , . . . , eT } by ( f (λn ) if p ∤ f (λn ), p en = 1 if p | f (λn ). Then we have W (ET ) < 5kp1/2 log p. Moreover, assume that also l ∈ N, T is a prime, and either min{(4k)l , (4l)k } ≤ T or 2 is a primitive root modulo T . Then we have also Cl (ET ) ≤ 5klp1/2 log p.
PSEUDORANDOM BINARY SEQUENCES
75
There were further
Data Loading...
