n=a²+b²

[a1call]

You can always try to find the squares by trial and erfor. After all that is the Fermat’s factorization method. But:

Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.

https://en.wikipedia.org/wiki/Fermat...ization_method

For a formulaic solution to the problem, well it’s been a work in progress for centuries now. No proof that it can’t exist AFAIK.

[Dr Sardonicus]

Originally Posted by Gelly

Oh shoot my mistake! I'm sure I come off super foolish now that I remember what the particular context was. It seems like to get the sum of squares representation of any composite requires factorization, and I thought that was wrong because we know the sum of squares representation of C1133, the large composite factor of F12.
<snip>

A representation of a cofactor of a sum of two squares can be found by finding the representations of the known factors and dividing out.

I find this easiest to do using the complex factors a + b*I and a - b*I of a^2 + b^2. But it's a little tricky, because you have to choose the "correct" conjugate divisor of each prime factor. You only get one representation of the cofactor, of course.

The following is ridiculously clunky, but it gets the job done.

? {
v=[114689, 26017793, 63766529, 190274191361, 1256132134125569, 568630647535356955169033410940867804839360742060818433];
s2sq=Qfb(1,0,1);
w=vector(#v, i, qfbsolve(s2sq,v[i])*[1,I]~);
z=I+2^2048;
for(i=1,#w,if(gcd(w[i],z)==1,w[i]=conj(w[i])));
q=z/prod(i=1,#w,w[i]);
print(abs(real(q)));
print();
print(abs(imag(q)))
}
200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916

11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591

[bhelmes]

A peaceful and pleasant night for you,

if a compositon of n=x²+y² exists and n not a prime,
how many different compostions exist depending of the number of factors of n ?

Please have patience with me, I try to do progress in math and invite other to participate.

[Dr Sardonicus]

Originally Posted by bhelmes

<snip>
if a compositon of n=x²+y² exists and n not a prime,
how many different compostions exist depending of the number of factors of n ?
<snip>

1. Drop the exclusion of primes.
2. Say "representations" rather than "compositions".
3. The meaning of "different" may be different from what you think it is.

Happy googling!

[bhelmes]

A peaceful day for you,

Is there a known algorithm for
x²+y²=m²+n²=d mod f

I think it is easier than to find x²+y²=0 mod p

Any interesting suggestion how to speed up Gimps ?
I really need a new Mp.

[Dr Sardonicus]

Originally Posted by bhelmes

Is there a known algorithm for
x²+y²=m²+n²=d mod f

Let g = gcd(d, f).

1. If g > 1 and any prime-power factor of g is congruent to 3 (mod 4) there is no solution.
2. If g = 1, f is divisible by 4 and d == 3 (mod 4) there is no solution.
3. If g = 1, f is divisible by 4, d == 1 (mod 4), r == 1 (mod 4), s == 1 (mod 4), and r*s == d (mod f) [e.g. r = d, s = 1], find primes p == r (mod f) and q == s (mod f). Then p*q provides a solution.

[bhelmes]

A peaceful and pleasant day for you,

I miss the case
4. g=1 and f odd

I am searching for x²+y²=m²+n²=d mod f, resp. two sums of squares with the same norm d mod f.

Algorithm:
choose a value r>0 and a start point x²+y²>f+r with x>y

if x²+y²>f+r then x:=x-1
if x²+y²<f then y:=y+1
if x²+y² > 0 mod f and x²+y² < r mod f store the pair with the norm and y:=y+1
if two points with the same norm is found stop the algorithm.

A visualisation and examples for small numbers can be found under
http://devalco.de/unit_circle/system_tangens.php

Is there a better algorithm available ?

[Dr Sardonicus]

I was completely wrong about the criterion for g > 1 with g = gcd(d, f). I struck it out.

As an example, x^2 + y^2 == 3 (mod 15) is solvable (e.g. x = y = 3). I had failed to consider that x^2 + y^2 could be divisible by a higher power of a prime than g, but the congruence (mod f) could still hold.

Mea culpa

A better approach is probably to factor the modulus f, and solve x^2 + y^2 == d (mod p) for each prime factor p of f. If f is divisible by a higher power of p, such solutions can be "lifted" to solutions mod p^2, etc.

If p is prime, one way to solve x^2 + y^2 == d (mod p) [assuming r is not 0 (mod p)] is by trial. Trying y = i = 0, 1, 2, etc. factor x^2 + i^2 - d (mod p). If it splits into linear factors, they give solutions to x^2 + i^2 == d (mod p). This should turn up a couple of solutions in fairly short order.

If d is 0 (mod p) there is always the solution x = y = 0 (mod p). If p = 2 there is the solution x = y = 1 (mod 2). If p is congruent to 1 (mod 4) there are several solutions.

Again, if f is divisible by a higher power of p, solutions mod p can be "lifted" to solutions mod p^2, p^3, etc.

Finally, solutions modulo the prime (power) factors of f can be combined using the Chinese Remainder Theorem.

Take d = 3, f = 15.

x^2 + y^2 == 3 (mod 3) [i.e. 0 mod 3] has the solution x = y = 0 (mod 3).

x^2 + y^2 = 3 (mod 5): Trying i = 0, no luck; i = 1, no luck. Trying i = 2, x^2 + 1 = 0 (mod 5) has the solutions x = 2 or 3 (mod 5).

Combining the mod 3 and mod 5 solutions we get 12^2 + 12^2, 3^2 + 12^2, and 3^2 + 3^2 == 3 (mod 15).