A set of integers modulo M can be naturally laid out along a circle: (x, y) = (Cos(τ i / M), Sin(τ i / M)). The relationships between the numbers can then be represented as chords. This simple technique is remarkably good at revealing nontrivial patterns. In this post, I will present some visualizations of various modular arithmetics concepts. A huge thanks goes to Christopher Walsh for introducing me to various applications of the circle mapping. For more examples, you can visit Simon Plouffe's home page which has many images of modulo distributions of various integer sequences.
Modular multiplicative inverses
A number b is called a modular multiplicative inverse of a modulo M if (a b) mod M = 1. Only numbers coprime to M have an inverse. They are counted by Euler totient function φ(M) (A000010). The following image was created by connecting each number with its inverse for M = 1 .. 264. Inverses of themselves are marked with radial strokes (A060594 gives their total number). The number of rows, 12, was chosen intentionally. Numbers with many factors (such as in rows 6 and 12) have relatively few lines, and prime numbers > 3 having the most lines can only be found in rows 1, 5, 7, 11.
g is a primitive root modulo M if every number from 1 to M coprime with M can be expressed as an integer power of g mod M. Primitive roots exist for M = 1, 2, 4, pk and 2pk, where p is an odd prime (A033948). The number of primitive roots, if any exist, is φ(φ(M)) (A010554). Once a single g is known, the rest of them can be found by raising g to powers less than φ(M) and coprime with it.
Following images depict the sequences gk for various M by connecting their consecutive values with chords. Only prime moduli are shown because they are the most interesting in the sense of having all the numbers 1 .. M - 1 representable as gk. Each row starts with the smallest primitive root and continues with its powers that are also primitive roots. Only the first half of all g is shown because the rest of them are multiplicative inverses of the first half and generate the same sequences but in reverse order. Cases M = 127 and M = 257 are shown separately.
Random number generators
Primitive roots are employed in Lehmer random number generators whose output consists of consecutive powers of g: Xi + 1 = g Xi mod M. Circle mapping can be used to spot nonrandomness in such generators. To improve the discriminating power, the visualization has been modified so that the chord color is dependent on the sequence term succeeding the ones connected. The images depict the infamous RANDU RNG (M = 231, g = 216 + 3, A096555) and the one used in ZX81 Sinclair (M = 216 + 1, g = 75 ). M used in RANDU has no primitive roots, so the sequence period is only 229. Instead of a uniformly gray disk, RANDU produces a clearly visible pattern. ZX81 RNG looks more uniform, but a wave-like pattern is still visible.
A polynomial f(x) is a permutation polynomial if it permutes the integers 0 .. M - 1. A characterization of permutation polynomials modulo prime powers can be found in . For example, 2x2 + x is a permutation polynomial for M being a power of 2. I won't try to cover permutation polynomials systematically in this post and will just show a few nice-looking ones. As before, the images are obtained by connecting consecutive values of f(x). Note a curious feature: images for the larger moduli seem to contain smaller versions of the images for the smaller moduli.
- Steven Vickers. Sinclair ZX81 BASIC Programming.
- Rajesh P Singh, Soumen Maity. Permutation Polynomials modulo pn.
Follow me on Twitter to receive notifications about new blog posts. This post was made possible thanks to the patron support. If you appreciate the effort put into creating this page and would like to see more posts like this, you can support me on Patreon. Top patrons of the month:
- Brian Bucklew
- Anton Shepelev
- Adam Hill
- Tomoyuki Naito
- John Metcalf