An Application of the Gauss Lemma to the Study of Pseudorandom Sequences Based on Quadratic Residues

V. E. Tarakanov

Matematičeskie zametki, Tome 73 (2003) no. 4, pp. 603-612

Résumé

In the context of the study of pseudorandom sequences that use quadratic residues modulo the prime $p$, the constructive description of the set of prime moduli for which given integers are quadratic residues is considered. Using the Gauss Lemma, we prove a criterion of combinatorial nature for a given integer $a$ to be a quadratic residue prime modulo $p$. It is shown how to apply this criterion to the problem of effective description of the prime moduli $p$ satisfying the equation $\bigl(\frac ap\bigr)=1$ for each $p$ from a given finite set $M$.