n=a²+b²

[bhelmes]

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.

[Batalov]

Originally Posted by bhelmes

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"?

[Gelly]

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.

[Dobri]

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² + b² with the exception of the prime exponents p = 4k + 3 for which there is no such sum.

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++;];

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}}

[Batalov]

Originally Posted by Gelly

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. Here is the jstor link. https://www.jstor.org/stable/2005889

Please explain why would you want to factor a prime number?
What you quoted is for "number is 1 mod 4 and nothing else prime".

[xilman]

Originally Posted by Batalov

Please explain why would you want to factor a prime number?
What you quoted is for "number is 1 mod 4 and nothing else prime".

Factoring into complex primes?

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.

[Gelly]

Originally Posted by Batalov

Please explain why would you want to factor a prime number?
What you quoted is for "number is 1 mod 4 and nothing else prime".

My mistake! I am interested in composites, personally, so evidently I'm having a hard time finding the resources for this even with the hour of research I put in!

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.

[Batalov]

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.

[bhelmes]

Originally Posted by Batalov

Either way. The OP asked for "fast" way. The answer to that is elegant and easy - there is no fast way.

I only needed one composition and the algorithm is described under
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.

[Dr Sardonicus]

Originally Posted by Gelly

My mistake! I am interested in composites, personally, so evidently I'm having a hard time finding the resources for this even with the hour of research I put in!
<snip>

If you want to know the decomposition(s) of a composite number into a sum of two squares, in general you need to factor the number. You certainly need the factorization if you want to be sure of having all the decompositions.

There are situations where you have one decomposition "by formula," e.g. Fermat numbers.

Pari-GP'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 Pari-GP 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.

? 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]
?

[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.

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.