20220504, 23:38  #1 
Mar 2016
2^{2}·101 Posts 
n=a²+b²
A peaceful and pleasant night for you,
if n odd and not a square and n, a, b element N how do I find (fast) the composition n=a²+b² ? Thanks in advance if you spent me some lines or a link. 
20220505, 00:55  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23255_{8} Posts 
Using Google is too hard?
Just type "sum of two squares". > https://en.wikipedia.org/wiki/Sum_of...quares_theorem Would you rather like to have a link to "let me google that for you"? 
20220506, 11:25  #3 
May 2020
47 Posts 
Perhaps I am horribly dull, but I found researching based on the "just google these four words" criteria became horribly unclear, as people on the internet are more concerned with whether you can represent a number as the sum of two squares, or how to factorize when you know two ways of writing a number as the sum of squares.
I want to save the trouble for anyone else interested in finding a sum of squares decomposition given only the fact that the number is 1 mod 4 and nothing else  no factorization, nothing. I eventually stumbled upon Brillhart's 1972 paper "Note on representing a prime as a sum of two squares.", which not only gives a lot of methods to decompose a number into a sum of two squares, but also the most efficient way to do so. Here is the jstor link. https://www.jstor.org/stable/2005889 I would much rather math research on something so basic not be buried in references and muddled Wikipedia jargon, because this should be a lot easier to find  mostly, so people can find out for themselves why it's so hard to get two sum of two squares decompositions given an unfactorized number. 
20220506, 16:01  #4 
"Καλός"
May 2018
2^{2}·5·17 Posts 
The Wolfram code below represents the prime exponent p of each known Mersenne prime 2^{p}1 as a unique sum of two squares p = a^{2} + b^{2} with the exception of the prime exponents p = 4k + 3 for which there is no such sum.
Code:
MPData = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 77232917, 82589933}; Np = 51; ic = 1; While[ic <= Np, p = MPData[[ic]]; Ms = FindInstance[(p == ac^2 + bc^2) && (ac <= bc), {ac, bc}, PositiveIntegers, 2]; Print[p, " ", Mod[p, 4], " ", Ms]; ic++;]; Code:
2 2 {{ac>1,bc>1}} 3 3 {} 5 1 {{ac>1,bc>2}} 7 3 {} 13 1 {{ac>2,bc>3}} 17 1 {{ac>1,bc>4}} 19 3 {} 31 3 {} 61 1 {{ac>5,bc>6}} 89 1 {{ac>5,bc>8}} 107 3 {} 127 3 {} 521 1 {{ac>11,bc>20}} 607 3 {} 1279 3 {} 2203 3 {} 2281 1 {{ac>16,bc>45}} 3217 1 {{ac>9,bc>56}} 4253 1 {{ac>38,bc>53}} 4423 3 {} 9689 1 {{ac>35,bc>92}} 9941 1 {{ac>70,bc>71}} 11213 1 {{ac>67,bc>82}} 19937 1 {{ac>76,bc>119}} 21701 1 {{ac>26,bc>145}} 23209 1 {{ac>40,bc>147}} 44497 1 {{ac>64,bc>201}} 86243 3 {} 110503 3 {} 132049 1 {{ac>120,bc>343}} 216091 3 {} 756839 3 {} 859433 1 {{ac>187,bc>908}} 1257787 3 {} 1398269 1 {{ac>610,bc>1013}} 2976221 1 {{ac>1189,bc>1250}} 3021377 1 {{ac>244,bc>1721}} 6972593 1 {{ac>352,bc>2617}} 13466917 1 {{ac>2241,bc>2906}} 20996011 3 {} 24036583 3 {} 25964951 3 {} 30402457 1 {{ac>3291,bc>4424}} 32582657 1 {{ac>3536,bc>4481}} 37156667 3 {} 42643801 1 {{ac>285,bc>6524}} 43112609 1 {{ac>3880,bc>5297}} 57885161 1 {{ac>2444,bc>7205}} 74207281 1 {{ac>2716,bc>8175}} 77232917 1 {{ac>2329,bc>8474}} 82589933 1 {{ac>5122,bc>7507}} 
20220506, 18:19  #5  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,901 Posts 
Quote:
What you quoted is for "number is 1 mod 4 and 

20220506, 19:58  #6  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2×5,711 Posts 
Quote:
One of the prized books in my library is a table of complex primes. Cost me all of 10p about 40 years ago. Handbook for First Complex Numbers, Part One 1 List of First 332,395 Complex Prime Numbers by Kogbetliantz and Krikorian to be precise. 

20220506, 22:33  #7  
May 2020
47 Posts 
Quote:
Can you just tell us the magic words to find the sum of two squares decomposition for composites? Or do you also not know and assumed it would be easy to find on google? I really truly want to know how it works, considering I remember a while ago that PARI/GP had some function for it with an esoteric name. 

20220506, 23:35  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23255_{8} Posts 
Step 1. You factor n. ("there is no royal road to geometry, your excellency" (c) Euclid)
Step 2. If there is a prime factor ≡ 3{mod 4} repeated odd number of times?  then Stop. No solution. Step 3. There are established algorithms. Wiki has a short explanation (see post #2 (!!) ); then just one jump via Wiki to OEIS; then use OEIS links. . . . . . . Ok, here is at least one way: solve each prime factor for sum of squares. then combine them using https://en.wikipedia.org/wiki/Brahma...nacci_identity Either way. The OP asked for "fast" way. The answer to that is elegant and easy  there is no fast way. 
20220507, 00:26  #9  
Mar 2016
2^{2}·101 Posts 
Quote:
https://en.wikipedia.org/wiki/Fermat...of_two_squares The english version of wikipedia is much better than the german, where no algorithm is indicated. Corona time was not funny, the war in Ukraine ugly and perhaps my question was a try to cheer you up. 

20220507, 12:05  #10  
Feb 2017
Nowhere
7·29^{2} Posts 
Quote:
There are situations where you have one decomposition "by formula," e.g. Fermat numbers. PariGP's qfbsolve(Q, n) function now works for composite n (it used to work only for prime n). Another function that works for composite n (assuming PariGP can find the factorization) is bnfisintnorm(). You first have to define the number field k = Q(i) where i^2 + 1 = 0. This function in effect gives each representation twice. Code:
? Q=Qfb(1,0,1);v=qfbsolve(Q,1009) %1 = [28, 15] ? k=bnfinit(t^2+1);bnfisintnorm(k,1009) %2 = [15*t  28, 15*t + 28] ? bnfisintnorm(k,1105) %3 = [33*t + 4, 31*t + 12, 32*t + 9, 24*t  23, 23*t + 24, 9*t  32, 12*t  31, 4*t + 33] ? 

20220507, 20:04  #11 
May 2020
47 Posts 
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.
But that method requires it to be a factor of a Fermat number, and to know the cofactors! Super sorry to be so pushy about it! Thank you all for the help for the true answer. 