Finite Fields
Groups, Rings, and Fields
- Fields are a subset of rings, which are a subset of the groups.
- Groups are defined by a simple set of properties. Each successive subset adds additional properties and is thus more complex.
- 同一集合中的兩個元素以多種方式組合後得到的元素,仍在同一個集合內
- 這些特殊的運算規則定義了集合的性質
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Group
A group , sometimes denoted by , is a set of elements with a binary operation denoted by that associates to each ordered pair (a, b) of elements in G an element in , such that the following axioms are obeyed:
The operator is generic and can refer to addition, multiplication, or some other mathematical operation.
- (A1) Closure: If and belong to , then is also in .
- (A2) Associative: for all in .
- (A3) Identity element: There is an element in such that for all in .
- (A4) Inverse element: For each in , there is an element in such that .
Abelian Group
A group is said to be abelian (also called commutative) if it satisfies the following additional condition:
- (A5) Commutitive: for all in .
Example:
- The set of integers (positive, negative, and 0) under addition is an abelian group.
- The set of nonzero real numbers under multiplication is an abelian group.
Cyclic Group
- Define exponentiation within a group as repeated application of operator
- Define as the identity element.
- A group is cyclic if every element in is a power ( is integer) of some fixed element .
Ring
https://math.ntnu.edu.tw/~li/algebra-html/chap5.pdf
A ring , sometimes denoted by , is a set of elements with two binary operations, called addition and multiplication, such that for all in the following axioms are obeyed.
- (A1 - A5) R is an abelian group with respect to addition; that is, R satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as 0 and the inverse of a as -a.
- 在加法運算下是一個 abelian group
- 乘法僅要求封閉性和結合律
- (M1) Closure under multiplication: If and belong to , then is also in .
- (M2) Associativity of multiplication: for all in .
- (M3) Distributive laws:
for all in .
for all in .
本質上 ring 是一個可以在其中進行加法、減法 [] 與乘法的集合(運算後結果仍在集合中)。
Commutative Ring
A ring is said to be commutative if it satisfies the following additional condition:
- (M4) Commutativity of multiplication: for all in .
Integral Domain
Define an integral domain, which is a commutative ring that obeys the following axioms.
- (M5) Multiplicative identity: There is an element 1 in such that for all in .
- (M6) No zero divisors: If in and , then either or .
Field
https://ccckmit.gitbooks.io/rlab/content/field.html
A field F, sometimes denoted by , is a set of elements with two binary operations, called addition and multiplication, such that for all in the following
axioms are obeyed.
- (A1 - M6) is an integral domain; that is, satisfies axioms A1 through A5 and M1 through M6.
- (M7) Multiplicative inverse: For each in , except 0, there is an element in such that .
本質上 field 是一個可以在其中進行加法、減法、乘法與除法的集合。除法定義為 。
Field 範例:
- 有理數:
- 實數:
- 複數:
- 由於整數中只有 1 與 -1 有乘法反元素,因此整數不是一個 field。
Properties of Groups, Rings, and Fields
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Finite Fields
- Galois Fields
- Finite fields are of increasing importance in Cryptography
- The finite field of order(階,元素的個數), where p is a prime, is generally written
- Special Finite Fields
- : Prime Field
- The set of integers with arithmetic operations modulo prime .
- : Binary Field
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Example: is the simplest finite field.
Addition is equivalent to the XOR operation, and Multiplication is equivalent to the logical AND operation.
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Generator of Finite Field
- A generator of a finite field of order (contains q elements) is an element whose first powers generate all the nonzero elements of
Prime Field GF(p)
- The set of integers with arithmetic operations modulo prime .
- Example
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
-
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Finding the Multiplicative Inverse in GF(p)
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Polynomial Arithmetic
Degree: n
Treatment of Polynomials
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
- Three Classes of Polynomial Arithmetic
- Ordinary polynomial arithmetic, using the basic rules of algebra.
- Polynomial arithmetic in which the coefficients are in .
- Polynomial arithmetic in which the coefficients are in , and the polynomials are defined modulo a polynomial whose highest power is some integer .
Ordinary Polynomial Arithmetic
- add or subtract corresponding coefficients
- multiply all terms by each other
- Example
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Polynomial Arithmetic with Modulo Coefficeients
- when computing value of each coefficient do calculation modulo some value
- could be modulo any prime
- most interested in mod 2
- i.e., all coefficients are 0 or 1
- Example
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
- Polynomial Division
- if r(x) = 0, g(x) divides f(x)
- if g(x) has no divisors other than itself & 1, then it is an irreducible polynomial ( prime polynomial)
- arithmetic modulo an irreducible polynomial forms a field

- Examples: Polynomial Arithmetic over
(減法與加法都是 XOR 運算)

Binary Field
Computation in
- polynomials with coefficients modulo 2
- degree < n
- hence must reduce modulo an irreducible poly of degree n (for multiplication only)
- Multiplicative Inverse
- by using the Extended Euclidean Algorithm
Elements of
- Example: 8 Elements of
- Polynomial Representation (form: )
- Binary Representation (form: )
- 000, 001, 010, 011, 100, 101, 110, 111
Addition in
- Example: Addition in
- Polynomial Representation

- Binary Representation
Multiplication in
- Example: Multiplication in
- Polynomial Representation
- using the irreducible poly of degree 3:
- 要標明是使用什麼 irreducible poly,若有其他符合的 irreducible poly 也可以使用
- Binary Representation

Additive and Multiplicative Inverses in
- Example: Additive and Multiplicative Inverses in

- Calculate the Multiplicative Inverse in
- Calculate by using the Extended Euclidean Algorithm
- degree of < the degree of
- Example: Compute
Computational Considerations for
- Represent polynomials as bit strings
- Addition XOR
- Multiplication shift & XOR
- Polynomial Modulo Reduction shift & XOR