Algebra

Dear Eric and Cypherpunks,

So, how is division defined in Fp?

Tom

Tom Jones says:
> Dear Eric and Cypherpunks,
> 
> So, how is division defined in Fp?

Being an old fogey, I still refer to the field formed by the integers
modulo a prime by a gothic capital Z sub p.

In Z_p, you define division as the inverse of multiplcation, just as
in real life. One easy way to do this is to note that every number in
a field like this has a multiplicative inverse. Multiplying by the
multiplicative inverse of a number is the same as dividing by the
number. 

For the hell of it, make yourself a multiplication table for Z_5. Its
a quick exercise. Note that every number in Z_5 other than zero
possesses a multiplicative inverse -- that is, a number that it can be
multiplied against to yield 1. Step back and then observe,
experimentally, that for any three positive numbers in Z_5 A, B and C
such that A*B=C, that C*(B^-1)=A. One can, of course, prove that this
is the case rigorously...

Perry

This really reminds me that I'd like to start gathering short discourses on
various subjects to make a WWW educational library/courses.

It has everything you'd need and there are lots of things even I'd 
like to write about.  I'm really thinking of a contrib learning
library.

Does anyone know if someone has started this yet?

If not, I'll organize a structure, contrib guidelines, WWW
server that allows contrib, voting (on best ways to learn
something), etc. and try to think up a domain that isn't
taken.  I'll by necessity have to set it up and let
it run since I'm already overloaded with work and family.

My feeling is that there is lots of stuff out there already
and that it needs to be organized.  Not overly so as
traditional schooling is, but in a way that allows
organic learning and search for what you may need to learn.

I'll start it on my web server and see about mirroring on
my friends systems (who have faster connections).

And now, the reason I decided to dump this here, I'd like
to ask permission to include discourses like the one just
given.

<wishing I would have brought this up somewhere else...>

comments please!

selfed.com or selfedu.com or maybe self-ed.com?????


> Tom Jones says:
> > Dear Eric and Cypherpunks,
> > 
> > So, how is division defined in Fp?
> 
> Being an old fogey, I still refer to the field formed by the integers
> modulo a prime by a gothic capital Z sub p.
> 
> In Z_p, you define division as the inverse of multiplcation, just as
> in real life. One easy way to do this is to note that every number in
> a field like this has a multiplicative inverse. Multiplying by the
> multiplicative inverse of a number is the same as dividing by the
> number. 
> 
> For the hell of it, make yourself a multiplication table for Z_5. Its
> a quick exercise. Note that every number in Z_5 other than zero
> possesses a multiplicative inverse -- that is, a number that it can be
> multiplied against to yield 1. Step back and then observe,
> experimentally, that for any three positive numbers in Z_5 A, B and C
> such that A*B=C, that C*(B^-1)=A. One can, of course, prove that this
> is the case rigorously...
> 
> Perry
> 


-- 
Stephen D. Williams    25Feb1965 VW,OH      sdw@lig.net http://www.lig.net/~sdw
Senior Consultant      510.503.9227 CA Page 513.496.5223 OH Page BA Aug94-Dec95
OO R&D AI:NN/ES crypto     By Buggy: 2464 Rosina Dr., Miamisburg, OH 45342-6430
Firewalls/WWW servers ICBM: 39 38 34N 84 17 12W home, 37 58 41N 122 01 48W work
Pres.: Concinnous Consulting,Inc.;SDW Systems;Local Internet Gateway Co.29Nov94

So, how is division defined in Fp?

There's a wonderful little theorem of broad technical use which says
(a, b, m, n are all integers, or more generally, elements of a
Euclidean domain)

   \forall a, b \in Z \exists m, n \in Z : a m + b n = gcd( a, b )

What this says is the greatest common divisor of 'a' and 'b' is a
linear combination of them.  The algorithm to find the gcd is the
Euclidean algorithm; the algorithm to find the constants 'm' and 'n'
is the extended Euclidean algorithm.

To define multiplicative inverses in F_p, substitute 'p' for 'b' in
the above equation.  The gcd of 'p' and any non-zero element of F_p is
1.  (And we already knew you can't divide by zero.)  Now, reduce the
equation modulo p; this turns elements of Z into elements of F_p and
the second term of the addition goes to zero.  What you get is

   \forall a \in F_p \exists m \in F_p : a m = 1 (mod p)

That's the existence of multiplicative inverses in F_p.  Use the
extended Euclidean algorithm to calculate them.

Eric