3 ms·

I 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

I 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 ago
  The 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.
- agrounds 5y ago
  Please note that a field that "satisfying the fundamental theorem of algebra" is not really a thing. The term you're looking for is algebraically complete field. The fundamental theorem of algebra states that the complex numbers are algebraically complete. Also note that every algebraically complete field is infinite. So the finite fields used in CS applications such as cryptography are never algebraically complete.

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 ago
The 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.
agrounds 5y ago
Please note that a field that "satisfying the fundamental theorem of algebra" is not really a thing. The term you're looking for is algebraically complete field. The fundamental theorem of algebra states that the complex numbers are algebraically complete. Also note that every algebraically complete field is infinite. So the finite fields used in CS applications such as cryptography are never algebraically complete.