콘웨이 다항식(마감 필드)

Conway polynomial (finite fields)

수학에서, 유한장pn F에 대한 콘웨이 다항식p,n C는 F의pn 표준 표현을p,n C의 분할장이라고 정의하는데 사용할 수 있는p F에 대한 수정 불가능한 특정 다항식이다.콘웨이 다항식은 리차드 A에 의해 존 H. 콘웨이의 이름을 따서 명명되었다. 가장 먼저 정의하고 예를 계산한 파커.콘웨이 다항식들은 한 필드의 표현과 그 하위 필드의 표현 사이에 콘웨이가 제안했던 어떤 호환성 조건을 만족시킨다.그것들은 다른 수학 데이터베이스와 컴퓨터 대수 시스템들 사이에서 이식성을 제공하는 컴퓨터 대수학에서 중요하다.콘웨이 다항식은 계산에 비용이 많이 들기 때문에 실제로 사용하기 위해 저장해야 한다.콘웨이 다항식 데이터베이스는 컴퓨터 대수 시스템 GAP,[1] 맥컬레이2, [2]마그마,[3] 세이지매트릭스와 [4]프랭크 뤼벡의 웹사이트에서 이용할 수 있다.[5]

배경

F의pn 원소는 aβn−1n−1 + ... 형식의 합으로 나타낼 수 있다.+ β1 + a0 여기서 β는 F에p 대한 ° n의 무reducible 다항식의 루트이고 a는 F의jp 요소다.이 표현에서 필드 요소의 추가는 벡터 추가일 뿐이다.이형성 p에 이르는 고유의 유한한 질서의 p가n 있는 반면, 필드 요소의 표현은 불가해한 다항식의 선택에 따라 달라진다.콘웨이 다항식은 이 선택을 표준화하는 방법이다.

유한 장의 0이 아닌 원소는 곱하기 아래 순환 그룹을 형성한다.F의pn 원시 원소 α는 이 그룹을 생성하는 원소다.0이 아닌 장 원소를 α의 힘으로 나타내면 장내의 곱셈이 효율적으로 수행될 수 있다.α에 대한 원시 다항식은 F에pn α를 근원으로 하는 F에p 계수가 있는 가능한 최소 수준의 단일 다항식이다(α에 대한 최소 다항식).그것은 반드시 되돌릴 수 없다.콘웨이 다항식은 원시적인 것으로 선택되어 그 뿌리가 각각 연관된 유한장의 승법군을 생성한다.

F의pn 하위 필드는 m을 n으로 나눈 F 필드다pm.F의pm 0이 아닌 원소에서 형성된 순환 그룹은 F의pn 순환 그룹의 하위 그룹이다.α가 후자를 발생시키면 전자를 발생시키는 α의 가장 작은 힘은 α이다r. 여기서 r = (pn - 1)/(pm - 1)f가n 루트 α를 가진 F에pn 대한 원시 다항식이고, f가mpm F에 대한 원시 다항식이라면 콘웨이의 정의에 따르면 f와m f는n α가r f의m 루트라면 호환된다.이를 위해서는m f(x)가n f(xr)를 나누어야 한다.이러한 호환성의 개념은 일부 저자들에 의해 표준 호환성이라 불린다.유한 필드의 콘웨이 다항식은 각 하위 필드의 콘웨이 다항식과 호환되도록 선택된다.이런 식으로 선택을 할 수 있다는 것은 베르너 니켈에 의해 증명되었다.[6]

정의

콘웨이 다항식 C는p,n 모든 m 나누기 n에 대해 C와p,m 호환되는 F에p 대한 사전 통계학적으로 최소의 n 도 원시 다항식으로 정의된다.이것은 n에 대한 귀납적 정의로, 베이스 케이스는 Cp,1(x) = x - α이고, 여기서 α는 F의p 사전적 최소 원시 요소다.사용되는 사전 순서 개념은 다음과 같다.

  • F의p 원소들은 0 < 1 < 2 < ...을 주문한다.< p − 1.
  • Fp[x]에서 d의 다항식은 축dd - 축 + ...라고d−1d−1 쓰여 있다.+ (-d1)a0, 그리고 나서 aadd−1 ... a0. d의 다항식 두 개를 해당 단어의 사전적 순서에 따라 주문한다.

다른 모든 것에 대한 호환성 조건을 만족시키는 하나의 단성 원시 다항식을 제외할 수 있는 어떤 자연적인 수학적 기준이 없는 것처럼 보이기 때문에, 콘웨이 다항식의 정의에 있어서 사전적 순서 부여는 하나의 관례로 간주되어야 한다.

연산

브루트 포스 검색보다 효율적인 콘웨이 다항식 계산 알고리즘은 히스와 뢰어가 개발했다.[7]뤼벡은 그들의 알고리즘이 파커의 방법의 재발견임을 나타낸다[5].

메모들

  1. ^ "Chapter 59". GAP 4 Manual. The GAP Group. Retrieved 8 February 2011.
  2. ^ Grayson, Daniel R.; Stillman, Michael E. "Macaulay2, a software system for research in algebraic geometry". Archived from the original on 20 July 2011. Retrieved 9 February 2011.
  3. ^ Bosma, W.; Steel, A. "Magma handbook: finite fields". Computational Algebra Group, School of Mathematics and Statistics, University of Sydney. Retrieved 8 February 2011.
  4. ^ "Frank Luebeck's tables of Conway polynomials over finite fields". The Sage Development Team. Retrieved 18 March 2013.
  5. ^ a b Lübeck, Frank. "Conway polynomials for finite fields". Retrieved 8 February 2011.
  6. ^ Nickel, Werner (1988), Endliche Körper in dem gruppentheoretischen Programmsystem GAP, Diploma thesis, RWTH Aachen, retrieved 10 February 2011.
  7. ^ Heath, Lenwood S.; Loehr, Nicholas A. (1998). "New algorithms for generating Conway polynomials over finite fields". Virginia Polytechnic Institute and State University. Technical Report ncstrl.vatech_cs//TR-98-14, Computer Science. Retrieved 8 February 2011.

참조