원시 다항식(필드 이론)

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "원시적 다항식" 필드 이론 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수학의 한 분야인 분야 이론에서 원시 다항식은 유한 확장 분야 GF(p^m)의 원시 요소의 최소 다항식이다.즉, GF(p) = Z/pZ에 계수가 있는 다항식 F(X)는 그 정도가 m이고 GF(p^m)에 루트 α가 있어 {0, 1, α, α²³, …, α^pm−2}이(가) 전체 필드 GF(p^m)가 될 경우 원시 다항식이다.이는 또한 α가 GF(p^m)에서 단결의 원시적(p^m - 1)-근본이라는 것을 의미한다.

특성.

모든 최소 다항식들은 해독이 불가능하기 때문에, 모든 원시 다항식들도 역시 해독이 불가능하다.

원시 다항식에는 0이 아닌 상수 항이 있어야 하는데, 그렇지 않으면 x에 의해 분할될 것이기 때문이다. GF(2), x + 1은 원시 다항식이고 다른 모든 원시 다항식들은 홀수 수가 있는데, 이는 항 수가 짝수인 다항식 모드는 x + 1로 분할되기 때문이다(뿌리로서 1이 있다).

GF(p) 위에 m 도(di)의 수정 불가능한 다항식 F(x)는 p가 prime인 경우 F(x)가 x - 1을 나누는ⁿ 최소 양의 정수 n이 n = p - 1이면^m 원시 다항식이다.

GF(p^m)를 넘어서면 정확히 ((p^m - 1)/m 원시 다항식 m이 있는데, 여기서 φ은 오일러의 토털 함수다.

도 m의 원시 다항식은 GF(p^m)에 서로 다른 뿌리를 가지고 있으며, 모두 p - 1의^m 순서를 가지고 있다.즉, α가 그러한 뿌리라면, 0 < i < p^m - 1>에 대해서는^pm−1 α = 1과 αⁱ α 1을 의미한다.

GF(p^m)에서 원시 원소 α의 도 m의 원시 다항식 F(x)는 F(x) = (x - α)(x - α^pp2)(x - α))⋅(x - α)⋅⋅(x - α)⋅⋅(x - α^pm−1)(⋅(x - α)을 명시적으로 가지고 있다.

사용법

필드 요소 표현

원시 다항식은 유한장의 원소 표현에 사용된다.GF(p^m)의 α가 원시 다항식 F(x)의 뿌리라면, α의 순서는 p - 1이므로^m GF(p^m)의 모든 비제로 원소를 α의 연속적인 힘으로 나타낼 수 있다.

${\displaystyle \matrm {GF}(p^{m})=\{0,1,\cHB ,\cHB ^{2},\ldots ,\cHB ^{p^{m}-2}\}.}$

이러한 요소가 축소된 모듈로 F(x)인 경우, 필드 모든 요소의 다항식 기본 표현을 제공한다.

유한 장의 곱셈 그룹은 항상 순환 그룹이기 때문에 원시 다항식 f는 다항식으로서, x는 GF(p)[x]/f(x)에 있는 곱셈 그룹의 생성자다.

의사 임의 비트 생성

두 개의 원소가 있는 필드인 GF(2)에 대한 원시 다항식을 유사성 비트 생성에 사용할 수 있다.실제로 최대 사이클 길이(2ⁿ - 1, 여기서 n은 선형 피드백 시프트 레지스터의 길이)를 가진 모든 선형 피드백 시프트 레지스터는 원시 다항식으로부터 구축될 수 있다.^[1]

예를 들어 원시 다항식 p(x¹⁰) = x + x + 1을³ 고려할 때, 사용자가 지정한 0이 아닌 10비트 시드(non-zero 10 bit seed)가 비트 위치 1부터 10까지를 점유하는 것으로 시작하며, 이는 GF(2)에 대한 다항식의 계수를 나타낸다.(씨앗은 무작위로 선택할 필요는 없지만, 될 수 있다.)그런 다음 시드를 왼쪽으로 이동하여 0번째 비트가 위치 1로 이동하여 GF(2^10)[x]/p(x)의 원시 요소인 x에 곱하기. 그런 다음 10번째 비트와 3번째 비트를 취하여 새로운 0번째 비트를 생성하여 3번째 비트의 xor가 0으로 분할 모듈로 p(x)를 달성한다.2¹⁰ - 1 = 1023 의사 난수 비트를 생성하기 위해 이 프로세스를 반복할 수 있다.

일반적으로 GF(2)에 대한 도 m의 원시 다항식의 경우, 이 프로세스는 동일한^m 순서를 반복하기 전에 2 - 1개의 의사 난수 비트를 생성한다.

CRC 코드

CRC(순환 중복 검사)는 메시지 비트 문자열을 GF(2)에 대한 다항식 계수로 해석하고 이를 GF(2)에 대한 고정 발전기 다항식 계수로 나누어 작동하는 오류 감지 코드다. CRC의 수학을 참조한다.원시 다항식(prival polyomial) 또는 그 중 복수형은 메시지 비트 문자열에서 2 - 1의 원초 다항식의 경우 최대 2ⁿ - 1의 거리까지 크게 발생하는 2비트 오류를 신뢰성 있게 검출할 수 있기 때문에 발전기 다항식에 적합한 선택이다.

원시삼원체

원시 다항식의 유용한 세분류는 원시^r 삼항이며, 0이 아닌 3개의 항을 가진 것은 x + x + 1이다^k.이러한 단순성은 특히 작고 빠른 선형 피드백 시프트 레지스터를 만든다.많은 결과는 삼원체의 원시성을 찾고 시험하는 기법을 제공한다.

GF^r(2)를 통한 다항식의 경우, 2 - 1은 메르센 프라임인 경우, 2 - 1은 변경할 수 없는 경우에만 도 r의 다항식은 원시적이다. (x의 기간이 2^r - 1의 비가항인 경우에만 원시적이지 않다. 프라임에는 비경쟁인자가 없다.)메르센 트위스터 사이비 난수 발생기는 삼원형을 사용하지 않지만 이를 활용한다.

리처드 브렌트는 x^74207281 + x^30684570 + 1과 같은 이 형태의 원시 삼원체 표본을 만들어 왔다.^[2][3]이것은 거대한 기간^74207281 2 - 1 × 3×10의^22338617 의사 난수 생성기를 만드는 데 사용할 수 있다.

참조

외부 링크

• Weisstein, Eric W. "Primitive Polynomial". MathWorld.