3 ms·
I don't know ECC at all. But a note: Finite fields are of two types: "Prime Fields" (such as the mod 19 field discussed in this blogpost), and "Extension Field
by dragontamer 5y ago
I don't know ECC at all. But a note:
Finite fields are of two types: "Prime Fields" (such as the mod 19 field discussed in this blogpost), and "Extension Fields" (which would be prime^n, such as 19^2 or 361. Or more commonly, the 2^x fields, such as 2, 4, 8, 16, 32, 64... 256... 65536 ... because the 2^x fields correspond very closely with binary numbers).
Prime fields can be taught very quickly: maybe 30 minutes of study and examples is all you really need to really get what is going on. Be it a 2, 5, or 19 field, its really cool and simple.
The "leap" from prime fields into extension fields takes a few hours of dedicated study (which probably will be done over a week to a month if you're a busy adult like me) if you plan to do it rigorously. A lot of blogposts, textbooks, and other reference material will handwave the extension field because its... really hard math.
My best advice is "believe in the textbooks", extension fields are possible. And this is one of those situations where you can just "believe in the math" and learn the details of extension fields AFTER you understand the applications of them. "Extension Fields are like prime fields but way more tricky". They behave like a prime field in almost every way that's important, but its just way harder to understand.
--------
I do recommend making the leap at some point, and truly understanding the extension fields. Once you get there, you finally understand the underlying math behind CRC32, AES, GCM mode, and ECC. Its a very worthwhile endeavor, but you really need to dedicate yourself to quiet study for some time to really get the concepts.
- lisper 5y agoDo you have a recommendation for a good source to go to for making this leap?
- dragontamer 5y agoI banged my head against Chapter 4 for "Algebraic Codes for data Transmission" by Richard E. Blahut. And you need probably Chapter 2 before you can understand Chapter 4. (Chapter 3 is on basic error-correction concepts). The rest of the book is on CRC32, Reed Solomon, and other such error correction concepts. So if you only care about extension fields, its all about Chapter 2 and 4. I... don't know if I can "recommend" the source, but that's the chapter that finally made me understand extension fields. Its difficult math. You need to cover groups (number systems that always have "addition"), rings (number systems that always have "addition" and "multiplication"), and fields (number systems that always have "addition", "Multiplication", and "division" ) for... some very precise definition of addition, multiplication, and division. Once understanding the properties of groups, rings, and fields, the textbook will step you through prime fields. The proof for why prime fields work requires a deep understanding of group and ring properties (so you really can't skip the group / ring discussions). Then extension fields start to get discussed and the fun really begins. Do you know about polynomials? Such as x^2 - 1 == (x+1) * (x-1) ?? Ever consider that because "x-1" can't be factored, that its kinda-sorta like a prime-polynomial (like prime numbers, a prime polynomial can't be factored). Ever think about polynomial arithmetic of a polynomial over a modulo of a prime polynomial? Well... there ya go. An extension field. Obviously (/s of course, its not obvious but... that's the gist). And you know that works because that's pretty similar to arithmetic of a integer over a modulo of a prime integer (aka: the Prime Fields). Yeah, same thing right? Lol.
- senderista 5y agoIf you already have the abstract algebra background then a good Galois theory textbook like Ian Stewart’s will do.
- dragontamer 5y agoMy issue is that I was a Comp. Engineering major. Sure, I've got some mathematical training (Fourier transforms, matricies, etc. etc.) but my classes never covered Abstract Algebra. A lot of this stuff is coming out of left-field for me: just never really studied anything in this branch of mathematics.
- AlexCoventry 5y agoIt's actually not that hard. An extension field of field F comes from an irreducible polynomial f(x), irreducible meaning that in any factorization f(x)=g(x)h(x), g or h is a constant. Say f(x)=x^n+cx^{n-1}+...+d. The extension field is then denoted by F[x]/(f(x)), which means that every polynomial with coefficients in F represents an element of the extension field, and you set f(x)=0, so anywhere you see x^n, you can replace it with -(cx^{n-1}+...+d). For example, the complex numbers are represented in this notation as an extension over the reals R by R[x]/(x^2+1). In this notation, "x" is essentially acting the same as "i" in the conventional complex-number notation, because anywhere you see x^2, you can replace it with -1. Multiplication works by multiplying polynomials as usual, then reducing the x^n terms to lower-degree polynomials. Inversion of a polynomial g(x) with degree less than n works by solving the equation g(x)h(x)=j(x)f(x)+1. Since g(x) has lower degree than f(x), and f(x) is irreducible, they are coprime, so appropriate h(x) and j(x) can be found using Euclid's algorithm (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Simple_algebraic_field_extensions https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#S...). OK, maybe that last bit is a little advanced, but Euclid's algorithm is also very simple arithmetic.
- bobbylarrybobby 5y agoGreat description. I’d say it’s also important to note that in this context, the division slash means you divide the “numerator” into equivalence classes such that the difference between any two elements in a class is divisible by the “denominator”; i.e., class elements are equivalent mod the denominator. So for instance, x^2 and -1 lie in the same class because x^2-(-1) = x^2 + 1
- AlexCoventry 5y agoYeah, that's important for quotients by more general ideals, but for a principal ideal in a polynomial ring, it's easier to speak of setting the generator to zero.
- mratsim 5y agoI usually explain extension fields as similar to complex numbers with regards to reals. I've collected a lot of extension fields references while working on my own implementation: https://github.com/mratsim/constantine/tree/master/constantine/tower_field_extensions https://github.com/mratsim/constantine/tree/master/constanti... The best likely being - Arithmetic of Finite Fields Chapter 5 of Guide to Pairing-Based Cryptography Jean Luc Beuchat, Luis J. Dominguez Perez, Sylvain Duquesne, Nadia El Mrabet, Laura Fuentes-Castañeda, Francisco Rodríguez-Henríquez, 2017 https://www.researchgate.net/publication/319538235_Arithmetic_of_Finite_Fields https://www.researchgate.net/publication/319538235_Arithmeti...
- dragontamer 5y ago> I usually explain extension fields as similar to complex numbers with regards to reals. Its a good analogy and the math is indeed very close to complex vs reals. If you consider "i" to be the "polynomial variable", then a prime-integer field vs a (prime-integer)^2 extension field is pretty much identical to real vs complex. Of course, there's a prime^3 extension field, or a prime^4 extension field, and then the analogy kind of stops working. EDIT: Now that I think of it... I can't really decide if complex-numbers are like a prime^4 field or like a prime^2 field. i^4 == 1 after all. In a prime^2 field, the variable x^2 == 1. In a prime^200 field, x^200 == 1. Etc. etc. ------------- Really, the glorious thing about extension fields is that a well selected extension field follows the fundamental theorem of algebra (which is... in simple terms... "All Polynomial equations have an answer that can be represented by your number system". Ex: (x^2 + 1 == 0) not only can be solved by a complex number x = i, but all such possible equations are proven to have an answer). So you get all the benefits of integers (such as perfectly mapping to 2^8 == 256), with none of the downsides of real (aka: uncountably infinite, rounding errors, etc. etc.). You get precision while still keeping your property of "having answers" to a huge class of important algebraic problems.
- ducttapecrown 5y agoThe complex numbers are a degree 2 field extension over the real numbers. The general theorem is that for a field k, and an irreducible (meaning it can't be factored with coefficients in k) polynomial p(x) with coefficients in k, the smallest field containing a root of p(x) and k is a vector space (over k) of dimension deg p(x). The irreducible polynomial corresponding to i is x^2 + 1 = 0. Similarly, a finite field of order q = p^r can be constructed with an irreducible polynomial of degree r with coefficients in the prime field of order p.
- rackjack 5y agoTo those curious: IIRC Extension fields can be described by polynomials. Example: F_2 = { 0, 1 }. f(x) = x^2 + x + 1. (This is "irreducible", which basically means it's "prime" in a polynomial world.) Note that F_2[x] is the set of polynomials with variable x and scalars in F_2. F_2[x]/f(x) = { 0, 1, x, x + 1 } (for each polynomial, take it modulo f(x)). This is because we know that x^2 + x + 1 = 0 => x^2 = x + 1 (please read = as "equivalent" - really, these relations should be modulo x^2 + x + 1). |F_2[x]/f(x)| = 4. 2^2 = 4. This is not a coincidence. The degree of the polynomial determines the size of the resultant field. For F_p[x]/h(x), where p is a prime and h(x) is irreducible with degree d, |F_p[x]/h(x)| = p^d. Another Example: g(x) = x^3 + x + 1. (This polynomial is also irreducible.) F_2[x]/g(x) = { 0, 1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1 } |F_2/g(x)| = 8 = 2^3. Edit: Also, I forgot to mention that the values in the resultant fields F_2[x]/f(x) (and F_x/g(x) correspondingly) should really have the form [v]_f(x), where v is in F_2[x]. That is, they are congruence classes modulo f(x) of values in F_2[x].
- dragontamer 5y agoThat's a decent summary. But it helps if people knew about prime fields (and I expect most people don't know enough about prime fields to learn about extension fields). Prime Field 2 (F_2) is too small and too easy to be a good example. I prefer teaching prime fields with Prime Field 5. 5 is a prime number, which means standard math modulo 5 results in a finite field. There are three attributes of a field: 1. An "addition" operator exists. 2. Every value "v" in the field has a value -v, also known as the "additive inverse". v + (-v) == 0 by definition. The value "0" is defined to be the "additive identity" 3. A "multiplication" operator exists. 4. EVERY value except 0 in the field has a value 1/v (where v is that arbitrary value). v * (1/v) == 1. This value "1" is defined to be the multiplicative identity. 0 has no inverse. --------- So, lets prove that the F_5 is a field, which instead of using fancy math, can be done by exhaustion (!!!). I just show every single number on a case-by-case basis has the properties we want and we're set. F_5 is the numbers {0, 1, 2, 3, 4}. + is normal addition mod 5, * is normal multiplication mod5. By simply describing all inverses (both additive inverses and multiplicative inverses), and proving that they operate as expected, we prove F_5 is a field by exhaustion. Note: a proper textbook would prove this in general over all prime numbers. This shortcut to just doing F_5 by exhaustion is just me taking a shortcut in explanations. * 0 is its own additive inverse. 0 + (-0) == 0 mod 5. * 1 is the inverse of 4. 1 + (-1) == 1 + 4 == 5 mod 5 == 0 mod 5. * 2 is the inverse of 3. 2 + (-2) == 2 + 3 == 5 mod 5 == 0 mod 5. * 3 and 4 play out identically. We've proven addition. Moving onto multiplication. * 0 has no inverse (as per definition of fields). * 1 is its own inverse. 1 * (1/1) == 1 * 1 == 1 mod 5. Not that numbers "outside" of the field, such as 6 still hold the property. 1 * 1 == 6 * 6 == 36 mod 5 == 1 mod 5 * 2 is the inverse of 3. 2 * (1/2) == 2 * 3 == 1 mod 5. * 3 is the inverse of 2, and plays out similarly. * 4 is its own inverse. 4 * (1/4) == 4 * 4 == 1 mod 5. -------------- Note that the distributed property still works. (2 + 4) * 3 == 18 mod 5 == 3 But we can also do it distributed, as well as shortcutting to use the new "multiplicative inverses" that exist in F_5... (2 + 4) * 3 == (2 * 3 + 4 * 3) == 2 * (1/2) + 4 * (1/2) == 1 + 2 == 3 --------- As such, F_5 is a field. It is also finite in length (consisting only of the numbers {0, 1, 2, 3, 4}. Because all numbers have both additive and multiplicative inverses, we can have assurances on the inverse of matricies that use F_5 (as long as det(matrix) != 0, we can find an inverse, because division is always possible), we can always find the roots of polynomials, we can build elliptical curves, etc. etc. Lots of useful properties.