Programming Praxis

We continue today with our study of Gaussian integers.

The greatest common divisor of two Gaussian integers is computed by Euclid’s algorithm: repeatedly replace dividend and divisor with divisor and remainder until the divisor is zero, at which point the dividend is the greatest common divisor. One Gaussian integer divides another if the remainder is zero, and two Gaussian integers are co-prime if their greatest common divisor is one of the four units.

If a Gaussian integer is not a unit, it is either prime or composite. A Gaussian integer a + b i is prime if either a or b is zero and the other is a prime congruent to 3 (modulo 4), or if both a and b are non-zero and the norm is prime.

If a Gaussian integer is composite, it can be factored by the following algorithm described by Jim Lewis: Factor the norm. For each norm factor of 2, add a factor 1 + i to the list of output factors. For each two norm factors p that is congruent to 3 (modulo 4), add a factor p + 0 i to the list of output factors. Otherwise, norm factor p is congruent to 1 (modulo 4): find k such that k ² = −1 (mod p), then add gcd(p, k + i) to the list of output factors. After considering all the norm factors, the original Gaussian integer divided by all the output factors will be a unit; if it is 1, then you are finished, otherwise add to the list of output factors the unit that remains after the division. To find k, choose some integer n between 2 and p −1, inclusive; if n ^(p −1)/2 = −1, which will be true about half the time, then k = n ^(p −1)/4.

Your task is to write functions for greatest common divisor, identifying primes, and factoring composites for Gaussian integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2