[issue2690] Precompute range length

[Alexander Belopolsky]

Alexander Belopolsky <belopolsky at users.sourceforge.net> added the comment:

On Fri, Apr 25, 2008 at 4:37 PM, Mark Dickinson <report at bugs.python.org> wrote:
..
>  for i in range(1, p):
>     if (i_is_a_nonresidue_modulo_p):
>         break
>
>  Here p might be a 200-digit prime number, and the situation is that half
>  the integers between 1 and p-1 are 'quadratic residues', while the other
>  half are 'quadratic nonresidues';  in practice the residues and
>  nonresidues are mixed up fairly well, so the first nonresidue shows up
>  pretty quickly, but there's no known small upper bound on when the first
>  nonresidue appears.

Hmm, AFAIKT there is always at least one non-residue between 1 and p
and therefore you can just write

for i in itertools.count(1):
    if (i_is_a_nonresidue_modulo_p):
         break

maybe with an additional check for p > 1.

__________________________________
Tracker <report at bugs.python.org>
<http://bugs.python.org/issue2690>
__________________________________