Algebraic properties of polynomial

iterates

Alina Ostafe
Department of Computing

Macquarie University
1
Motivation

1. Better and cryptographically stronger pseudo-

random number generators (PRNG) as linear
constructions has been succefully attacked.

We recall that an attack on a PRNG is an

algorithm that observes several outputs of a
PRNG and then able to continue to generate
the same sequence with a nontrivial probability.

2. Possible new hash functions

3. Links with traditional questions in the theory

of algebraic dynamical systems such as degree
growth, periods, etc.
2

General setting

p: prime number
IFp: finite field of p elements.

F = {F1, . . . , Fm}: system of m polynomials/rational

functions in m variables over IFp

How do we iterate?

Define the k-th iteration of the rational functions

Fi by the recurrence relation
(0) (k) (k−1) (k−1)
Fi = Xi, Fi = Fi(F1 , . . . , Fm ),
where i = 1, . . . , m and k = 1, 2, . . ..
3
Our motivation:

Polynomial Pseudorandom Number Generators (PRNG)

Consider the PRNG defined by a recurrence rela-

tion in IFp
un+1 = F(un),
where
un = (un,1, . . . , un,m)
and

F = (F1(X1, . . . , Xm), . . . , Fm(X1, . . . , Xm)).

In particular, for any n, k ≥ 0 and i = 1, . . . , m we

have
un+k = F(k)(un).
IFp = finite field =⇒ sequence of vectors (wn) is
eventually periodic with some period τ ≤ pm.
4
Quality of PRNG
Uniformity of distribution of PRNG

⇓
Estimating exponential sums

In our case:
 
−1
NX m
X
Sa(N ) = e aiun,i ,
n=0 i=1
where

e(z) = exp(2πiz/p), a = (a1, . . . , am) ∈ Z m.

Informally: Trivial bound

|Sa(N )| ≤ N
(as it is a sum on N roots of unity).

Motivation: Good pseudorandom sequences should

have small values of |Sa(N )|!!! The smaller, the
better!
5
How do we estimate |Sa(N )|?

Standard technique of estimating |Sa(N )| reduces

it to estimating the exponential sum
  
m

(k) (l)
 X X 
e ai(Fi (v) − Fi (v)) .
 

v∈IFm
 
p i=1 

We can now try to apply Weil 1948:

 
 p 
e (F (x1, . . . , xm)) < Dpm−1/2,
 X 


x ,...,x =1 
1 m

where F ∈ IFp[X1, . . . , Xm] is a nonconstant poly-

nomial of degree D.

Remarks:

• The degree plays an important role in the es-

timate of the exponential sum!

• We need linear independence of the iterations

(k)
Fi , k ≥ 1.

• In some special cases elementary methods re-

place the use of the Weil bound and give stronger
bounds!
6
Degree growth

If f is a univariate polynomial of degree d, the

degree growth

deg f (k) = dk
is fully controlled and exponential (if d ≥ 2).

Question: How about the multivariate case?

Clearly the growth cannot be faster than exponen-

tial, but can it be slower?

YES!!

. . . and for us, generally speaking, the slower the

better.
7
What systems do we study?

Ostafe and Shparlinski 2009–2011:

F = {F1, . . . , Fm}: system of m rational functions
in m variables over IFp of the form:
e
F1(X1, . . . , Xm) = X11 G1(X2, . . . , Xm) + H1(X2, . . . , Xm),
...
m−1e
Fm−1(X1, . . . , X m) = Xm−1 Gm−1(Xm) + Hm−1(Xm),
em + h ,
Fm(X1, . . . , Xm) = gmXm m
where

ei ∈ {−1, 1}, Gi, Hi ∈ IFp[Xi+1, . . . , Xm], gm, hm ∈ IFp. g

ei = 1 : Gi has a unique leading monomial,

s
i,i+1 s
Gi(Xi+1, . . . , Xm) = giXi+1 . . . Xmi,m +G
f (X
i i+1 , . . . , Xm ),

gi 6= 0, degXj G
f <s ,
i i,j degXj Hi ≤ si,j , 1 ≤ i < j ≤ m
ei = −1 : Hi has a unique leading monomial
i,i+1 s s
Hi(Xi+1, . . . , Xm) = hiXi+1 . . . Xmi,m +H
f (X
i i+1 , . . . , Xm ),

with

hi 6= 0, degXj H
f <s ,
i i,j degXj Gi ≤ 2si,j , 1 ≤ i < j ≤ m
8

Lemma 1 For the above systems, if ei = 1,

(k)
Fi = XiGi,k (Xi+1, . . . , Xm) + Hi,k (Xi+1, . . . , Xm),
and if ei = −1,

(k) XiRi,k + Si,k

Fi = , i = 1, . . . , m, k = 0, 1, . . . ,
XiRi,k−1 + Si,k−1
where

Gi,k , Hi,k , Ri,k , Si,k ∈ IF(Xi+1, . . . , Xm), i = 1, . . . , m−1.

In both cases,
(k) 1
deg Fi = km−isi,i+1 . . . sm−1,m + ψi(k),
(m − i)!

ψi(T ) ∈ Q[T ], deg ψi < m − i, i = 1, . . . , m − 1.

Conclusion: The degree grows

• polynomially in the number of iterations

• monotonically (beyond a certain point).

Remark: The above effect does not occur in the

univariate case.
9
Why do we win?

• we estimate the exponential sum for ei = 1 for

all i = 1, . . . , m,
  
m−1

(k) (l)
 X X 
e ai(Fi (v) − Fi (v)) ,
 

v∈IFm
 
p i=1 

where, as before, e(z) = exp(2πiz/p) and

(k) (l)
Fi − Fi = Xi(Gi,k − Gi,l ) + Hi,k − Hi,l .

• the case of rational functions will follow more

or less the same... but we have to take care
of the poles!!!
• slow degree growth of the polynomials

Remark: Slow, but not too slow!!! ... so that

Gi,k − Gi,l is nontrivial for k 6= l
• the linearity of the polynomials Fi in Xi

Remark: We do not use the Weil bound. In-

stead we evaluate exponential sume with linear
functions and estimate the number of zeros of
Gi,k − Gi,l , k 6= l: any nontrivial m-variate poly-
nomial of degree D has at most Dpm−1 zeros,
and thus we save p instead of p1/2 from the
Weil bound.
10
Wish list

All results at some point are based on an estimate

of exponential sums with
m−1  
X (k) (l)
La,k,l (v) = ai Fi (v ) − F i (v )
i=1

We want La,k,l (v) to be

• nontrivial (i.e. not to be a constant)

• exponential sums friendly:

(i) of small degree (to apply the Weil bound)

(ii) linear in some of the variables

(iii) to have a low dimensional locus of singular-

ity (to apply the Deligne bound, or Deligne-
like bounds by Katz, etc.)

Properties (i) and (ii) have been exploited in

the above constructions, a dream project is to
find a system with well-controlled property (iii)
and improve previous results.
11
Maximal periods

Ostafe 2010: Let (un) be defined as above with

period τ ≤ pm. If ei = 1 for all i = 1, . . . , m, then
τ = pm if and only if
Y
Gi(v) = 1, gm = 1, deg Ri = (m−i)(p−1),
v∈IFm−i
p

where
(2) (pm−i )
R i = Hi G i . . . G i (mod I)
is of degree at most p − 1 in each variable and I
p p
is the ideal generated by X1 − X1, . . . , Xm − Xm.

Example: m = 2, p ≡ 3 (mod 4),

F1 = X1(f (X2)2+(p+1)/4)+a and F2 = X2+b,

a, b ∈ IF∗p and f ∈ IFp[X] generates a permutation.

Question: When do the systems of rational func-

tions defined above achieve maximal period?

Ostafe and Shparlinski 2011 (in progress): When

all ei = −1, the maximal period reduces to de-
scribing the maximal period of a certain Möbius
transformation defined by the iterations of Fi.
12
Other algebraic properties

• Can we find nontrivial lower bounds for the

(k)
number of monomials of the polynomials Fi ,
for any i = 1, . . . , m, k = 1, 2, . . . over finite
fields?

Fuchs and Zannier 2009:

The number of monomials of the kth iterations
of a univariate rational function over C tends
to infinity with k.

Remark: This is not necessarily the case of

multivariate polynomials ...

Example: Let m = 4, F1 = X1 − X4(X3X1 +

X4X2), F2 = X2 +X3(X3X1 +X4X2), F3 = X3,
F4 = X4. Then, for any k ≥ 1,
(k)
F1 = X1 − kX4(X3X1 + X4X2)
(k)
F2 = X2 + kX3(X3X1 + X4X2).

So, the degree growth is constant, as the num-

ber of monomials at every iteration (over any
field)!!!
13
There are situations (with a bit of dirty tricks
with the characteristic) when

– the degree grows exponentially,

– the number of monomials is constant, or

even decreases to a monomial

. . . at least over finite fields.

p p
Example: Let m = 2, F1 = X1 − X2, F2 =
p p
X1 + X2 over IFq , q = pm. Then

k
 c Xp ,

k = even, jk ∈ {1, 2}
(k) i,k jk
Fi = k k ,
p p
 d (X ± X ), k = odd

i,k 1 2
where ci,k , di,k ∈ IFq , i = 1, 2.

Question: Can we achieve this without cheat-

ing?
 14

• The additive complexity of the polynomials

(k)
Fi , for any i = 1, . . . , m, k = 1, 2, . . ., is the
smallest number of ‘+’ signs in the formulas
evaluating these polynomials.
Note that the additive complexity can be much
smaller than the number of monomials.
Example:
f (X, Y ) = (X 2+2Y )100(3X+Y 3)200+(X 300+Y )10
is of total degree 3000 and thus has a very
long representation via the list of coefficients.
However, the additive complexity is 4 and thus
has a very concise representation/evaluation.
Construct polynomial systems with exponen-
tially degree growth, but with polynomial ad-
ditive complexity growth of their iterations. It
is possible...
Example: f (X) = (x − b)d + b, f (k)(X) = (X −
k
b)d + b, b ∈ IFq , d ≥ 2

• If we have a Gröbner basis (GB) for {F1, . . . , Fm},

(k) (k)
what can we say about the GB of {F1 , . . . , Fm }?
Can we say something about the dimension of
(k) (k)
the ideal generated by F1 , . . . , Fm ?
15
Let’s talk about irreducibility!!!

At some point of the argument we need to esti-

mate the number of zeros of some linear com-
(k)
binations of several distinct iterates Fi (X) of
F1, . . . , Fm.

It is natural to start with studying the same iter-

ates. E.g.: can we say anything interesting about
(k)
the polynomials Fi (X)? Are they irreducible for
any k?
NO RESULTS!
⇓
Let’s start with the univariate case
. . . still no general results yet

... except Gomez, Nicolas, Ostafe and Sadornil

2011, work in progress.

⇓
Let’s start with quadratic polynomials
. . . not too many results but there are some!!
16

Irreducibility of iterations

For a field IF, f ∈ IF[X] is called stable if f (k) ir-

reducible for all k.

• Irreducibility is very common over Q. =⇒ over

IF = Q a “random” polynomial is expected to
be stable. Ahmadi, Luca, Ostafe and Shpar-
linski 2010: proved this for quadratic polyno-
mials.

• Over IFq irreducibility is rare: prob. ∼ 1/d for

a random polynomial of degree d. =⇒ We
expect very few stable polynomials (recall that
deg f (k) grows fast).

– Gomez Perez and Piñera Nicolas 2010: es-

timate on the number of stable quadratic
polynomials for odd q.
– Ahmadi, Luca, Ostafe and Shparlinski 2010:
No stable quadratic polynomial over IF2n ; it
has nothing to do with char = 2 as x2 + t
is stable over IF2(t).
17
Stability testing of quadratic polynomials over IFq

f (X) = aX 2 + bX + c ∈ IFq [X], a 6= 0

γ = −b/2a the unique critical point of f

Critical orbit of f :

Orb(f ) = {f (n)(γ) : n = 2, 3, . . .}
∃t such that f (t)(γ) = f (s)(γ) for some positive
integer s < t.

tf =the smallest value of t with the above condi-

tion. Then:

Orb(f ) = {f (n)(γ) : n = 2, . . . , tf }

Jones and Boston 2009:

f ∈ IFq [X] is stable if and only if the adjusted crit-
ical orbit
[
Orb(f ) = {−f (γ)} Orb(f )
contains no squares.
18
Trivially #Orb(f ) ≤ q and thus one can test f ∈
IFq [X] for stability in q steps.

Ostafe and Shparlinski 2009:

Theorem 2 For any odd q and any stable quadratic

polynomial f ∈ IFq [X] we have
 
tf = O q 3/4 .

Corollary 3 For any odd q, a quadratic polyno-

mial f ∈ IFq [X] can be tested for stability in time
q 3/4+o(1).
19
Stability of arbitrary univariate polynomials over
IFq

Ahmadi, Luca, Ostafe and Shparlinski 2010: even

degree polynomials of the form F = g(f ) where f
is a quadratic polynomial, and g is any polynomial
of degree d

Theorem 4 For any odd q and any stable polyno-

mial F = g(f ) ∈ IFq [X], where f = aX 2 + bX + c ∈
IFq [X] and g ∈ IFq [X] of degree d, we have
 
tF = O q 1−α d ,

where
log 2
αd = .
2 log(4d)

We can say a bit more ...

20
Gomez, Nicolas, Ostafe and Sadornil 2011 (work
in progress):

f ∈ IFq [X] stable with leading coefficient a ∈ IF∗q , q

odd, deg f ≥ 2, (deg f, p) = 1
f 0 nonconstant, γi roots of f 0, i = 1, . . . , deg f − 1

Then

1. if d = deg f is even,
f −1
degY d−1
d
f (n)(γi) | n > 1 }
[ Y
{a { (−1) a
2 f (γi) }
i=1 i=1
contains only non squares in IFq ;

2. if d = deg f is odd,

(d−1) d−1
f (n)(γi)
Y
{ (−1) 2 d | n≥1 }
i=1
contains only squares in IFq .
21

Questions:

• Is there an algorithm to check a quadratic poly-

nomial for stability in Q[X] in finitely many
steps?

• Do there exist stable polynomials of degree kp,

k ≥ 1, over a field of characteristic p?

• Can we say something about the stability of

multivariate polynomials?

Zaharescu 2005: some results about the irre-

ducibility of iterates of multivariate polynomi-
als, but not in the usual way, only with respect
to one variable.