On the nonlinearity of the sequence of signs of Kloosterman sums

It is known that Kloosterman sums with prime denominator p take real values, so one can define a sequence of signs of such sums. Several pseudorandom properties of this sequence have recently been studied by Fouvry, Michel, Rivat and Sárközy. Here we use one of their results to estimate a certain important characteristic of this sequence which is also of cryptographic interest. Copyright Clearance Centre, Inc.