Re: question on finding the most efficient quadratic residue filters for Heron triangles

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Sep 24, 2024 at 04:30:09PM -0700, American Citizen wrote:
> To all:
> 
> I work with triangles, specifically Heron triangles, which have rational
> area.
> 
> In running over the 3 sides, say a,b,c, I use quadratic residues to help
> trim down the testing that has to be done to find rational area.
> 
> (1)   area(a,b,c) = sqrt(  (a+b+c) * (-a+b+c) * (a-b+c) * (a+b-c) ) /4
> 
> Currently I am testing all 4 parts of the Heron formula, using the following
> quadratic residues for n = 7695, 6460, 6859, 2565, and 5130 in that order.
> 
> i.e.
> 
> t1 = (a+b+c)
> 
> t2 = (-a+b+c)
> 
> t3 = (a-b+c)
> 
> t4 = (a+b-c)
> 
> test ( (t1%7695) * (t2%7695) * (t3%7695) * (t4%7695) % 7695 to see if the
> modulo value IS a possible legitimate quadratic residue.
> 
> Can GP Pari suggest a very efficient way to filter the a,b,c values? I want
> to use GP-Pari to help me develop very efficient C++ code for Heron triangle
> searches.

Well, one option which worked for us for A5cond is to use hyperellratpoints.
Set a and b, and use hyperellratpoints to find the possible c 

? my(a=12,b=13);hyperellratpoints((a+b+c) * (-a+b+c) * (a-b+c) * (a+b-c),[10^6,1])
%7 = [[-25,0],[-5,120],[-5,-120],[-1,0],[1,0],[5,120],[5,-120],[25,0]]

It is just a sieve, the implementation (from Michael Stoll) is very efficient.

Cheers,
Bill.