유한체 (finite field)

개요

• 유한체의 크기 \(q\)는 적당한 소수 \(p\)와 자연수 \(r\)에 대하여 \(q=p^r\)를 만족
• 크기가 같은 두 유한체는 동형이며, \(\mathbb{F}_q\)로 나타냄
• 갈루아 체라고 불리기도 함

성질

• \(\mathbb{F}_{q}^{\times}\)는 순환군
• \(n\)차의 기약다항식 \(f\in \mathbb{F}_{p}[x]\)에 대하여, 다음이 성립

\[ \mathbb{F}_{p^n}\cong \mathbb{F}_{p}[x]/(f) \]

• 유한체 \(\mathbb{F}_{q}\) 는 방정식 \(x^{q}-x=x(x^{q-1}-1)=0\) 의 근으로 구성
• \(x^{p^n}-x\)는 \(\mathbb{F}_{p}\)위에서 차수가 \(n\)을 나누고, 최고차항이 1이며 기약인 모든 다항식들의 곱으로 분해됨
• 가령 \(\mathbb{F}_2\)위에서 다음이 성립

\[ x^{2^5}-x=x (x+1) \left(x^5+x^2+1\right) \left(x^5+x^3+1\right) \left(x^5+x^3+x^2+x+1\right) \left(x^5+x^4+x^2+x+1\right) \left(x^5+x^4+x^3+x+1\right) \left(x^5+x^4+x^3+x^2+1\right) \]

예

• \((\mathbb{F}_7,+,\cdot)\)
• 덧셈표

\[ \begin{array}{c|ccccccc} + & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\ 2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ 3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ 4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ 5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 \\ 6 & 6 & 0 & 1 & 2 & 3 & 4 & 5 \\ \end{array} \]

• 곱셈표

\[ \begin{array}{c|ccccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\ 3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\ 4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\ 5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ 6 & 0 & 6 & 5 & 4 & 3 & 2 & 1 \\ \end{array} \]

관련된 항목들

• 정수론에서의 상호법칙 (reciprocity laws)
• 프로베니우스 원소
• 코딩이론
• 유한체에서의 정수론과 기하학

매스매티카 파일 및 계산 리소스

• https://docs.google.com/file/d/0B8XXo8Tve1cxM1NnQVhTbkw3NVE/edit
• http://reference.wolfram.com/mathematica/FiniteFields/guide/FiniteFieldsPackage.html

리뷰논문, 에세이, 강의노트

• Lüneburg, Heinz. 2001. “On the Early History of Galois Fields.” In Finite Fields and Applications (Augsburg, 1999), 341–355. Berlin: Springer. http://link.springer.com/chapter/10.1007%2F978-3-642-56755-1_27

관련논문

• Weingartner, Andreas. ‘On the Degrees of Polynomial Divisors over Finite Fields’. arXiv:1507.01920 [math], 7 July 2015. http://arxiv.org/abs/1507.01920.

노트

말뭉치

1. A finite field with 11 elements can be defined as GF(11^1) .
2. A finite field with 256 elements would be written as GF(2^8) .
3. You can’t have a finite field with 12 elements since you’d have to write it as 2^2 * 3 which breaks the convention of p^m .
4. The notation GF(p) means we have a finite field with the integers {0, … , p-1} .
5. But it may be surprising that there are finite fields.
6. All finite fields have pn elements where p is prime and n is an integer at least 1.
7. The field with pn elements is sometimes called the Galois field with that many elements, written GF(pn).
8. The Galois fields of order GF(p) are simply the integers mod p. For n > 1, the elements of GF(pn) are polynomials of degree n-1 with coefficients coming from GF(p).
9. These are based on linear recurring sequences in finite fields, and in most practical implementations on maximal period sequences (compare with Section 6).
10. Multidimensional analogs of pseudorandom numbers are pseudorandom vectors, which can also be generated by means of finite fields.
11. In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements.
12. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules.
13. The most common examples of finite fields are given by the integers mod p when p is a prime number.
14. Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory.
15. A finite field must be a finite dimensional vector space, so all finite fields have degrees.
16. The previous result does not prove the existence of finite fields of these sizes.
17. Constructing Finite Fields There are several ways to represent the elements of a finite field.
18. Another idea that can be used as a basis for a representation is the fact that the non-zero elements of a finite field can all be written as powers of a primitive element.
19. Finite fields as splitting fields Each nite eld is a splitting eld of a polynomial depending only on the elds size.
20. A finite field is a field with a finite field order (i.e., number of elements), also called a Galois field.
21. For each prime power, there exists exactly one (with the usual caveat that "exactly one" means "exactly one up to an isomorphism") finite field GF( ), often written as in current usage.
22. Note, however, that in the ring of residues modulo 4, so 2 has no reciprocal, and the ring of residues modulo 4 is distinct from the finite field with four elements.
23. Finite fields are therefore denoted GF( ), instead of GF( ), where , for clarity.
24. To understand IDEA, AES, and some other modern cryptosystems, it is necessary to understand a bit about finite fields.
25. The fields that we commonly used in mathematics courses ( For cryptological purposes, finite fields are useful.
26. Q R , Finite field of p elements Recall that the integers mod 26 do not form a field.
27. Two basic finite fields are:Create a finite field with q = p^n elements usingThis creates the ring of characteristic 3, having 3^4 = 81 elements.
28. Finite fields can be used as base rings for polynomial rings.
29. In general, to make a finite field withelements, we use GF The generator of the field can be obtained as usual.
30. Internally, elements of the finite field are stored as powers of the primitive element.
31. Additionally, every finite field extension can be obtained by adjoining elements, possibly several times (in stages).
32. Also called Galois fields, finite fields are often used in cryptography and error checking.
33. For finite fields, Wolfram|Alpha produces the multiplication and addition tables and the primitive and characteristic polynomials, along with several other properties.
34. Suppose that \(F\) is a finite field with \(n\) elements.
35. For every prime \(p\) and every positive integer \(n\text{,}\) there exists a finite field \(F\) with \(p^n\) elements.
36. While this representation is very fast it is limited to finite fields of small cardinality.
37. Sage contains a database of Conway polynomials which also can be queried independently of finite field construction.
38. This lattice is stored in an AlgebraicClosureFiniteField object; different algebraic closure objects can be created by using a different prefix keyword to the finite field constructor.
39. While Sage supports basic arithmetic in finite fields some more advanced features for computing with finite fields are still not implemented.
40. This chapter describes the special functionality which exists in GAP for finite fields and their elements.
41. Of course the general functionality for fields (see Chapter 58) also applies to finite fields.
42. In the following, the term finite field element is used to denote GAP objects in the category IsFFE (59.1-1), and finite field means a field consisting of such elements.
43. Note that in principle we must distinguish these fields from (abstract) finite fields.
44. The finite field with p k p^k pk elements will be a suitable quotient of this ring.
45. AbstractAlgebra.jl provides a module, implemented in src/julia/GF.jl for finite fields.
46. Finite fields have type GFField{T} where T is either Int or BigInt .
47. Elements of such a finite field have type GFElem{T} .
48. In order to construct finite fields in AbstractAlgebra.jl, one must first construct the field itself.
49. In mathematics, a finite field is a field that contains a finite number of elements.
50. Finite fields are an important area of mathematics and computer science and are widely used in geometry, finite geometry, algebraic geometry, number theory, coding theory and cryptography.
51. A finite field is also known as Galois field.
52. We saw earlier how to make a finite field.
53. but they usually factor over finite fields.
54. HOW DO WE KNOW THAT GF (23) IS A FINITE FIELD?
55. We study finite fields first because of their practical applications.
56. Finally, we study finite fields as a simple example of an extension field.
57. A finite extension is an extension of finite degree (not, as one would naturally think, an extension which is a finite field).
58. The explicit construction of finite fields and the computation in finite fields are emphasised.
59. In particular, the construction of irreducible polynomials and the normal basis of finite fields are included.
60. …depend on the use of finite fields, finite geometries, and number theory.
61. All arithmetic operations performed on this field will yield a result that belongs to the same finite field.
62. For example, a finite field of size 256 with numbers from 0 to 255 is defined.
63. All the arithmetic operations (addition, subtraction, multiplication, and division) on this field will yield a result in the range of 0 to 255, thus belonging to the original finite field itself.
64. Conventional arithmetic differs from finite field arithmetic as it operates on an infinite set of real numbers.
65. For example, can there be any finite fields?
66. So has no nontrivial zero divisors, and so every element has an inverse, and so it’s a finite field with elements.
67. The next question is obvious: can we get finite fields of other sizes?
68. The answer turns out to be yes, but you can’t get finite fields of any size.
69. Henceforth, in light of Theorem 2.2 , we will write 𝔽 q for the unique (up to isomorphism) finite field of cardinality q = p n .