Dear Eric and Cypherpunks, So, how is division defined in Fp? Tom
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
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
participants (4)
-
A5713643665＠attpls.net -
eric＠remailer.net -
Perry E. Metzger -
sdw＠lig.net