On the cross-combined measure of families ofbinary lattices and sequences
Katalin Gyarmati
Eötvös Loránd University, Faculty of Siences,
Department of Algebra and Number Theory,
Hungary, Budapest
gykati@cs.elte.hu

Measures of pseudorandomness
The constructive and quantitative study of pseudorandomness
stared by the work of Mauduit and Sárközy. They introduced thefollowing measures:

Definition
For a binary sequence EN = (e1 , e2 , . . . , eN ) ∈ {−1, +1}NW (EN ) = max
a,b,tandCℓ (EN ) =max

M, d1 <d2 <···<dℓt
Xea+jbM
Xen+d1 · · · en+dℓ

j=0n=12 / 24

Cassaigne, Ferenczi, Mauduit, Rivat and Sárközy formulated thefollowing principle:“The sequence EN is considered a “good” pseudorandom sequence ifthese measures W (EN ) and Cℓ (EN ) are “small”.”
EN has strong pseudorandom properties if
W (EN ), Cℓ (EN ) ≪ N 1−ε .
But in the best constructions we have:
W (EN ), Cℓ (EN ) ≪ N 1/2 (log N)c .

3 / 24

Hoﬀstein and Lieman studied the following construction: Letf (x) ∈ Fp [x] be a polynomial of degree k. Consider the sequence  f (1)0 deff (2)f (p)Ep (f ) =where now= 1.
,,...,pppp
For example, for p = 7, f (x) = x 2 + 1 this sequence can beillustrated by

= +1
= −1
Hoﬀstein and Lieman didn’t prove anything on the pseudorandom
properties of this sequence.

4 / 24

Ep (f ) =f (1)p 
f (2)
f (p)
,,...,ppIn 2004 Goubin, Mauduit and Sárközy proved that under some not
too restrictive conditions on the prime p or the polynomial f (x) wehave
W (Ep (f )), Cℓ (Ep (f )) ≪ p1/2 log p
Since then several other constructions have been given, but still thisis one of the best: it has strong pseudorandom properties and its
implementation is relatively easy and fast.

5 / 24

I remark that several important a posteriori tests (indicated by apackage of the National Institute of Standards and Technology)
were checked by Rivat, Mauduit and Sárközy. This work wascontinued by Mérai, Rivat and Sárközy.

6 / 24

Large families of binary sequences
Let P≤K denote the set of monic polynomials f (x) ∈ Fp [x] ofdegree k where 1 ≤ k ≤ K .
For f ∈ P≤K deﬁne
Ep (f ) =

f (1)
p

 

f (2)
f (p),,...,.
pp

Let F≤K ,Legendre denote the following large family of binary
sequences:F≤K ,Legendre = {Ep (f ) : f ∈ P≤K }By the result of Goubin, Mauduit and Sárközy many individual
sequences belonging to this family have strong pseudorandom
properties.

7 / 24

In many applications it is not enough to know that the family
contains many sequences with strong pseudorandom properties it ismuch more important to know that the given family has a “rich”,“complex” structure.
For example, there are many independent sequences in it.
Earlier family measures
Ahlswede, Khachatrian, Mauduit and Sárközy: family complexity
Based on the well know Hamming distance: distance minimum.
Bérczes, Ködmön, Pethő, Tóth and others: avalanche eﬀect andcollision free.
Mauduit, Sárközy and Gy.: cross-correlation measure.
8 / 24

Now I will focus on the cross-correlation measure.
(1)

(ℓ)

For sequences EN , . . . , EN ∈ {−1, +1}N write
(i )

(i )

(i )

(i )

for i = 1, 2, . . . , ℓ

EN = (e1 , e2 , . . . eN )and then deﬁne∼(1)∗(ℓ) def(2)

C (EN , EN , . . . , EN ) =max

M,d1 <d2 <···<dℓ

(i )

MX
(1)
(ℓ)
en+d1 · · · en+dℓ .
n=1

(j)

where if the sequences EN and EN (for some 1 ≤ i < j ≤ ℓ) are
identical then in the maximum di = dj is not allowed.
Let F be a large families of binary sequences. Deﬁne thecross-correlation measure bydefΦℓ (F) =

∼

max

(1)
(ℓ)
EN ,...,EN ∈F

(1)

(2)

(ℓ)

C (EN , EN , . . . , EN )9 / 24

Mauduit, Sárközy, Gy.: If the cross-correlation measure is smallthen the sequences in the family are highly independent.
For f ∈ P≤K deﬁne
Ep (f ) =f (1)p f (2)f (p),,...,.
pp

Let F≤K ,Legendre denote the following large family of binary
sequences:F≤K ,Legendre = {Ep (f ) : f ∈ P≤K }Unfortunately F≤K ,Legendre has a very bad cross-correlation
measure.

10 / 24

F≤K ,Legendre has a very bad cross-correlation measure: Consider thepolynomials f (x) = x, x + 1 and x(x + 1). Let     12pn(1) def(1)Ep = Ep (x) =,,...,
so en =pppp
   n+13p+12(2)(2) def,,...,
so en =Ep = Ep (x + 1) =pppp 
1·22·3p · (p + 1)
(3) def
Ep = Ep (x(x + 1)) =,,...,ppp

n(n + 1)(3)
so en =Thenp
∼

(1)

(2)

p X



(3)

Φ3 (F≤K ,Legendre )≥C (Ep , Ep , Ep ) ≥pX(1) (2) (3)en en en
n=1

=n=1n
pn+1p



n(n + 1)p= p − 2.
11 / 24

Construction (Mauduit, Sárközy, Gy.)F≤K ,Legendre,irreducible = {Ep (f ) : f ∈ P≤K andf (x) = x k + ak−2 x k−2 + · · · + a0 is irreducible

oThis family has strong cross-correlation measure:Φℓ (F≤K ,Legendre,irreducible ) ≪ ℓKp1/2 log p.
Problem: It is very diﬃcult and slow to generate one variable
irreducible polynomials over Fp ...
Solution: Consider the multidimensional case!

12 / 24

Binary lattices
Binary sequences can be illustrated in the following way:

= +1
= −1
Binary lattices are the multidimensional extensions of sequences.
Two dimensional binary lattices can be illustrated the following way:

13 / 24

First Hubert, Mauduit and Sárközy studied the multidimensionalcase, they introduced the following precise deﬁnitions (here I
present only the two dimensional case):
IN2 = {x = (x1 , x2 ) : 0 ≤ x1 ≤ N − 1, 0 ≤ x2 ≤ N − 1}
Then a function
η : IN2 → {−1, +1}
called as a two dimensional binary lattice.
B ⊆ IN2 is a box-lattice if it is of the form
B = {x = (x1 u1 , x2 u2 ) : 0 ≤ x1 < t1 , 0 ≤ x2 < t2 }The combined pseudorandom measure of η of order ℓ isdefQℓ (η) =max

B,d1 ,...,dℓX

η(x + d1 ) · · · η(x + dℓ )x∈B

14 / 24

Analogously to the one dimensional cross-correlation measure, Ideﬁned the cross-combined measure for binary lattices:For lattices η1 , η2 , . . . , ηℓ : IN2 → write deﬁne∼∗defQ(η1 , η2 , . . . , ηℓ ) =max

B,d1 <d2 <···<dℓX

η1 (x + d1 ) · · · ηℓ (x + dℓ )x∈Bwhere if the lattices ηi and ηj (for some 1 ≤ i < j ≤ ℓ) are identicalthen in the maximum di = dj is not allowed.
Let G be a large families of binary lattices. Deﬁne thecross-combined measure bydefΦℓ (G) =∼max

η1 ,...,ηℓ ∈G

Q(η1 , η2 , . . . , ηℓ )15 / 24

I studied the connections of the cross-combined measure with otherfamily measures of lattices deﬁned earlier.
Each earlier one-dimensional results can be easily extended to themultidimensional case.

16 / 24

With Mauduit and Sárközy we studied connections between lattices
and sequences. Starting out from a binary lattice η by taking theﬁrst (from the bottom) row of the lattice then we continue by thesecond row, then the third row follows etc. we get a binary
sequence E (η)E()

Gyarmati, Mauduit, Sárközy: There exist binary lattices which havevery large pseudorandom measures, but the corresponding binary
sequence has strong pseudorandom properties.
Gy.: If the lattice has strong pseudorandom properties, thecorresponding binary sequence also has:Cℓ (E (η)) ≤ (ℓ + 2)Qℓ (η).

17 / 24

E()

Let G be a family of two dimensional binary lattices. Then we deﬁnedef
F = (E (G)) of binary sequences by E (G) = {E (η) : η ∈ G}.
Theorem (Gy.):Φℓ (E (G)) ≤ (ℓ + 2)Φℓ (G).

This theorem gives a new way of construction of a family of binary
sequences with strong cross-combined measure: First we generate afamily of binary lattices G with strong cross-combined measure andfrom this we easily generate the family E (G) of binary sequences
which also has strong cross-correlation measure.
18 / 24

I proved for more earlier constructions of family of binary lattices
that they have optimal or nearly optimal cross-combined measure.

Theorem (Gy.)
Let γ denote the quadratic character of Fp2 and let v1 , v2 be a basisof the vectorspace Fp2 over Fp . Let G≤K ,quadratic,irreducible denotethe family of all binary lattices η : Ip2 → {−1, +1} defined byη((x1 , x2 )) = γ(f (x1 v1 + x2 v2 ))where the used one variable irreducible polynomial f is the formf (x) = x k + ak−2 x k−2 + · · · + a0 ∈ Fp2 [x] with degree k ≤ K .
ThenΦℓ (G≤K ,quadratic,irreducible ) ≪ ℓKp log p.
Thus this family has optimal cross-combined measure. Using theprevious theorem about the connections of lattices and sequences
we also get the following:Φℓ (E (G≤K ,quadratic,irreducible )) ≪ ℓ2 Kp log p.
19 / 24

The diﬃculties of the generation of lattices from the familyG≤K ,quadratic,irreducible orsequences from the family E (G≤K ,quadratic,irreducible ) is that they arebased on one-variable irreducible polynomials over Fp2 .
The generation of one-variable irreducible polynomials over ﬁnite
ﬁelds is complicated and slow.
This problem can be avoided by using two-variable polynomials at
the price we have slightly weaker pseudorandom measures than theoptimal bounds.

20 / 24

Theorem (Gy.)
Let G≤K ,Legendre,irreducible denote the family of all binary lattices
η : Ip2 → {−1, +1} defined byη((x1 , x2 )) =f (x1 , x2 )p

where the used two variable irreducible polynomial f ∈ Fp [x1 , x2 ] isnot of the form f (x1 , x2 ) = ϕ(αx1 + βx2 ) with degree k ≤ K . ThenΦℓ (G≤K ,Legendre,irreducible ) ≪ ℓKp3/2 log p.
Then we also have

Theorem (Gy.)Φℓ (E (G≤K ,Legendre,irreducible )) ≪ ℓKp3/2 log p.
21 / 24

Is it diﬃcult to generate two variable irreducible polynomials overFp ?
It can be easy! For example, by the analogue of theSchönemann-Eisenstein criteria the polynomials
f (x1 , x2 ) = x1k + x1 x2 g (x1 , x2 ) + x2 h(x2 )(where deg g ≤ k − 5 and deg h = k − 2, the coeﬃcient of x k−3 inh(x) is 0, x ∤ h(x)) are irreducible. Using only polynomials of thisform in the deﬁnitions of the binary lattices
f (x1 , x2 )η((x1 , x2 )) =p
we may deﬁne a familyG≤K ,Sch.−Eis.,Legendre (⊆ G≤K ,Legendre,irreducible ).
22 / 24

Then by G≤K ,Sch.−Eis.,Legendre ⊆ G≤K ,Legendre,irreducible we haveΦℓ (G≤K ,Sch.−Eis,irreducible ) ≤ Φℓ (G≤K ,Legendre,irreducible )≪ ℓKp3/2 log p.
and thusΦℓ (E (G≤K ,Sch.−Eis.,irreducible )) ≪ ℓKp3/2 log p.
Thus the family G≤K ,Sch.−Eis.,Legendre (based on polynomials ofform f (x1 , x2 ) = x1k + x1 x2 g (x1 , x2 ) + x2 h(x2 )) has nearly optimal
cross-combined measure, clearly it is very large (it contains morethan pK (K −.1)/2 lattices).
The binary lattices from this family can be generated easily andfast. Clearly the same holds for the family of sequences
E (G≤K ,Sch.−Eis.,irreducible ).

23 / 24

Thank you for your attention!

24 / 24