My research and investigations

Finite Fields – more Models

The story starts here.
———————————————————————–
X: My roommate suggests another model for GF(2).
G: Glad to know. Tell me about it.

X: It is based on binary arithmetic used in computers.
G: What are computers?

X: Don’t you use a computer to surf the Net?
G: I surf in the Net. You see, I’ve logged off from your real world long time ago.

X: Oh yes. Computers are the machines we use to connect to the Net.
G: Ah, those stops of the Net that take and send packets! I always get shocks there. How do computers work?

X: Computers process information by electronic bits — that’s why you get the shocks.
G: What is a bit?

X: “Bit” stands for for a “Binary digit“, a digit in the binary system.
G: I know the binary system — it is based on the number 2.

X: Similar to the base-10 system with 10 digits, the base-2 system has only two digits: 0 and 1.
G: I see, the same two symbols of GF(2)!

X: Instead of counting in bunches of 10 in decimal system, binary system counts in bunches of 2.

Counting Decimal Binary Base-3 Base-4 Base-5 Note
zero 0 0 0 0 0 all have zero
one 1 1 1 1 1 all have one
two 2 10 2 2 2 run out of symbols in Base-2, carry to next bunch
three 3 11 10 3 3 run out of symbols in Base-3, carry to next bunch
four 4 100 11 10 4 run out of symbols in Base-4, carry to next bunch
five 5 101 12 11 10 run out of symbols in Base-5, carry to next bunch
six 6 110 20 12 11
seven 7 111 21 13 12
eight 8 1000 22 20 13
nine 9 1001 100 21 14
ten 10 1010 101 22 20 finally run out of symbols in Base-10, carry to next bunch

G: In binary arithmetic, once the digit reaches 2 it is promoted as carry to the next position: 1+1=10 base 2.

X: Yes. 10 base 2 = 1×2+0 = 2.
G: How do these relate to GF(2)?

X: Assume an electronic component with only 1 bit. It won’ have room to store the number 2.
G: It will be forced to drop the carry bit, and store only the remaining bit, which is 0.

X: Thus giving 1+1=0 in base-2 carry-free arithmetic!
G: Excellent! Shall we draw up the computations in bits and have a look?

X: I can do that in my head. The 8 easy computations are:

Bit Computations
Binary add, ignore carry Binary 0 Binary 1
Binary 0 Binary 0 Binary 1
Binary 1 Binary 1 Binary 0

 

Binary multiply Binary 0 Binary 1
Binary 0 Binary 0 Binary 0
Binary 1 Binary 0 Binary 1

 

G: So what are the dictionaries to make this a model of GF(2)?
X: The dictionaries for the symbols and operations are:

Bit Model of GF(2)
Symbol Meaning
0 Binary bit 0
1 Binary bit 1

 

Operation Meaning
+ Binary add, ignore carry
× Binary multiply

 

G: The check is simple: the bit and the symbol are the same. This Bit model for GF(2) is verified correct. Well Done!
X: Now we have two models for GF(2): the Parity model and the Bit model.

G: Excuse my eavesdropping, but this is child’s play!
G: Who’s talking?

G: Johann Carl Friedrich Gauss (1777-1855), from Germany.
G: Ah, the Prince of Mathematics!

G: And you mention my name in your last letter.
G: Indeed. But master, why do you consider our models for GF(2) child’s play?

G: How do you check the parity of a number?
G: Check whether it is divisible by 2, of course.

G: And the possible remainders of division by 2 are?
G: 0 and 1. Oh-oh.

G: And you, how do you convert a number from decimal to binary?
X: By counting in bunches of 2, which is successive division by 2 whenever the amount exceeds 2.

G: For 1 bit, you’ll perform only one division by 2, and the possible results?
X: 0 and 1. Oh-oh.

G: So you see, both your models for GF(2) are nothing but my Modulo 2 model of GF(2).
X: Your model?

G: Haven’t you read my book?
X: Which book?
G: Your classic Disquisitiones Arithmeticae (Investigations on Arithmetic) of 1801, I’ve read that.

G: I wrote that at the age of 21. The first chapter is on modular arithmetic.
X: What is modular arithmetic?

G: Fix a number n, called the modulo, then perform add and multiply of numbers as usual, but any result will be divided by the modulo n, keeping only the remainder. I even invent a notation for that.
G: x+y ≡ z mod n is x+y, then keep only the remainder z of division by n. Similar expressions for other arithmetic operations.
X: Let me try an example. For modulo n=3, 2+2=4 ≡ 1 mod 3 because 4 divided by 3 gives remainder 1.

G: When the modulo n=2, there are only 2 remainders: 0 mod 2 and 1 mod 2.
G: In modul0 2 arithmetic, the 8 easy computations are:

Modulo 2 arithmetic
Add mod 2 0 mod 2 1 mod 2
0 mod 2 0 mod 2 1 mod 2
1 mod 2 1 mod 2 0 mod 2

 

Multiply mod 2 0 mod 2 1 mod 2
0 mod 2 0 mod 2 0 mod 2
1 mod 2 0 mod 2 1 mod 2

 

X: Let me check: for modulo 2, 1+1=2 ≡ 0 mod 2.
G: Hence the Modulo 2 model of GF(2) is:

Modulo 2 (Z2) Model of GF(2)
Symbol Meaning
0 0 mod 2
1 1 mod 2

 

Operation Meaning
x+y x+y mod 2
x×y x×y mod 2

 

G: Again the modulo 2 remainders and symbols match. This Modulo 2 model of GF(2) is verified correct.

G: This is such a natural model for GF(2). How come I miss that?
G: You didn’t miss that, it’s always been in your head after reading my book.
X: I think that’s why you said I can treat the symbols as numbers if I wanted to.

G: The modulo 2 system is denoted by Z2, and your Parity model is implicitly Z2.
X: What is Z?
G: Zahlen in German, or Numbers in English. The modulo is the subscript.

G: Nice meeting you, Gauss. It’s dinner time, shall we find a place to eat and discuss my last letter?
G: Glad to. Let me find a good place using my mobile app.

B: Don’t go. I have another model of GF(2)!
E: Me, too! I have yet another model of GF(2).
G: Long time no see!

G: Shall we continue after dinner?
X: Arrrh — I’m going to log back on after dinner, don’t start without me!
G: Sure.

———————————————————————–
Z: Are you staying for dinner? We have Chinese take-away tonight.

X: No. I’m heading back to Al-GBar right after dinner.
Z: What’s the hurry?

X: The prince and his friends are waiting.
Z: The real Prince? Or the artist formerly known as Prince?

X: No and no, I’ll explain later. My instant noodles are ready.
———————————————————————–
Next

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: