Pseudorandomness of binary sequences derived from linear recursions
- PDF / 451,909 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 102 Downloads / 217 Views
Pseudorandomness of binary sequences derived from linear recursions László Mérai1,2
Published online: 28 May 2015 © Akadémiai Kiadó, Budapest, Hungary 2015
Abstract In this paper we study the pseudorandomness of finite binary sequences derived from linear recursions. We show, that the well-distribution measures of these sequences are small. Furthermore we also show that the correlation measures of these sequences are small for small correlation orders, but if the order of the correlation is greater than the order of the linear recursion, then the correlation can be large. Keywords
Pseudorandomness · Pseudorandom measures · Linear recursion
Mathematics Subject Classification
Primary 11K45
1 Introduction In order to study the pseudorandomness of finite binary sequences Mauduit and Sárközy [6] introduced the following measures of pseudorandomness: For a given binary sequence E N = (e1 , . . . , e N ) ∈ {−1, +1} N write U (E N , t, a, b) =
t−1
ea+ jb ,
j=0
B
László Mérai [email protected]
1
Department of Computer Algebra, Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary
2
Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Strasse 69, 4040 Linz, Austria
123
Pseudorandomness of binary sequences
65
and for D = (d1 , . . . , d ) with non-negative integers 0 ≤ d1 < · · · < d write V (E N , M, D) =
M
en+d1 en+d2 . . . en+d .
n=1
Then the well-distribution measure of E N is defined by
t−1 ea+ jb , W (E N ) = max |U (E N , t, a, b)| = max a,b,t a,b,t j=0
where the maximum is taken over all a, b, t ∈ N such that 1 ≤ a ≤ a + (t − 1)b ≤ N , and the correlation measure of order of E N is defined as M en+d1 en+d2 . . . en+d , C (E N ) = max |V (E N , M, D)| = max M,D M,D n=1
where the maximum is taken over all D and M such that d + M ≤ N . The sequence E N possesses good pseudorandom properties, if both these measures W (E N ) and C (E N ) (at least for small ) are “small” in terms of N (in particular, both are o(N ) as N → ∞). This terminology is justified since for a truly random sequence E N √ each of these measures is N log N . (For a more precise version of this result see [1]). Let q = p m be an odd prime power and Fq be the finite field with q elements. Let h be a positive integer and c1 , c2 , . . . , ch ∈ Fq be fixed elements. For initial values x1 , . . . , x h ∈ Fq consider the sequence (xn ) defined by the linear recursion xn = c1 xn−1 + · · · + ch xn−h , n > h.
(1.1)
In this paper we study the pseudorandomness of finite binary sequences derived from the sequences (xn ). If q = p is a prime number, Gyarmati, Peth˝o and Sárközy [4] studied the binary sequence obtained from (xn ) by using the Legendre symbol while if q is a power of 2 Folláth [2] studied the binary sequence obtained from (xn ) by using additive characters (see also [3]). In general, it is hard to control the pseudorandom measures of the binary sequences derived from (xn ). However we can gi
Data Loading...
