Triangular polynomial Z-actions on Fn and a p cryptographic application 1 Stefan Maubach 1 0 2 Jacobs University Bremen n Bremen, Germany u J [email protected] 8 2 June 30, 2011 ] G A Abstract . h Thisarticle concernsitself withthetriangular permutationgroup,induced t a by triangular polynomial maps over F . The aim of this article is twofold: on p m the one hand,we give an alternative to F -actions on Fn, namely Z-actions on p p [ Fnp and how to describe them as what we call “Z-flows”. On the other hand, 1 wedescribehowthetriangularpermutationgroupcanbeusedinapplications, v in particular we give a cryptographic application for session-key generation. 0 0 The described system has a certain degree of information theoretic security. 8 We compute its efficiency and storage size. 5 To make this work, we give explicit criteria for a triangular permutation . 6 maptohaveonlyoneorbit, whichwecall“maximal orbitmaps”. Wedescribe 0 1 theconjugacyclasses ofmaximalorbitmaps,andshowhowonecanconjugate 1 them even further to the map z −→ z+1 on Z/pnZ. : v i X 1 Introduction r a When generalizing the concept of algebraic additive group actions on kn where k is of characteristic zero, to fields of characteristic p, one tends to (obviously) go to (k,+) actions on kn. These then automatically have order p. This makes the generalization, though seemingly natural in some way, restrictive. For example, a common class of additive group actions is those induced by strictly triangular poly- nomial maps: maps of the form (X +g ,...,X +g ) where g ∈ k[X ,...,X ]. 1 1 n n i 1 i−1 In characteristic zero all these maps can be embedded into a unique algebraic addi- tive group action ϕ : (k,+)×kn −→ kn such that ϕ(1,X ,...,X ) is exactly this 1 n map: analytically speaking, they are the “time one-maps of a (k,+) flow on kn”. However, in characteristic p they do not always have order p, so they cannot be part of a (k+)-action. 1 To give an example, if F = (x+y +z,y +z,z) in characteristic zero, then the additive group action becomes 1 (t,(x,y,z)) −→ (x+ty + (t2 +t)z,y +tz,z). 2 In particular, one can find a triangular polynomial map F having coefficients in T k[t] such that F , being the evaluation of F at T = m, equals Fm for each m ∈ Z. m T One of the nice things of strictly triangular polynomial maps in characteristic zero is indeedthispropertythat itiseasytocompute powersofthemap, i.eif F isastrictly triangular map, then it is easy to compute Fm(v) for any given n ∈ N,v ∈ kn: such a formula F explains this. If one would like to consider (x +y + z,y +z,z) as a T map F3 −→ F3, however, it is not directly possible to give such an explicit formula, p p as one cannot divide by 2! This article shows how to solve this problem for the case k = F , by studying (Z,+)-actions in stead of (k,+) actions. Regardless of these p actions, we explain how to quickly compute Fm(v) for this case. Being able to compute Fm(v) quickly can be useful: in applications it can be useful to have a set of maps ϕ which commute: an example is Diffie-Hellmann key m exchange (see section 6). One takes ϕ = Fm. We explain how to do this, compute m its storage size and computational difficulty, and explain why it has a certain degree of security. All of the theorems in section 2 are motivated by the application in section 5 and 6, while those of section 4 are inspired by it. Section 3 is a preparation for section 4. Contents 1 Introduction 1 2 Triangular polynomial maps 3 2.1 The triangular permutation group B (F ) . . . . . . . . . . . . . . . . 3 n p 2.2 Maximal orbit maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Classification of maximal order maps . . . . . . . . . . . . . . . . . . 7 3 Generalities on polynomial maps Z −→ F 10 p 4 Exponents of triangular maps over F 11 p 4.1 Some more generalities . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 More general triangular groups . . . . . . . . . . . . . . . . . . . . . 12 4.3 Exponents of triangular maps: Z-flows . . . . . . . . . . . . . . . . . 13 5 Efficiently exponentiating maximal orbit triangular maps 15 5.1 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Storage size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.3 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 6 Asymmetric keycryptographic application: Diffie-Hellmann session- key exchange. 17 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.2 System description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 6.3 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.4 Storage size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.5 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 7 Future research 20 2 Triangular polynomial maps 2.1 The triangular permutation group B (F ) n p Below, write A := F [X ,...,X ], and write i for the ideal in A generated by n p 1 n n n the Xp − X . (Writing ı,A if n is clear.) Write x := X + i, and write R := i i i i n F [x ,...,x ] = A /i . In this article, a polynomial map is an element F ∈ (A )n. p 1 n n n n Each F induces a map Fn −→ Fn, i.e. we have a map π : (A )n −→ Hom(Fn,Fn). p p n p p Then in (please read as subset of An, not in ⊂ A !) is the kernel of π. Hence, we may see π(F) as an element of (R )n, and since π is surjective, these elements coincide n one to one with the elements of Hom(Fn,Fn). So it means that we can write maps p p like (x2+x ,x +1+x ) ∈ Hom(Fn,Fn). The set of elements in Hom(Fn,Fn) which 1 2 2 1 p p p p are isomorphisms we denote, as usual, by Perm(Fn). p We define a polynomial map to be triangular if F = (F ,...,F ) where F ∈ 1 n i A = F [X ,X ,...,X ].1 Similarly, F iscalledstrictly triangularifF −X ∈ A = i p 1 2 i i i i−1 F [X ,...,X ]. We state that an element in Hom(Fn,Fn) is strictly triangular if p 1 i−1 p p it is the image of a strictly triangular element in An. n Polynomial maps can be composed, yielding another polynomial map, and hence wehaveanassociative operation◦on(A )n. Thepolynomial mapI := (X ,...,X ) n 1 n is an identity with respect to this operation, and a polynomial map is said to be invertible if it has a polynomial inverse. The polynomial maps which are invertible form a group, denoted GA (F ). Thus, π(GA (F )) ⊆ Perm(Fn) (see [10, 11, 12] n p n p p on the image of this group). The set of strictly triangular polynomial maps forms a subgroup (see [6] section 3.6) denoted by B0(F ) (see [2] for the reasoning behind n p the naming of these groups). One can also define the groups B (A ) ⊂ B (F ) n−m m n p and B0 (A ) ⊂ B0(F ). n−m m n p In this article we will focus on the group π(B0(F )), for which we introduce the n p 1Note that often the definition is to let F ∈ F [X ,...,X ] (and in fact we are used to it i p i n ourselves) but for this article it turned out to be more convenient to choose the definition in the text; some induction proofs then have easier indexes). 3 shorthand notation B (F ). We also have the groups2 n p B (R ) < B (F ). n−m m n p Elements σ ∈ B (F ) thus have a unique representation of the form n p σ = (x +g ,x +g (x ),...,x +g (x ,...,x )) 1 1 2 2 1 n n 1 n where we assume that deg (g ) ≤ p − 1 for each 1 ≤ i,j ≤ n. If σ ∈ B (R ), xi j n−m m then it is like above, only g = 0 if i ≤ m. We will write e = π(I) ∈ Perm(Fn). We i p start with a few generalities on elements of B : n Lemma 2.1. Let σ ∈ B (F ) where q = pm. Then n p i B (R )⊳B (F ). n−m m n p ∼ ∼ ii B (R )/B (R ) = B (R ).In particular, B (R )/B (R ) = n−m m n−m−k m+k k m n−m m n−m−1 m+1 B (R ), which is isomorphic with the group < R ,+ >. 1 m m iii If σ ∈ B (R ), then σp ∈ B (R ). n−m m n−m−1 m+1 iv If σ ∈ B (F ), then σpn = e. n p v Any cycle in σ ∈ B (F ) has length pi for some i. n p pn−pm vi #B (R ) = p(cid:16) p−1 (cid:17).Inparticular, B (F )is a p-sylowsubgroup of Perm(Fn). n−m m n p p vii If gcd(m,p) = 1, then for σ ∈ B (F ) there exists τ ∈ B (F ) such that n p n p τm = σ. Proof. (i) If σ ∈ B (F ), write σ ∈ B (F ) for the first m coordinates. If one n p m m p composes elements σ,τ ∈ B (F ), then one can easily check that (στ) = σ τ . n p m m m Now σ ∈ B (F ) satisfies σ ∈ B (R ) if and only if σ = e ∈ B (R ). Thus, n p n−m m m n−m m if σ ∈ B (R ) and τ ∈ B (F ), then (τ−1στ) = τ−1eτ = e ∈ B (R ), hence n−m m n p m m m n−m m B (R ) is closed under conjugation by elements of B (F ) and hence normal. n−m m n p (ii) A proof sketch to save space: modding out B (R ) removes the last n−m−k m+k n−m−k coordinates and leaves the first m+k coordinates intact. To understand B (R) for a ring R, note that elements are of the form (x +r) and that (x +r)(x + 1 1 1 1 s) = (x +r+s). 1 (iii) Any element in < R ,+ > has order p, hence if σ ∈ B (R ) then σ + m n−m m 2There’s a small formal issue here: if σ ∈ Bk(R) then σ = (x1 + g1,...,xn + gn) where gi ∈ R[x1,...,xi−1], but we actually mean σ ∈ Bn−m(Rm) then σ = (x1+m+g1+m,...,xn+gn) where gi+m ∈Rm[x1+m,...,xi+m−1], and not even that: we identify (x1+m+g1+m,...,xn+gn) with(x1,x2,...,xm,x1+m+g1+m,...,xn+gn). However,theseformalthingsareeasilyfixed,and wedonotwanttointerrupttheflowofthe articlewiththese formalities: allelementsarefromthe group B (F ) and the groups mentioned are all subgroups of this group. n p 4 B (R ) ∈ B (R )/B (R )hasorderp; henceσp ∈ B (R ). n−m−1 m+1 n−m m n−m−1 m+1 n−m−1 m+1 (iv) Applying (iii) n times, yields that if σ ∈ B (F ) = B (R ), then σpn ∈ B (R ) n p n 0 0 n which is the trivial group. (v) follows easily from (iv). (vi): The number of coefficients of g is pi−1. Hence, an element in B (R ) is i n−m m determined by pm + pm+1 + ... + pn = pmpn−m−1 coefficients. The stated formula p−1 follows since each coefficient can take p values. (vii) Since (m,pn) = 1 there exist a,b ∈ Z such that am+bpn = 1. Pick τ := σa, then τm = σam = σ. In respect to lemma 2.1 part (vi) we mention the papers of Kaluznin from 1945 and 1947 [7, 8] which were motivated by finding the p-sylow subgroups of Perm(N) where N ∈ N∗. His description of the p-sylow groups of Perm(pn) is exactly the triangular permutation group. 2.2 Maximal orbit maps Definition 2.2. We define σ ∈ B (F ) being of maximal orbit if σ consists of one n p permutation cycle of length pn. The reason that we do not generalize the results of this article to other finite fields (i.e. finite extensions of F ) is that there exist no elements of maximal orbit p in B (F ) if m ≥ 2. (One can prove lemma 2.1 part (i) for F for all m, so the n pm pm longest possible orbit is pn in stead of pnm.) Theorem 2.3. σ = (x + g ,...,x + g ) is of maximal orbit if and only if the 1 1 n n coefficient c of xp−1···xp−1 in g is nonzero for each 1 ≤ i ≤ n. Furthermore, if σ i 1 i−1 i is of maximal orbit, then σpn−1(α˜,a) = (α˜,a+(−1)n−1c ) n for each a ∈ F ,α˜ ∈ Fn−1. p p Proof. We will prove the result by induction to n. If n = 1 then σ = (x + g ), 1 1 and this is a cycle of length p if and only if g 6= 0. Suppose the theorem is proven 1 for n −1. Write σ = (σ˜,σ ) where σ˜ can be seen as an element of B (F ). Let n n−1 p α = (α˜,α ) ∈ Fn where α ∈ F ,α˜ ∈ Fn−1. By the induction assumption, σ˜ n p n p p permutes Fn−1 with a pn−1 cycle if and only if the coefficients are as described in p the theorem. In particular, if σ˜ does not permute Fn−1 then let β ∈ Fn−1 such that p p ˜ ˜ iterating σ˜ onα˜ never reaches some β. Then iterating σ onα will never reach (β,α ) n and σ is not of maximal order. So let us assume that σ˜ is of maximal order, and let us try to determine whether the coefficient of (x x ···x )p−1 in σ determines if σ 2 3 n n is of maximal order. Iterating σ˜ to α˜ cycles through all elements α˜0,α˜1,...,α˜pn−1−1 5 (where α˜ := α˜) of Fn−1, and σ˜pn−1(α˜) = α˜. Hence, σi(α) = (α˜ ,c ) for some c ∈ F . 0 p i i i p One sees that σ(α˜ ,c ) = (α˜,c +g (α˜ )) and thus we have that c = c +g (α˜ ), i i i n i i+1 i n i yielding the formula i−1 c := α + g (α˜ ). i 0 n j Xj=0 We apply the above formula for i = pn−1, where we need to compute pn−1−1 g (α˜ ) = g (β). n i n Xj=0 β∈XFnp−1 Wecansplit thesum foreachmonomial appearinging . Bythebelowlemma 2.4we n see that only the term (x x ···x )p−1 is of importance. Hence, if the coefficient 1 3 n−1 of this term in g is zero, then σpn−1(α) = α and σ is not of maximal order, and if n the coefficent is a ∈ F∗, then p σpn−1(α˜,α ) = (α˜,α +(−1)n−1a) n n and hence σ is of maximal order. Lemma 2.4. Let M(x ,...,x ) = xa1xa2 ···xan where 0 ≤ a ≤ p − 1 for each 1 n 1 2 n i 1 ≤ i ≤ n. Then M(α) = 0 unless a = a = ... = a = p −1, when it is α∈Fn 1 2 n p (−1)n. P Proof. We proceed by induction to n. For n = 1 we have a standard exercise on finite fields: we get sums of d-th powers of the elements in F , which we call S. Let p a be a generator of F∗. Then S = p−1(ai)d. Let b = ad. Then S = p−1bi. If p i=1 i=1 d = p − 1, then b = 1 and S = pP− 1 = −1. If d < p − 1, then b 6=P1. Then S(b−1) = bp −1 = 0. Since b−1 6= 0, S = 0. Now assume the lemma has been proven for n−1. Define M˜ = xa2 ···xan. Then 2 n α∈Fnp M(α) = b∈Fp α˜∈Fnp−1ba1M˜(α˜) P = Pb∈FpbPa1 α˜∈Fnp−1M˜(α˜) (induction) = δP· (cid:0)baP1 (cid:1) b∈Fp P where δ = 0 unless a = ... = a = p−1, when it is (−1)n−1, by induction. Now 2 n ba1 = 0 unless when a = p−1, when it is -1. Thus the lemma is proven. b∈Fp 1 P So, the above theorem 2.3 gives a clear citerion in the coefficients appearing in σ for when an element in B (F ) is of maximal order. Now, note that lemma 2.1 part n p (vi) actually tells one that it is possible to find an “m-th root” of any σ ∈ B (F ) n p when (m,p) = 1. For m = p, however, it will not be always possible. (In particular, if σ is of maximal orbit, it is not possible.) This induces a few questions we were unable to solve satisfactory like theorem 2.3 does: 6 Question 2.5. (1) Can one recognise of the coefficients in σ ∈ B (F ) if σ is a p-th power of another n p map in B (F )? In particular, what is B (R )/G where G := {σp | σ ∈ B (F )}. n p n−1 1 n p (2) Can one recognise of the coefficients in σ ∈ B (F ) if σ is a pi-th power of a map n p of maximal orbit? (Note that G in (1) is a fully invariant subgroup of B (F ), and in particular n p normal, see [14] page 28.) There are some necessary requirements, like in (1) σ must be in B (R ) and n−1 1 (consequently) in(2)σ ∈ B (R ), but thesearebynomeanssufficient: (x ,x +x ) n−i i 1 2 1 is not a p-th power while (x ,x +1) is. 1 2 2.3 Classification of maximal order maps The following few lemmas are meant to be tools to reduce the number of coefficients necessary to describe σ. First, we will consider the issue that if two maps are powers of each other, then they are interchangeable in some semse (in particular in the application). After that we will find the conjugacy classes of maximal order maps. Definition 2.6. We say that two permutations c,c′ ∈ Perm(N) where N ∈ N∗ are equivalent if < c >=< c′ >, i.e. there exist a,b ∈ N∗ such that ca = c′,(c′)b = c. Definition 2.7. σ = (x +g ,...,x +g ) ∈ B (F ) is said to be on standard form 1 1 n n n p if σ(0,0,...,0) = (0,0,...,0,1), i.e. the constant terms of g ,...,g are zero and 2 n g = 1. 1 Lemma 2.8. If σ ∈ B (F ) of maximal order, then there is exactly one σ′ ∈ B (F ) n p n p on standard form, such that σ,σ′ are equivalent. In other words, standard form maximal order maps form a representant system of the maximal order maps modulo equivalence. Proof. Write σ = (x +g ,σ˜). Since σ is of maximal order, g 6= 0. Now let a ∈ N 1 1 1 be an inverse of g modulo p. Then σa = (x +ag ,...) = (x +1,...) and by lemma 1 1 1 1 2.1 part (vii), σa is equivalent to σ. So we can assume that g = 1 by replacing σ 1 by σa. Now, starting with O := (0,0,...,0) and iterating σ, then we see that σm(O) = (m mod p,...). So, this first coordinate equals 1 if and only if m mod p = 1 which means that m = ap + 1 for some a ∈ N. Since σ is of maximal order, the sequence O,σ(O),σ2(O),...,σpn−1(O)lists all elements ofFn. The sublist ofvectors p starting with 1 is σ(O),σp+1(O),σ2p+1(O),...,σpn−p+1(O). One of these elements equals (0,0,...,0,1), i.e. there exists exactly one a ∈ N such that σap+1(O) = (0,0,...,0,1). By lemma 2.1 (vii) , σap+1 is equivalent to σ, and satisfies the above requirement. (Uniqueness is automatic, as for a cycle of length pn in Perm(Fn) there p is only one power of that cycle sending O to (0,0,...,0,1). ) 7 We will now focus on finding representants for the conjugacy classes of maximal order maps. Definition 2.9. Write xα = xα1 ···xαn for α ∈ Fn. Define 1 n p R− := F xα n p α∈Fn,α=6 X(p−1,...,p−1) p the subvector space of R without the monomial (x ···x )p−1. n 1 n If σ ∈ B (F ), define σ∗ : R −→ R by σ∗(f) = f(σ). We denote by e∗ the identity n p n n map on R . n Lemma 2.10. If σ ∈ B (F ) is of maximal orbit, then ker(σ∗ − e∗) = F . (The n p p converse is also true: if the kernel is F , then σ is of maximal orbit.) p Proof. Let f ∈ ker(σ∗ −e∗). Then 0 = σ∗(f)−e∗(f) = f(σ)−f so f = f(σ), and thus f = f(σi) for all i. Let α ∈ Fn, then f(α) = f(σi(α)) for each i. Since σ is of p maximal orbit, we thus get that f(α) = f(β) for each β ∈ Fn, in other words, f is p a constant function. Notice that since f ∈ R this indeed means f = 0. n The converse goes similarly: if σ is not of maximal orbit, then f only needs to be constant on the orbits of σ. Corollary 2.11. If σ ∈ B (F ), then Im(σ∗ −e∗) ⊆ R−. If σ is of maximal orbit, n p n then we even have equality Im(σ∗ −e∗) = R−. n Proof. Notethatσ∗(R−) ⊂ R−. Acomputationshowsthat(σ∗−e∗)((x ···x )p−1) ∈ n n 1 n R−. Because of linearity of σ∗ − e∗ we thus have that (σ∗ − e∗)R = (σ∗ − n n e∗)(F (x ···x )p−1 +R−) ⊆ F (σ∗ −e∗)((x ···x )p−1)+(σ∗ −e∗)(R−) ⊆ R−. p 1 n n p 1 n n n The second part follows from lemma 2.10: the kernel has dimension 1, so the image must have codimension 1. Proposition 2.12. Let σ,τ ∈ B (F ) of maximal orbit, i.e. n p σ = (x +λ , x +λ xp−1+g , x +λ (x x )p−1+g ,..., x +λ (x ···x )p−1+g ), 1 1 2 2 1 2 3 3 1 2 3 n n 1 n n τ = (x +µ ,x +µ xp−1+h ,x +µ (x x )p−1+h ,...,x +µ (x ···x )p−1+h ), 1 1 2 2 1 2 3 3 1 2 3 n n 1 n n where λ ,µ ∈ F∗, and g ,h ∈ R . Then there exists ϕ ∈ B (F ) such that i i p i i i−1 n p ϕ−1σϕ = τ if and only if λ = µ for all 1 ≤ i ≤ n. If ϕ exists, then one may i i additionally assume ϕ to be on standard form (see definition 2.7), and then ϕ is unique. The above proposition hence shows that λ ,...,λ is a defining invariant for σ. 1 n Proof. By induction to n. The case n = 1 is obvious (one picks ϕ = (x +1), which 1 is on standard form). Write σ = (σ˜,x + g ),τ = (τ˜,x + h ). The induction n n n n assumption means we can find a unique standard form map ϕ˜ in n − 1 variables 8 such that ϕ˜−1σϕ˜ = τ˜ if and only if λ = µ ,...,λ = µ . We will extend 1 1 n−1 n−1 ϕ := (ϕ˜,x )φ where φ := (x ,...,x ,x +f ). Write (ϕ˜,x )−1σ(ϕ˜,x ) = (τ˜,x + n 1 n−1 n n n n n λ (x ···x )p−1 + k ) where k ∈ R− . Now a computation reveals φ−1(τ˜,x + n 1 n n n n−1 n λ (x ···x )p−1 + k )φ = (τ˜,x + λ (x ···x )p−1 + k + (e∗ − τ˜∗)(f )). We thus n 1 n n n n 1 n n n are (only) able to change λ (x ···x )p−1+k by elements of R− as corollary 2.11 n 1 n n n−1 shows, meaning that τ and σ are only conjugate if λ = µ . Let us assume the n n latter, and pick f so that (e∗−τ˜∗)(f ) = k . If we assume f to have constant part n n n n zero then f is unique. ϕ is now on normal form by construction, and the above n shows that it is unique. Definition 2.13. Define δ ∈ R as the polynomial such that δ (p−1,...,p−1) = 1 i i i and δ(α) = 0 for all other α ∈ Fi. (And δ = 1.) Then define p 0 ∆ := (x +δ ,x +δ ,...,x +δ ). 1 0 2 1 n n−1 Theorem 2.14. Let σ ∈ B (F ) of maximal orbit. Then there exist a unique ϕ ∈ n p B (F ) on standard form, and a diagonal linear map D, such that D−1ϕ−1σϕD = ∆. n p Proof. Write µ for the coefficient of (x ···x )p−1 in δ (µ = 1). By proposition i 1 i−1 i−1 1 2.12 we see that σ is equivalent to (x + λ ,x + λ δ ,...,x + λ δ ) for some 1 1 2 2 1 n n n−1 λ ∈ F∗. Write D := (λ x ,...,λ x ). By proposition 2.12 there exists a unique i p 1 1 n n ϕ ∈ B (F ) on standard form such that ϕ−1σϕ = (x + λ ,x + λ δ (D−1),x + n p 1 1 2 2 1 3 λ δ (D−1),...,x +λ δ (D−1)). Now a computation reveals that D−1ϕ−1σϕD = 3 2 n n n−1 ∆. The above theorem thus enables us to see all maximal orbit maps as a unique conjugate of one map, namely ∆. This map is, in some sense, very simple, as the following remark shows: Remark 2.15. Define the bijection ζ : Z/pnZ −→ (F )n by ζ(a + a p + ... + p 0 1 a pn−1) = (a ,...,a ) mod p where 0 ≤ a ≤ p −1. Then ζ∆ζ−1 is the map n−1 0 n−1 i m −→ m+1. The following lemma is specifically necessary for the application in section 5, in order to prove a certain degree of security. Lemma 2.16. Let σ ∈ B (F ) be of maximal orbit, and let α ∈ Fn for 1 ≤ i ≤ m+1 n p i p and β := σ(α ). Let i i Ω := {τ ∈ B (F ) | τ(α ) = β , 1 ≤ i ≤ m, τ of maximal orbit}. n p i i Then for any j ∈ N, j ≤ log (m), τ ∈ Ω, τ (α ) is fixed, while for any j > log (m), p j m p the values τ (α) where τ runs over Ω are uniformly distributed on F . j p Hence, when knowing m pairs (α ,σ(α )) of a specific σ as above, then given another i i value α , one can predict the first [log (m)] coordinates of σ(α ) with 100% m+1 p m+1 certainty, while the other coordinates are fully unknown. 9 Proof. Let σ = (f ,...,f ) like stated. Note that f = x +g (x ,...,x ) and that 1 n j j j 1 j−1 g has pj−1 coefficients (of which one, the coefficient of (x x ···x )p−1, is nonzero, j 1 2 j−1 a fact we will ignore). What in fact is given, is foreach 0 ≤ j ≤ n−1 a list of mpairs (α ,g (α )). Each such pair gives one linear equation on the coefficients of g . i n−j i n−j If j ≤ log (m), then pj ≤ m, and we have an overdetermined set of linear equations, p so g is fixed. If j > log (m), then pj > m, and we have an underdetermined set n−j p of linear equations on the coefficients of g . It is now standard to see that g can n−j n−j still be any value, and the possible outcomes of g can appear with equal chance. n−j (The set of degree p polynomials in one variable where p − 1 values are fixed, is exactly of size p: for each value of F there’s one polynomial. ) p 3 Generalities on polynomial maps Z −→ F p The below definitions we took from [4]. These concepts first appeared in [13]. Definition 3.1. Let A,B ⊆ Q. Then define Int(A,B) := {f ∈ Q[T] | f(A) ⊆ B}. In this article, A will be Z or Z, and B = Z. In particular, we abbreviate (p) Int(Z) = Int(Z,Z). Note that Int(A,B) is a subring of Q[T]. The following is a well-known lemma: Lemma 3.2. T T Int(Z) = Z = Z i ∈ N . (cid:18)i(cid:19) (cid:20)(cid:18)i(cid:19) (cid:21) Mi∈N Proof. (sketch) Let V be the set of polynomials of degree d and less having coeffi- cients in Q. The polynomials T , T ,..., T form a Q-basis for V. This means 0 1 d that f = d a T for some(cid:0) a(cid:1) (cid:0)∈(cid:1)Q. L(cid:0)et(cid:1)v = (f(0),f(1),...,f(d)) ∈ Zd+1, i=0 i i i ~a = (a ,a ,P...,a )(cid:0). D(cid:1)efine A := ( i ) of size (d+1)×(d+1). Then v = A~a where 0 1 d j A has coefficients in Z, is of upper(cid:0)tr(cid:1)iangular form, and has only 1’s on the diagonal. Hence, A is invertible with an inverse having coefficients in Z. Thus, ~a = A−1v is a vector in Zd+1 proving the lemma. Corollary 3.3. T T Int(Z,Z ) = Z = Z i ∈ N . (p) (p) (p) (cid:18)i(cid:19) (cid:20)(cid:18)i(cid:19) (cid:21) Mi∈N If f ∈ Z[ T | m ∈ N] then it makes sense to consider the map Z −→ F given m p by n −→ f(n(cid:0)) (cid:1)mod p. Also, if r ∈ Z , then it makes sense to write down r mod p (p) in the following way: if r = a where a ∈ Z,b ∈ Z\pZ then r mod p = (a mod p)(b b mod p)−1. 10