Re: Is list correct datatype for dynamically building results?

[Denis Simon <denis.simon@unicaen.fr>]

Hi Hermann,

If you know in advance the size of your output, then you should probably use a t_VEC of that size.
In this situation the dynamically building is not necessary.

smallest_qnr(m,s=2,c=1) = {
     my( l=vector(c) );
     my( i = 1);
     forprime(p=s, oo,
        if(kronecker(p, m)==-1,
          l[i] = p;
	  i++;
	  if( i > c, break())
	)
     );
     l
     }

Denis SIMON.

----- Mail original -----
> De: "hermann" <hermann@stamm-wilbrandt.de>
> À: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> Envoyé: Samedi 22 Juillet 2023 02:10:15
> Objet: Is list correct datatype for dynamically building results?

> Or better t_VEC?
> 
> I learned from Bill on nice infinite forprime() loops.
> And exiting based on kronecker().
> 
> 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
>   };
> ?
> 
> Smallest 5 qnrs starting with 2:
> 
> ? smallest_qnr(85,,5)
> %128 = List([2, 11, 13, 29, 31])
> ?
> 
> Smallest 5 qnrs starting with 32:
> 
> ? smallest_qnr(85,32,5)
> %129 = List([41, 43, 47, 53, 61])
> ?
> 
> 
> Above function is fast for really huge numbers, eg. 1million-digit
> prime.
> 
> So it allows to return smallest qnrs for all RSA-numbers, not only the
> already factored ones:
> 
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp
> 
> ? \r RSA_numbers_factored
> validate(rsa): ✓
> ? for(i=1,#rsa,[l,n]=rsa[i][1..2];print("RSA-",l,": ",
> smallest_qnr(n,2,5)))
> RSA-59: List([2, 3, 11, 13, 17])
> RSA-79: List([3, 7, 11, 23, 29])
> RSA-100: List([2, 3, 17, 19, 23])
> RSA-110: List([2, 3, 5, 11, 23])
> RSA-120: List([3, 7, 11, 13, 17])
> RSA-129: List([2, 3, 7, 11, 13])
> RSA-130: List([2, 5, 7, 17, 31])
> RSA-140: List([3, 13, 17, 23, 37])
> RSA-150: List([2, 3, 5, 11, 19])
> RSA-155: List([5, 19, 29, 37, 41])
> RSA-160: List([5, 7, 11, 17, 19])
> RSA-170: List([3, 11, 17, 29, 37])
> RSA-576: List([2, 11, 13, 37, 41])
> RSA-180: List([11, 13, 17, 23, 31])
> RSA-190: List([7, 11, 31, 37, 43])
> RSA-640: List([3, 7, 11, 13, 17])
> RSA-200: List([3, 5, 7, 11, 17])
> RSA-210: List([2, 3, 5, 7, 19])
> RSA-704: List([3, 7, 11, 13, 17])
> RSA-220: List([2, 13, 19, 29, 31])
> RSA-230: List([7, 11, 13, 19, 53])
> RSA-232: List([3, 11, 19, 29, 31])
> RSA-768: List([2, 5, 7, 11, 13])
> RSA-240: List([2, 3, 13, 19, 37])
> RSA-250: List([5, 7, 13, 31, 37])
> RSA-260: List([3, 13, 17, 19, 41])
> RSA-270: List([3, 5, 11, 17, 23])
> RSA-896: List([3, 7, 11, 23, 29])
> RSA-280: List([2, 11, 13, 19, 23])
> RSA-290: List([3, 11, 17, 19, 23])
> RSA-300: List([3, 5, 11, 13, 23])
> RSA-309: List([2, 7, 11, 19, 23])
> RSA-1024: List([2, 3, 5, 13, 17])
> RSA-310: List([7, 17, 19, 29, 31])
> RSA-320: List([2, 5, 7, 11, 17])
> RSA-330: List([2, 3, 5, 7, 13])
> RSA-340: List([5, 17, 19, 29, 41])
> RSA-350: List([3, 7, 11, 13, 17])
> RSA-360: List([11, 23, 37, 47, 53])
> RSA-370: List([2, 11, 17, 29, 31])
> RSA-380: List([3, 7, 13, 23, 41])
> RSA-390: List([7, 17, 19, 47, 59])
> RSA-400: List([5, 7, 11, 13, 19])
> RSA-410: List([3, 7, 11, 19, 23])
> RSA-420: List([2, 3, 7, 13, 17])
> RSA-430: List([2, 7, 29, 31, 37])
> RSA-440: List([2, 3, 7, 11, 19])
> RSA-450: List([5, 7, 11, 17, 23])
> RSA-460: List([2, 11, 13, 19, 23])
> RSA-1536: List([2, 3, 7, 19, 23])
> RSA-470: List([7, 11, 17, 23, 37])
> RSA-480: List([3, 5, 7, 17, 19])
> RSA-490: List([2, 3, 17, 19, 23])
> RSA-500: List([7, 17, 23, 37, 41])
> RSA-617: List([2, 5, 17, 19, 37])
> RSA-2048: List([2, 3, 5, 7, 11])
> ?
> 
> 
> Regards,
> 
> Hermann.
> 
> 
> P.S:
> Just started computation of "sqrt(-1) (mod p)" for  9,383,761-digit
> prime. Not with Pari, but with libgmpxx mpz_powm() because it is a bit
> faster. Basically it computes Mod(3,p)^(2^31172165)^10223 -- runtime
> forcast of minimal 75.4 days(!) on fast AMD 7600X CPU:
> https://github.com/Hermann-SW/9383761-digit-prime/tree/main#readme
> 
> pi@pi400-64:~ $ ssh hermann@7600x uptime
>  02:05:44 up 1 day,  8:32,  0 users,  load average: 1.00, 1.00, 1.00
> pi@pi400-64:~ $