This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
Assumed Foreknowledge
I assume :
- Knowledge of the complex numbers
Terminology
- ℤ, ℕ, [) (], (), [], {}, ∈, sets
Modular Arithmetic1
Often we want to just consider the number between 0 and n for convenience sake and as they very nice to work with. However we have a problem - say we want to only consider the number 0 up to 10 but what if we want to do 9 + 4 this is 13 which is outside our bound. We solve this with modular arithmetic
Now we say that 9 + 4 = 13 ≡ 3 (mod 10) or 4*7 = 8 (mod 10); and it's like this for all numbers so 1344 ≡ 4 (mod 10). To work out these equivalences we can simply say that a + k*n ≡ a (mod n).
We call the numbers 0 up to p with modular arithmetic and multiplication to be ℤp or 𝔽p; so whenever you see either of these 2 used just think of the numbers 0 to p with + and * as described above.
Multiplicative Inverses2
A multiplicative inverse is the number that you have to multiply to get to 1. So inv(a) = 1/a; however in the world of ℤp we only have the numbers [0..p) and so for a != 1 we don't have 1/a. So we need to find a way of expressing 1/a in ℤp and luckily there is a way of doing so the Extended Euclidean algorithm3. It turns out that a modular inverse will exist if a and p are what is called coprime - this means that they have GCD 1; a quick way of ensuring that all elements (except 0) have a multiplicative inverse is therefore to pick p to be prime. An implementation of this can be in inv' in GaussianMod.hs.
Gaussian Integers (mod p)
Now we've covered standard modular arithmetic we conclude that's far too simple... time to get more complex - quite literally.
We write ℤp[i] to mean the Gaussian Integers mod p which are just the number x + iy where x and y are both from ℤp. Multiplication and addition work the standard way for complex numbers except that if either the real or the imaginary component of the number goes over p then it is reduced in the same way as in stand modular arithmetic.
Multiplicative inverses also exist and the inv(x + iy) = (x - iy) * inv(x2 + y2) and so exist when x2 + y2 is coprime to p. Therefore it is easy to see that if p is prime then all Gaussian Integers (mod p) have an inverse.
These are described in GaussianMod.hs