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

[American Citizen <website.reader3@gmail.com>]

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