In the two prior blogs I have explored decomposing primes into two squares. In the first prior blog, I focused on just breaking down primes congruent to one mod 4 into the sum of two squares. In that article I produced a Groovy script to do that breakdown. In the second prior article I extended it to primes congruent to one mod 3 and the decomposition into 3 times a square plus a square. In that blog article I also said this was the other efficiently computable case. That implicitly claimed that I had exhausted the cases that had fairly straightforward efficient algorithms for computation. That got me to thinking, is that really true? Are there any other cases that are efficiently computable with fairly simple algorithms?
In the Wiki Article on Fermat Squares, it states that if a prime is congruent to 1 or 3 mod 8, it can be broken down into two times a square plus a square. Looking at that, I wondered if I could handle that case as well. It involves the number field obtained by adding the square root of negative two, and that is also an Euclidean Domain. So the only real issue was finding a multiplicative square root of -2 in the integers mod p. And I remembered that if i is the square root of negative one, then (i + 1) * (i + 1) = 2i. From that initial thought, I was able to piece together an algorithm for this case.
In what follows I give a synopsis of the math that I used for this case. One of the rules I used is that I would not be allowed to consult any text book or article for the actual math, even though there is quite a nice textbook that you can find at Primes of The Form x2 + ny2, and instead I would rely on the math I learned over 30 years ago.
The case of primes congruent to 1 mod 8 is fairly straightforward since eight divides the order of the multiplicative group mod p. That means in multiplicative group mod p, there is an eighth root of unit and if you have a generator for the multiplicative group, then taking that generator to (p - 1)/8 power will give you that eighth root of unity. Let w be that root, then some simple math shows that the square of w(1 + w2) is -2. Note that w2 is the i from the earlier paragraph.
The case of primes congruent to 3 mod 8 is a bit trickier and involves extending finite fields. In this case, the multiplicative group of non-zero numbers mod p, split into two equal groups, those that are a square of a number mod p, and those that are not. And those that are a square form a subgroup of the multiplicative group mod p. Also, there is no fourth root of unity, which means that -1 is not a square mod p. So you can get from the subset of squares to non squares (and vice versa), just by multiplying by -1. If you extend the field mod p by the square root of -1, you will get a field of order p2. The multiplicative group for that is of order p2 - 1, and given that p is congruent to 3 mod 8, it is not hard to see that the order of this group is exactly divisible by 8 (if you understand the phrase “field mod p”, you should then be able to do this calculation as well). That means that in this new field, it has an eighth root of unity but not a sixteenth root of unity. Now, with a bit of mathematics of how you construct a sixteenth root of unity from an eighth root of unity, it is not difficult to show that this means that 2 cannot be a multiplicative square, which means that -2 is a square. However, a number not being a square mod p happens if and only if that number to the (p - 1)/2 power is -1. So 2 to the power (p-1)/2 is -1. Then since (p+1) is divisible by 4, some simple math shows that 2 to the power (p+1)/4 is a square root of negative 2.
In the prior two blog posts, I put the Groovy script into the body of the blog post. The Groovy has now gotten sufficiently complex that this time I decided to create a Gist and reference that instead. The Gist is at https://gist.github.com/sampwhite/e58bbb44595bfb7d056de0578a2b9e3e. And the Groovy Web Console pre-loaded with the Gist can be found at https://gwc-experiment.appspot.com/?gist=sampwhite/e58bbb44595bfb7d056de0578a2b9e3e. Also, unlike in the previous iterations, the code is written as a more formal code construct. Class and method names are longer, there is a bit more commentary, and the code is no longer treated simply as a script. And in one other change, for the case of primes congruent to one mod four, I wrote the breakdown into squares as 4 times the square of a number plus the square of the number. You can do this, because if an odd number is the sum of two squares one of the squares is a square of an even number. By doing this we can make a stronger claim of uniqueness. Each of the breakdown into squares is the unique breakdown into nx2+y2 for a given n and possible positive integers x and y. As before, in the Groovy Web Console Result tab, the case of two times a square plus a square is prefixed with M2, the case for three times a square plus a square is prefixed with M3, and the case of four times a square plus a square is prefixed with M4.
And for one last thing (at least for this blog article), I ran the code as an application on my laptop and in less than two minutes generated a prime with 1,000 digits congruent to 1 mod 24 that exhibited all three breakdowns into sums of squares. The example can be found at https://gist.github.com/sampwhite/c84cfa1fe0718d54d5f75ce3219ddd0c. I find this to be remarkable. A number with a hundred digits is already larger than all the atoms in the universe. Here is a prime number incredibly larger in order of magnitude that we claim is uniquely broken down into particular combinations of squares of integers, and we are able to compute that breakdown.