Re: Is list correct datatype for dynamically building results?

[Karim Belabas <Karim.Belabas@u-bordeaux.fr>]

* hermann@stamm-wilbrandt.de [2023-07-22 02:10]:
[...]
> Until now I used "smallest_qnr(n)" function to return smallest quadratic
> non-residue (mod n).
> 
> I extended definition to return c smallest quadratic non-residues:
> 
> ? smallest_qnr(m,s=2,c=1) = {
>     l=List();
>     for(c=-c,-1,
>      forprime(t=s, oo,
>         if(kronecker(t, m)==-1,
>           listput(l,t);
>           s=t+1;
>           break()
>         )
>       )
>     );
>     l
>   };

That function doesn't quite achieve what you claim. Precisely, it
returns the smallest integers t with kronecker(t, m) = -1, which
are the same as quadratic non residues only if m is prime.

If m is composite, say m = a * b, then you may end up with
  kronecker(t,a) = kronecker(t,b) = -1  
for a smaller t that the ones you return. Such t's are not quadratic
residues mod m although your kronecker(t, m) == -1 test won't detect them.

E.g.,

? kronecker(2,9)  
%1 = 1;  \\ obviously; since kronecker(2, 3) = -1
? issquare(Mod(2,9))
%2 = 0;
? [i^2 % 9 | i <- [0..8]]
%3 = [0, 1, 4, 0, 7, 7, 0, 4, 1]

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/