Multiplicative character sums and products of sparse integers in residue classes

Abstract

We estimate multiplicative character sums over the integers with a fixed sum of binary digits and apply these results to study the distribution of products of such integers in residues modulo a prime p. Such products have recently appeared in some cryptographic algorithms, thus our results give some quantitative assurances of their pseudorandomness which is crucial for the security of these algorithms