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

On Sun, Mar 23, 2025 at 05:55:50PM -0700, American Citizen wrote:
> Hello:
> 
> I am trying to determine if using quadratic residues will shorten down the
> time to check two numbers, a,b such that a^2 + b^2 = square (say s^2)
> 
> In regard to body cuboids, I looked at the side = 288807105787200
> 
> Using the divisors of side^2, we find that 1,492,627 integers or fractions
> exist, such that x^2 + 288807105787200^2 = s^2 where x is in Z or Q
> (actually n/2)
> 
> There are 1,262,992 integers with this property and 229,635 rationals (all
> have denominator 2) with this property.
> 
> I am looking for two numbers r,s from this pile of 1,492,627 values such
> that r^2 + s^2 = t^2 (t either integer or rational)

Assuming you do the computation in C, not in GP:

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)).
Compute a bit array B so that B[i]==1 iff i is a square modulo N.

Compute the array of r^2 mod N using C arithmetic for all r.

Compute i = r^2 + s^2 mod N using C arithmetic and check whether B[i]==1.
If yes do the full check.

This strategy reduces the number of full tests by a factor 1/2^(k+1).

Cheers,
Bill.