complex modular exponentiation (fwd)

[Kragen]

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

---------- Forwarded message ----------
Date: Tue, 8 Dec 1998 01:44:00 -0500 (EST)
From: Matthew OConnor <matthew@anti-earth.org>
To: kragen@pobox.com
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[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.

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

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
> example); 

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

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

 QAI1)9
-7">D@C
M4'0B3.
%86/;<J
=2$#GNP
5FK*H?L
E+(,&:O

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

(more Xs)
./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

(sorta intresting):
./mod-exp-complex 2 7 11 | ./plot-exp-complex 1


--
- Matthew O'Connor
- (matthew@anti-earth.org)