On pseudorandom binary sequences constructed by using finite fields
- PDF / 488,861 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 202 Views
On pseudorandom binary sequences constructed by using finite fields Richárd Seb˝ok1
Published online: 16 October 2015 © Akadémiai Kiadó, Budapest, Hungary 2015
Abstract By using finite fields of order pr with r ≥ 2 and their quadratic characters, Sárközy and Winterhof presented a construction for binary sequences of length pr with strong pseudorandom properties. In the special case r = 2 Gyarmati improved on their estimates for the pseudorandom measures of these sequences. Here we extend Gyarmati’s result and sharpen the estimates of Sárközy and Winterhof for any prime power pr . Keywords Binary sequences · Pseudorandomness · Finite fields · Well-distributions · Correlation Mathematics Subject Classification
Primary 11K45
1 Introduction Pseudorandom binary sequences play a crucial role in cryptography. The algorithm generating the pseudorandom binary sequence is called pseudorandom bit generator and it is usually characterized in terms of the “next bit test”: the generator satisfies this test if there is no polynomial time algorithm such that having the first k bits it predicts the k + 1-st bit with probability much greater than 1/2. However, this test is suitable only for recursive construction; the non-existence of polynomial time algorithm cannot be proved, the probability much greater than 1/2 is not a strict mathematical notion (see [17] for further details). Another frequently used classical definition of pseudorandomness uses linear complexity profile, but there is a lower bound in [2] for linear complexity profile in terms of the correlation measure (for definition see (1.1)).
B 1
Richárd Seb˝ok [email protected] Department of Algebra and Number Theory, Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary
123
On pseudorandom binary sequences constructed by using finite fields
211
Thus Mauduit and Sárközy proposed a new, more constructive and quantitative approach. First in [17] they introduced the following measures for studying pseudorandom (briefly PR) properties of finite binary sequences: The well-distribution measure of the binary sequence E N = (e1 , . . . , e N ) ∈ {−1, +1} N is defined by
t |U W (E n ) = max (E N , t, a, b)| = max ea+ jb , a,b,t a,b,t j=1
where the maximum is taken over all a ∈ Z, b, t ∈ N such that 1 ≤ a + b ≤ a + bt ≤ N . The correlation measure of order k of E N is defined as M (1.1) en+d1 en+d2 . . . en+dk , Ck (E N ) = max |V (E N , M, D)| = max M,D M,D n=1
where the maximum is taken over all D = (d1 , . . . , dk ) with non-negative integers d1 < · · · < dk and M ∈ N such that M + dk ≤ N . The combined (well-distribution-correlation) PR-measure of order k of E N is defined as Q k (E N ) = max |Z (a, b, t, D)| a,b,t,D t = max ea+ jb+d1 ea+ jb+d2 . . . ea+ jb+dk a,b,t,D j=0
(1.2)
where the maximum is taken over all a, b, t, D = (d1 , d2 , . . . , dk ) such that all the subscripts a + jb + dl belongs to {1, . . . , N }. Then the sequence E N is considered as a sequence possessing
Data Loading...
