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

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

My computer finished the run (about 2 days with inefficient code)

Only 1,666 values from 1,492,627 were found to create a body cuboid, of 
which only 1,153 were found. (some cuboids shared values)

This is a very low percentage of 0.111% using the side = 288807105787200 
(which was deliberately chosen of a product of low value primes)

Thank you again Karim and Bill for the posts.

Randall

On 3/25/25 01:56, Karim Belabas wrote:
> * American Citizen [2025-03-25 01:09]:
> [...]
> > > 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?
> Certainly not: you precomputed the r^2 mod N (and the s^2 mod N) separately
> [a linear cost, not quadratic as your number of checks]
>
> Hence r^2 + s^2 mod N is an simple addition mod N
>
>    ulong
>    Fl_add(ulong a, ulong b, ulong N)
>    {
>      ulong res = a + b;
>      return (res >= N || res < a) ? res - N : res;
>    }
>
> Cheers,
>
>      K.B.