Large families of pseudorandom subsets formed by power residues

Cécile Dartyge (1) , András Sárközy (2)

1 IECL - Institut Élie Cartan de Lorraine
2 Department of Algebra and Number Theory [Budapest]

In an earlier paper the authors introduced the measures of pseudo-randomness of subsets of the set of the positive integers not exceeding N , and they also presented two examples for subsets possessing strong pseudorandom properties. One of these examples included permutation polynomials f (X) ∈ F p [X] and d-powers in F p. This construction is not of much practical use since very little is known on permutation polynomials and there are only very few of them. Here the construction is extended to a large class of polynomials which can be constructed easily, and it is shown that all the subsets belonging to the large family of subsets obtained in this way possess strong pseudorandom properties. The complexity of this large family is also studied.

Mots clés: pseudo-randomness; subset of positive integers; complexity

Domaines: Théorie des nombres [math.NT]

Cécile Dartyge, András Sárközy. Large families of pseudorandom subsets formed by power residues. Uniform Distribution Theory, 2007, 2, pp.73 - 88. ⟨hal-02310146⟩