Large Families of Pseudorandom Subsets Formed by Power Residues

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 proper- ties. One of these examples included permutation polynomials f(X) ∈ Fp[X] and d-powers in Fp. 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.