complex modular exponentiation

[Matthew OConnor]

On Tue, 8 Dec 1998, Kragen wrote:

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

No that message was started (however not sent) before you had announced
the official change.

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

Yes.  It gets a little fuzzy on what you mean by division.  If your
talking decimal points and fractions, then you might be out of luck.

However, 17/28 is the same as 28^-1 * 17.  So if you think of things in
terms of their multiplicative inverse, then things can be better
understood...

Now, by def. of a field the equation au = 1 (a not zero) has a solution
for u in the field.  So if you  want to pick any arbitrary elements, a, 
c in a field such that there exist an element "b" and ab = c then you
can do this:

    since we are in a field, a^-1 exists.  More importantly a*a^-1 = 1.
    multiply both sides by c.  so now you have a*a^-1c = c.
    let b = a^-1*c.  Since we are in a field, b is in the field.
    therefore b exists.

No need to break out into the def. of what the elements of C_n are.  Once
you have determined that C_n is a field you get a bunch of stuff for free.
(And C_n is a field iff n is prime).

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

I didn't say it was true for the complex integers.  It is pretty easy
to prove that it isn't.  For example, take (2 + 2i)^3 (mod 3).  It
is equal to (2 + i) (mod 3), which is not (2 + 2i).  So it doesn't
appear to be true (in general).

Also, You deleted part of the message so I went an retrieved it, this is
from your orignal post on this subject: (or I deleted part of the message,
one of us did).

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

You clearly say that you are not familiar with exponentiation in the
integer realm.  The suggestions I gave were for exponentiation in the
integer realm.  If you'd like me to sketch a proof of Fermat's little
theorem (for integers) i could do so.

(I apologize if I don't preserve the context of the material I am replying
 to.  It is my inferior communication skills I need to work on.)

> > 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 would think so too.
 
> > 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)].

I don't understand how you arrived at that conclusion.

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

Yes i meant no *other* sequence.

The reason is that if n is prime then C_n is a field.

Defintion:  Let S be a set with two binary operations +, *, definied on
            it.

            S is field if and only if the following conditions hold:

            1) S is closed under +.

            2) + is associative in S.

            3) + is commutative in S.

            4) An element, call it 0, exists in S such that 
               a + 0 = 0 + a = a.  (ie additive identity).

            5) The additive inverse for any a in S exists.

            6) S is closed under *

            7) * is associative in S.

            8) * is commutative in S.

            9) An element, call it 1, exists in S such that
               a*1 = 1*a = a.  (ie multiplicative identity).

           10) The multiplicative inverse exists for any a not
               equal to zero.

           11) The distributive laws hold true.

Quick Def:  Let S be a set where + and * are binary operations defined on
            it.  Then S is a field if and only if:

              1) (S, +) is an abelian group.

              2) (S - {0}, *) is an abelian group. Where S - {0} denotes
                 the set S with the additive identity, 0, removed.

              3) The distributive laws hold true.


Quicker Def:  Let S be a set. S is a field if the opeartions +, *, - and /
              are defined and closed on S and +, * are commutative.


Now let me prove something...

Let F be a field with the elements a, b such that a =/= 0 and b =/= 0.
Then a*b =/= 0.

Proof:  Assume a*b = 0.  This means that F - {0} isn't closed under *.
        Therefore (F - {0}, *) isn't even a group (let alone abelian).
        So we have a contradiction.  Therefore a*b =/= 0 for all a, b
        in F such that a =/= 0 and b =/= 0.

Let me prove that C_n is a field if n is prime.

Let C_n = {x + iy: x, y are in Z_n} where n is prime.
Then C_n is a field.

Proof: (I'm going to use that fact that Z_n is a field, you may
        want to veryify this yourself).

       Let, z, z' be in C_n such that z = x + iy and z' = a + ib.

       Therefore z + z' = (x + a) + i(y + b).

       Since Z_n is a field, + commutes.

       So, z + z' = (x + a) + i(y + b) = (a + x) + i(b + y) = z' + z.

       Since Z_n is a field, + is closed under Z_n.

       So, (a + x) is in Z_n and (b + y) is in Z_n.

       Therefore z + z' = z' + z is in C_n.

       Since Z_n is a field there exists additive inverses of
       (x + a) and (y + b).  Denote those inverses as -(x + a)
       and -(y + b).  Define -(z + z') as -(x + a) + i*-(y + b).

       But clearly (z + z') + -(z + z') = 0.  So the additive inverse
       exists.

       The existance of the additive idenity (0 + i0) is obvious.  
       Associativty is left up to you.

       Therefore (C_n, +) is an abelian group.

       Do the same with (C_n - {0}, *) to show it is an abelian group.
       All of them are just as easy, except maybe proving the inverse
       always exists.
       (Hint: when trying to prove the inverse exists for x + iy, show
              that (x^2 + y^2)^-1*(x - iy) exists and is in C_n and
              then watch what happens when you multiply x + iy to it.)

       Anyway, a little bit of handwaving here, but I'm lazy and don't
       wanna type out stuff you can find in a billion web-pages and books.

       Anyway, after showing that (C_n - {0}, *) is an abelian group,
       show that the distrubitive laws are true.  Then you will be
       convinced that C_n is a field if n is prime.

       (BTW the hypothesis that n is prime is used throughout, since it
        is required that Z_n be a field for C_n to be a field).

Hmm, *sigh*.  Anyway, back to the original question:

   If n is prime then no sequence will contain (0,0) other than the
   sequence starting with (0,0).

   Why?  Since the sequences are generated by exponentation, which
   is repetitve multiplication, it is clear that if a sequence
   DID evalute to zero (such that the sequence didn't start with zero)
   then (C_n - {0}, *) wouldn't be closed under multiplication.

   Also, since (C_n - {0}, *) IS an abelian group, no two nonzero
   elements of C_n can equal zero (since zero isn't in the group).

   That is why I think that is true.

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

No.

Since C_n clearly relys on the properties of Z_n lets just look at Z_n.

If n isn't prime then Z_n isn't a field.  In particular let n be a
Carmichael number (it doesn't matter what n is though, as long as it
isn't prime).

Since n isn't prime, let n = p_1 * p_2 * p_3 * ... * p_n  (the prime
decomposition of n).

Now let A = p_1 and let B = p_2 * p_3 * ... * p_n.

Well we know that all integers can be represented in Z_n, so A and B are
both in Z_n.

And A*B = n = 0 (mod n).

Therefore if n isn't prime then there must exist two elements, A, B, in
Z_n (both non-zero) such that A*B = 0. A and B need not be distinct.

Well, since A*B = 0, (Z_n - {0}, *) isn't a group.  Therefore Z_n isn't
a field if n isn't prime.

Therefore C_n isn't a field.  (Look at the obvious counterexample, A + i0
and B + i0.  They are both non-zero, multiply them and you get 0 + i0. So
C_n can't be a field).

Carmichael numbers don't fool us in this case.

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

Definition:  Let S be a set with a binary operation @.
             (S, @) is said to be a group (or simply S is said to be a group 
             under @) if and only if the following conditions are true:

             1) S is closed under @

             2) @ is associative in S.

             3) There exist a unique element, e, in S such that for all 
                a in S, a@e = a = e@a.

             4) For all a in S there exists an inverse, denoted a^-1, such
                that a@a^-1 = e = a^-1@a.

Definition:  If (S, @) is a group and @ is commutitive then S is said
             to be an abelian group.

Definition:  Let a be an element of the group (S, @) then the order of a
             is the smallest positive integer k such that a^k = e.  If 
             no such k exists than a is said to have infinite order.
             (note a^k denotes a@a@a@a@ -- k times).

Definition: Let (S, @) be a finite group with n elements (ie a group w/
            finitely many elements).  Then if there exists an element a in
            (S, @) such that a has order n then (S, @) is said to be 
            a finitely cyclic group generated by a.

Definition: If there exists any element a in (S, @) such that successive
            powers of a will generate all elements of (S, @) then (S, @)
            is a cyclic group generated by a.

Example:  Z_n is a field if n is prime.  And by definition (Z_n, +) is
          a group.  And (Z_n, +) is a cyclic group generated by 1.

          1 = 1
          1 + 1 = 2
          ...so on...
          1 + 1 + 1 ...n times... = n = 0


If you don't believe me then here is a website:

http://www.math.csusb.edu/notes/advanced/algebra/gp/node4.html

( If its on TV it has to be true ;) )


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

That would prove intresting.

An intresting extension of Fermat's Little Theorem is Euler's Theorem:

   if a and m are relatively prime then a^phi(m) = 1 (mod m).

where phi(m) is Euler's Phi Function.  phi(m) is defined as follows:

      phi(1) = 1.
      phi(m) = the number positive integers a <= m such that a and m are
               relatively prime.

I don't know how this extends to C_n of course (or if it even does).

Also, the set of all elements in Z_n that have an inverse form a group
under *.  And the number of elements in that group is phi(n).  :)

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

I'm sorry I don't know if that is true.  I haven't been able to find a
counter example.  I'll give the proof the good ole college try some other
time.

What /is/ true is that if n isn't prime then there must be two elements a,
b, both non-zero such that ab = 0.

Here is why there must two elements a, b, both non-zero such that ab = 0
if n isn't prime.

C_n is finite.  Every finite integral domain is a field.

Let n not be prime.  So if for all a, b non-zero in C_n if a*b =/= 0 then
C_n is an integral domain.  Since C_n is finite it is also a field.

But it can't be.  Let A, B, be in Z_n such that A*B = n.  Let a = A + i0
and let b = B + i 0.

Both a and b are non-zero, but a*b = 0.

Therefore C_n isn't an integral domain.

Therefore C_n isn't a field if n isn't prime.
 
> > 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".

Hmm, you mean using differen't characters is supposed to somehow induce
visual effects that make the pattern look different?  I mean the same
points are plotted, just w/ different symbols.

Maybe I'm just not seeing it :/


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

It would be nice if I could determine the order in which the points
were plotted.  (Perhaps you can do that w/ the colors, if I knew which
symbol logicaly followed the next.  I'm sure there is order to it, but
I haven't looked at your code that closely).


Anyway, if you respond then go easy on me, I'm sure this email has
lots of typos. :/  I've checked it over a few times, but I'm sure
they will pop.

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