Re: question on trying to use quadratic residues to eliminate needless checks

Bill:

I am trying to develop the C++ code following your suggestion.

On 3/24/25 14:09, Bill Allombert wrote:
> Pick k a small integer as large as possible so that the computation does not
> use too much memory (try k=7).
>
> Take N = 4*vecprod(primes(k)).
for k = 7, we have N = 2042040
> Compute a bit array B so that B[i]==1 iff i is a square modulo N.

Ah, I have not used bit arrays before in C++, are you talking about 
std::bitset ?

> Compute the array of r^2 mod N using C arithmetic for all r.
I assume 0 <= r <= N ?? and this is obviously integer array. Would 
std::vector<long> suffice?
> Compute i = r^2 + s^2 mod N using C arithmetic and check whether B[i]==1.
> If yes do the full check.
I am puzzled. I am trying to avoid the costly r^2 + s^2 operation, 
reducing the sum mod N. Or is that unavoidable?
> This strategy reduces the number of full tests by a factor 1/2^(k+1).

But am I still facing the (r^2+s^2) mod N cost?

Randall