complex modular exponentiation (fwd)
Tue, 8 Dec 1998 10:23:05 -0500 (EST)
<email@example.com> Kragen Sitaker <http://www.pobox.com/~kragen/>
This radically anti-cynical approach to life is not just a shared
disposition but also an act of conscious dissent. -- Alan Bershaw, on the
attitude of Jewel fans ("everyday angels")
---------- Forwarded message ----------
Date: Tue, 8 Dec 1998 01:44:00 -0500 (EST)
From: Matthew OConnor <firstname.lastname@example.org>
Subject: Re: complex modular exponentiation
-- I'm not sure if your lists are working or not. If they are then you
-- can pass this on to your list if you feel it is "worthy" or not if you
-- don't. These are just some observations I thought I'd make on this
-- thought experiment.
On Fri, 4 Dec 1998, Kragen wrote:
> Kevin Player turned me on to this; I think the idea is original with him.
Which part of the idea is original with him?
> Define "z mod n", where z is a complex number expressed as x + iy,
> where x and y are both integers, and where n is also an integer, to mean
> (x mod n) + i (y mod n), where "mod" is defined in its usual way --
> remainder after integer division, in the interval [0, n).
Define C_n to be the set of numbers z mod n.
Analgous to Z_n, the set of integers mod n.
> Then this complex "mod" has at least some of the same properties as the
> integer "mod" we all know and love:
> ((a mod n) + (b mod n)) mod n = (a + b) mod n
> ((a mod n) (b mod n)) mod n = (a b) mod n
> (These are pretty easy to prove. Subtraction trivially works; dunno about
> division, and I'm not familiar with exponentiation in the integer realm
> (except what obviously follows from what's above, namely ((a mod n)^b)
> mod n = (a^b) mod n.))
Division holds in C_n if n is prime. (Not always true in general).
As for exponentation, Fermat's little theorem is handy when n is prime
also there are certain elements called generators that are helpful too.
> Suppose we take some number n and some number z and define z[x+1] =
> (z z[x]) mod n. Then z[x] = (z^x) mod n (as you can see from
Why was the notion of exponentiation developed this way? It seems a
Even though the set of elemnts in C_n isn't continous I'd be intrested in
seeing what happens for z[x] = z[x-1]^2 + z. (ie mandelbrot equation).
I don't know how feasible this is since z[x] can't really blow up to
infinity, but there may be some kind of correlation one could construct.
At the very least I think it would loop.
> Eventually, you will always get into a loop, because there are only a
> finite number of points (x, y) where x < n, y < n, and each one has a
> unique successor. Your loop may include all the points in that space
> except for (0, 0) (z = 2 + i, n = 7, for example); it may visit only a
if n is prime then no loop will contain (0,0) (or degenerate into (0,0)).
In particular the numbers "z" that DO loop through all the points in C_n
are called "generators" and the set of elements in C_n (except (0,0)) form
a cyclic group under multiplication mod n. All of this is, of course,
only when n is prime.
> few; it may not even include the original point (z = 1 + i, n=6, for
When n isn't prime things get ugly (or more intresting)...
> it may just be (0, 0) (which is always its own successor)
> (try z = 2 + 2i, n =8, for example).
This is very true, and semi-intresting because of the reason it is true...
If n isn't prime then C_n isn't an integral domain and then the examples
of the above result are aplenty. As a matter of fact if n isn't prime
then there has to be at least 1 element in C_n that degenerates to zero.
> If you plot the points you iterate through this way, you can get some
> interesting patterns.
> The scripts I have included here will do the modular exponentiation for
> you and plot the results in ASCII. (It would be nice to plot them in
> nicer ways, but hey, I was in a hurry. And my PostScript printer wants
> ink, while my ASCII printer is working fine.)
> mod-exp-complex x y n outputs the results of exponentiating (x + iy)
> mod n. plot-exp-complex n takes the output from mod-exp-complex as input
> and plots it in ASCII, using different characters to represent different
> iterations, with 'n' being the number of different characters to use.
> Space always indicates unvisited points.
The number points actually visisted (ie the points w/o a space) is called
the order of z (for z in C_n) if the loop passes through (1, 0).
If the loop doesn't passes through z then z is said to have infinite
Normally the order of a number is defined as the smallest positive number
k such that a^k = 1 for a in "something" (usually a group).
For example, let z = 2 + i (mod 7). Your program produces: (w/ num of
colors == 100).
There are 48 non "space" characters displayed, so the order of 2 + i in
C_7 is 48. And you will notice that 2 + i is a generator of the nonzero
elements of C_7.
Another example: let z = 2 + 5i (mod 7). Your program produces:
(w/ num of colors == 100).
Notice that it passes through (1, 0) and there are 8 characters. So the
order of 2 + 5i (mod 7) is 8.
> mod-exp-complex detects loops in kind of a stupid way. I'd like to find
> a better one.
> Try these commands:
> ./mod-exp-complex 2 1 7 | ./plot-exp-complex 3
> ./mod-exp-complex 2 1 7 | ./plot-exp-complex 4 (a very different pattern)
> ./mod-exp-complex 2 4 7 | ./plot-exp-complex 3
> ./mod-exp-complex 2 3 17 | ./plot-exp-complex 4
> ./mod-exp-complex 1 7 17 | ./plot-exp-complex 4
> ./mod-exp-complex 2 7 43 | ./plot-exp-complex 3
> ./mod-exp-complex 30 21 43 | ./plot-exp-complex 6
These are really intresting. What is the reason for the "number of
colors" option to the plot-exp-complex script?
This is the most intresting thing I could come up with that wasn't along
the same lines as the ones you pointed out:
./mod-exp-complex 1 30 50 | ./plot-exp-complex 1 (notice the spacing).
(hmm, police code for homicide gives a litle X :)
./mod-exp-complex 1 8 7 | ./plot-exp-complex 1
(what is up w/ the Xs?)
./mod-exp-complex 100 100 101 | ./plot-exp-complex 1
./mod-exp-complex 10 10 11 | ./plot-exp-complex 1
(let me read your fortune in the complex numbers):
./mod-exp-complex 12 8 98 | ./plot-exp-complex 1
./mod-exp-complex 2 7 11 | ./plot-exp-complex 1
- Matthew O'Connor