complex modular exponentiation

[Kragen]

On Tue, 8 Dec 1998, Matthew OConnor wrote:
> -- I'm not sure if your lists are working or not.

I think so.  Did you send it to one of them?  I'll forward it to
kragen-discuss.

> 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?

He'd been playing with x^n mod m for real integers, and decided to try
complex numbers.

> > 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).

What exactly do you mean by "holds"?  That for any x[1], y[1], x[2],
y[2], there exists an x[3], y[3] such that (x[3] + i y[3])(x[1] + i
y[1]) = x[2] + i y[2]?

> As for exponentation, Fermat's little theorem is handy when n is prime
> also there are certain elements called generators that are helpful too.

I don't know the proof of Fermat's little theorem even for real
integers.  Can you show me the proof for "complex integers"?

> > Suppose we take some number n and some number z[1] and define z[x+1] =
> > (z[1] z[x]) mod n.  Then z[x] = (z[1]^x) mod n (as you can see from
> > induction).  
> 
> Why was the notion of exponentiation developed this way?  It seems a
> little strange.

Probably because that's the way I coded it, and I wanted to sort of
handwave and say, "Look, this code doesn't just compute some random
function -- it actually has a connection to something meaningful."

> 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[0].  (ie mandelbrot equation).

Me too.  Should be relatively easy to do.

> 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.

Well, at some point, z[x] = z[y] for x < y, just because there are a
finite number of points.  And since z[x] is just a function of z[x-1],
z[0], and n, then for all a > x, z[a] = z[a - (y-x)].

> > 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)).

Well, obviously the sequence that starts at (0, 0) will be a loop of
period 1 that contains (0, 0).  I assume you mean no *other* sequence.
Why do you think so?

Are these things you're saying about prime n also true for Carmichael
numbers n?

> 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.

Cool.  I should look up the term "cyclic group" before I respond to
that. :)

> > few; it may not even include the original point (z = 1 + i, n=6, for
> > example); 
> 
> When n isn't prime things get ugly (or more intresting)...

I should try to characterize these things.

> > 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.

Why?

> These are really intresting.  What is the reason for the "number of
> colors" option to the plot-exp-complex script?

To make it look cool.  You can see different patterns when you change
the "number of colors".

The patterns probably indicate something deep and important, but I'm
not sure what.

-- 
<kragen@pobox.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")