Sunday, March 28, 2010

Upper bound problem

Consider a loop that sums the first p - 1 odd integers modulo p (thus enumerating the quadratic residues modulo p). For each odd integer, an internal counter is incremented, and then the modulo p operation is applied. For example, for p = 19, the first five internal counter values will be 1, 4, 9, and 16. The next value will be 25, which will be mapped into 6 when seen modulo 19 (hence 6 is a quadratic residue modulo 19).

What is the maximum value the internal counter can reach before the modulo operation?

No comments: