Applications of Number Theory
Currently the most important applications of number theory in modern technology are in the fields of cryptography and coding theory.
Applications in Coding Theory
Finite fields are essential for algebraic coding. From a mathematical point of view there is only one finite field for any size q which
is very often denoted by GF(q). Here GF stands for Galois field and q gives the number of elements which is either a prime or a prime power.
For prime fields GF(p) the field is most often represented by the set {0,1,2,..p-1} and addition, subtraction, multiplication and division
is done modulo p.
However, from a technical point of view, different representations of finite fields can give significant advantages for practical applications.
For coded modulation the representation of finite fields as Gaussian integers modulo a Gaussian prime is essential.
See my paper K.Huber, "Codes over Gaussian Integers", IEEE Trans. on Inf. Theory, Vol.40, No.1, January 1994, pp.207-216
(for an overview in German see also here).
From this application the problem arose to compute the sum of the squared euclidean distances from zero to all elements of the finite field
represented als Gaussian integers modulo a Gaussian prime (the most important case being p a prime of the form 1 mod 4,
which according to a famous theorem of Fermat can be represented as p=a2 + b2 and the Gaussian prime is then a + i b).
Representations of the fields GF(p) for all primes p=1 mod 4 for p smaller than 500 are
given here (size 1,2 MB) from which you can find the representation e.g. for the
field GF(29). For instance 26 mod 5+2i is seen to give 2+2i and the squared Euclidean distance from zero to 2+2i - the Norm of 2+2i -
is given by N(2+2i)=(2+2i)(2-2i)=8. To compute the sum of the squared distances for this field we find that it is
given by 4 * ( N(1 mod 5+2i) + N(2 mod 5+2i) + N(13 mod 5+2i) + N(14 mod 5+2i) + N(25 mod 5+2i) + N(26 mod 5+2i) + N(8 mod 5+2i))=
4*(1+4+2+5+5+8+10)=4*35=140. Clearly this sum can easily be computed numerically.
If codes over Gaussian integers are used for signal transmission it is important to know this sum over all Gaussian integers of the field,
from which the average signal energy can be obtained if all signal points are used with equal probability.
It turned out that this sum, lets call it S, is in fact given by a very simple formula:
Theorem: S=(p2-1)/6
The proof of this theorem is published in the appendix of my paper
K.Huber, "Codes over Tori", IEEE Trans. on Inf. Theory, Vol.43, No.2, March 1997, pp.740-744.
For convenience this proof is also given here.
When I first computed this sum, I thought that this result is certainly known. But I could not find it in the literature. Therefore
I did send it as problem to the American Mathematicl Monthly. The problem and its solution appeared
in K.Huber, Problem 10497, American Mathematical Monthly, January 1996, p.75. and
Solution: American Mathematical Monthly, February 1998, p.185. As the AMM is a very wide-spread mathematical journal it is
quite likely that this theorem was not known before.
PS: My proof is not restricted to primes of the form p=1 mod 4.
It holds for all integers n=a2 + b2 with n=1 mod 4 and a>b ≥1 leading to S=(n2-1)/6.
PPS: The colours for the signalpoints for the representation of GF(p) as Gaussian integers give the biquadratic character of each element.
This is an extension of the concept of quadratic residue introduced by Gauss. If we compute k(p-1)/4 mod a+ib of each
element we obtain either 1,i,-1,-i. The elements are respectively blue, green, red, yellow. Biquadratic residues play a role for algebraic
coding (see e.g. reference [23] of my publications).
Applications in Public-Key-Cryptography
Classic cryptosystems are symmetric. This means that the sender and the receiver must know the key to encrypt and decrypt a message.
This results in the problem to transfer this key, which must be kept secret. These symmetric cryptosystems are still the work-horse
for
encrypted data transmission. Asymmetric cryptosystems, also called public-key-cryptosystems, are a more recent development.
Such systems use two keys, one for encryption and one for decryption. The point is, that the encryption key can be made public and everybody
knowing this key may encrypt messages. But only the legitimate receiver who is in possession of the secret key, is able to decrypt the message.
Public key cryptosystems are all based on mathematical problems which are considered as being difficult. The mathematical problems which are mainly used
today are the discrete logarithm problem and the factoring problem. At the beginning of the development of public-key cryptosystems there
was another problem, the knapsack problem which was suggested for practical applications. As the first such systems were shown to be unsafe, knapsack
systems are currently not considered anymore.
In a way this is ironic as the base of the knapsack systems is a difficult problem, the subset sum problem. On the other hand the difficulty of the
cryptosystems which are in use today (i.e. the dicrete logarithm problem and the factoring problem), is not known at all.
Some say that these problems are so difficult that one even does not know how difficult they are. I do not share this opinion. I think, in spite of the
fact that knapsack systems in general have a bad reputation, they should still be on the research agenda.
Test your number-theoretic intuition
Before you start reading the subsequent paper on representing a number as sum of four squares you might want to test your intuition
on number theory here.
An algorithm to represent a number as sum of four squares
This paper dates from the first half of the nineties. It has not been published.
It might be of interest for certain applications.
A public key cryptosystem based on Gaussian Integers
A knapsack system based on Gaussian integers is given here.
This paper was presented at a conference in St.Petersburg, Russia in 1995 (see the exact reference here).