> 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.

Sure.  It's just uglier that way. :-)  And I feel it would be mildly 
annoying not to be able to use the obvious tool for the job, for subtle 
reasons.  It's also a potential source of bugs: one might write such code 
using range and only discover later that it fails unexpectedly for large 
inputs.

These really aren't serious objections---just mild preferences.  I'll stop 
being disruptive now :)