GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller), but GF2 and GF3 are too small to really see where the beauty of all this math lies.
------
GF5 (which is simply "arithmetic modulo 5") has all the properties of Real-numbers "we care about", and none of the hassles of decimals or partial numbers.
GF5 is simply arithmetic modulo 5. Its really easy to do. 4 + 2 == 1. (Aka: 4 + 2 mod 5 == 6 mod 5 == 1). Addition and multiplication are easily proven to be the same.
The fun starts when you start doing roots, exponents and logarithms (!!!). Take the definition of addition / multiplication above (aka: addition / multiplication modulo 5) and redefine square-root, exponents, and logarithms to be consistent with it.
That is to say: 2 * 3 == 1. Which means that 3 == (1/2) (yes, "one half" is now 3 in GF5). Which means 3 is 2^(-1).
* 2^2 == 4.
* 2^2 * (2^-1) == 4 * 3 == 12 mod 5 == 2.
Which means 2^2 * 2^-1 == 2^(2-1) and look, exponents work as expected. Feel free to play around with all the numbers: you'll find that exponents work once you match this new "definition" of exponents.
---------
Because exponents work, logarithms work. Because everything works, we can have complicated ellipical curves defined over the numbers {0, 1, 2, 3, 4} (aka: the numbers mod 5) and have everything work out mathematically.
--------
The hard part is proving that all of this works in GF(5^2) aka GF25. It turns out that you can't just "mod 25" the stuff, you need to do an extension field (and basically make a complex number out of things).
Once you understand GF25 extension fields and its relationship with GF5, then it becomes easy to generalize that to GF2 and its extension fields GF(2^8) (aka: binary numbers of 8 bits) or GF(2^32) (aka: 32-bit numbers).
Turns out for extension fields (like GF(5^2) aka GF25) you need to redefine multiplication and addition as well and then rebuild all the math from the ground up off of this new definition of addition and new definition of multiplication. And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers.
Bonus points: GF(2^32)'s new addition operator is just an xor. Only multiplication is difficult.
But once you do that, it all __JUST WORKS__ and is amazing.
----------
Galois Fields are a way to "cheat" a definition of logarithm, exponents, square roots, multiplication, division, and addition (by redefining these operations).
It turns out that these operations continue to work "as expected" in the Galois Field... as long as you're cool with the new definitions of them.
------
EDIT: I'm slightly wrong. Seems like Curve25519 is a prime field and not an extension field. So this is more similar to GF5 than it is to GF(2^32). Still, other elliptical curves are in GF(2^32) or other extension fields, so the study of extension fields is useful for other curves.
Curve25519 can be understood with just the GF(5) description I gave earlier in this post. Prime fields are really simple: just mod(the prime number) and you're set. There's some weird properties that can accelerate speed (Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster).
> Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster
that's not just a weird property you can use for performance, standard grade-school division doesn't work in fields because the results are outside of the field.
So division is redefined using the modular inverse-- which has a natural definition the modular inverse a of element x is the value that makes the product ax equal the identity.
The "cool optimization" though is that since modular inverses are kinda expensive, you can rewrite your arithmetic to keep things in fractional form as long as possible and get a big speed-up.
[This also applies to ordinary numbers with division: E.g. use newton's method to compute square roots but don't do any division, keep everything as fractions -- with that trick you can compute pretty accurate square roots in your head! ... seems people don't get taught this kind of thing any more because of access to calculator :) ]
> And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers.
This makes it sound like you're saying that regular computer arithmetic is GF(2^32). :)
In my experience GF(2^32) arithmetic is fairly uncommon! Work in GF(2^8) is extremely common, e.g. it's used all over in error correcting codes. The field size is common because it's perfectly reasonable to implement multiplication using a log and inverse log table.
For 2^32 you really want a CLMUL instruction if you want high performance. Though once you have one you can easily go to 64-bits if it's useful for your application.
You won't find a lot of binary extension field (GF(2^n)) stuff in crypto these days except sometimes hidden deep inside a block cipher (like the AES sbox) because the extensions create a lot of additional and surprising algebraic structure. E.g. in these fields (x + y)^2 == (x^2 + y^2)! ( https://en.wikipedia.org/wiki/Freshman%27s_dream ) Unless you're doing something where the structure is useful, it's better to not have it.
Error correcting codes, CRCs, hashes, and related stuff-- however, has lots of it.
Fair. I guess I was implicitly staying away from extension fields because people's attention span will start drifing away the minute I start to attempt to explain how to perform modulo polynomial arithmetic over irreducible polynomials.
Prime fields (GF2, GF3, GF5...) are just easier to explain than extension fields (GF (2^2), GF(3^2), GF(5^2)... GF(2^8)...)
GF5 is the 3rd smallest finite field (GF2 and GF3 are smaller), but GF2 and GF3 are too small to really see where the beauty of all this math lies.
------
GF5 (which is simply "arithmetic modulo 5") has all the properties of Real-numbers "we care about", and none of the hassles of decimals or partial numbers.
GF5 is simply arithmetic modulo 5. Its really easy to do. 4 + 2 == 1. (Aka: 4 + 2 mod 5 == 6 mod 5 == 1). Addition and multiplication are easily proven to be the same.
The fun starts when you start doing roots, exponents and logarithms (!!!). Take the definition of addition / multiplication above (aka: addition / multiplication modulo 5) and redefine square-root, exponents, and logarithms to be consistent with it.
That is to say: 2 * 3 == 1. Which means that 3 == (1/2) (yes, "one half" is now 3 in GF5). Which means 3 is 2^(-1).
* 2^2 == 4.
* 2^2 * (2^-1) == 4 * 3 == 12 mod 5 == 2.
Which means 2^2 * 2^-1 == 2^(2-1) and look, exponents work as expected. Feel free to play around with all the numbers: you'll find that exponents work once you match this new "definition" of exponents.
---------
Because exponents work, logarithms work. Because everything works, we can have complicated ellipical curves defined over the numbers {0, 1, 2, 3, 4} (aka: the numbers mod 5) and have everything work out mathematically.
--------
The hard part is proving that all of this works in GF(5^2) aka GF25. It turns out that you can't just "mod 25" the stuff, you need to do an extension field (and basically make a complex number out of things).
Once you understand GF25 extension fields and its relationship with GF5, then it becomes easy to generalize that to GF2 and its extension fields GF(2^8) (aka: binary numbers of 8 bits) or GF(2^32) (aka: 32-bit numbers).
Turns out for extension fields (like GF(5^2) aka GF25) you need to redefine multiplication and addition as well and then rebuild all the math from the ground up off of this new definition of addition and new definition of multiplication. And again, this is most important for GF(2^32), aka the 32-bit number field that's common on today's computers.
Bonus points: GF(2^32)'s new addition operator is just an xor. Only multiplication is difficult.
But once you do that, it all __JUST WORKS__ and is amazing.
----------
Galois Fields are a way to "cheat" a definition of logarithm, exponents, square roots, multiplication, division, and addition (by redefining these operations).
It turns out that these operations continue to work "as expected" in the Galois Field... as long as you're cool with the new definitions of them.
------
EDIT: I'm slightly wrong. Seems like Curve25519 is a prime field and not an extension field. So this is more similar to GF5 than it is to GF(2^32). Still, other elliptical curves are in GF(2^32) or other extension fields, so the study of extension fields is useful for other curves.
Curve25519 can be understood with just the GF(5) description I gave earlier in this post. Prime fields are really simple: just mod(the prime number) and you're set. There's some weird properties that can accelerate speed (Any division by Foo is equivalent to multiplying by (1/Foo), which might be faster).