Re: efficient foursquare() and/or threesquare1m4() functions

[hermann@stamm-wilbrandt.de]

On 2023-10-07 11:49, John Cremona wrote:
> It's nice to see that an old talk by a Warwick student is still
> useful!
>
> For solving quadratic forms without factoring, see the work of Denis
> Simon (who reads this list), as well as one of my papers, though that
> would give you rational rather than integral solutions.
>
> John Cremona
I will look later.

Because I already implemented generation of ternary quadratic form Q for 
n
- that represents n
- and has determinant 1.

Now I need to figure out how to determine matrix M, such that
M~*Q*M is diagonal matrix. The diagonal entries of M~*Q*M
are three square representation of n.


Is there a PARI/GP function that can determine M given Q?


Here is the initial gist:
https://gist.github.com/Hermann-SW/f13b8adf7d7e3094f0b6db0bce29a7b8

Works for
- even numbers !=0 (mod 4)
- odd numbers !=7 (mod 8)
- odd numbers ==7 (mod 8)
- multiples of 4
as can be seen in 1st gist comment.

For even numbers first b needs to be determined such that -b is
quadratic residue (mod b*n-1) with b*n-1 prime, easy with GP:

        for(vv=0,oo,
            if(ispseudoprime((4*vv+1)*n-1),
                v=vv; break()));
        b=4*v+1;
        p=b*n-1;
        assert(kronecker(-b,p)==1);

First comment of gist also has links to presentation and article.

Regards,

Hermann.