mersenneforum.org > Math n=a²+b²
 Register FAQ Search Today's Posts Mark Forums Read

2022-05-07, 23:34   #12
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

8D816 Posts

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

Quote:
 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.

2022-05-08, 02:26   #13
Dr Sardonicus

Feb 2017
Nowhere

26·7·13 Posts

Quote:
 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.
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.
Code:
? {
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

 2022-05-19, 23:50 #14 bhelmes     Mar 2016 3×7×19 Posts 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.
2022-05-20, 00:54   #15
Dr Sardonicus

Feb 2017
Nowhere

26·7·13 Posts

Quote:
 Originally Posted by bhelmes 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 ?
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!

 2022-06-04, 18:25 #16 bhelmes     Mar 2016 3×7×19 Posts 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. Last fiddled with by bhelmes on 2022-06-04 at 18:36
2022-06-06, 12:38   #17
Dr Sardonicus

Feb 2017
Nowhere

26·7·13 Posts

Quote:
 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.

Last fiddled with by Dr Sardonicus on 2022-06-08 at 15:27 Reason: Strike out incorrect criterion

 2022-06-08, 11:44 #18 bhelmes     Mar 2016 3×7×19 Posts 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² 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 ?
 2022-06-08, 16:10 #19 Dr Sardonicus     Feb 2017 Nowhere 16C016 Posts 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). Last fiddled with by Dr Sardonicus on 2022-06-08 at 16:11

All times are UTC. The time now is 12:14.

Sun Jun 26 12:14:17 UTC 2022 up 73 days, 10:15, 1 user, load averages: 1.02, 1.00, 1.00