(Z/pZ)[x] (Polynomials over Z/pZ)

(Z/pZ)[x]는 계수가 소수 p를 법으로 하는 정수의 체 Z/pZ에 속하는, 변수 x에 대한 다항식 환을 나타내는 수학 표기법입니다. 계수 연산은 모두 p로 나눈 나머지로 이루어집니다.

표기의 구성

• Z: 모든 정수의 집합.
• p: 소수.
• Z/pZ: p를 법으로 하는 정수로, 원소가 {0, 1, …, p−1}인 유한체를 이룹니다. GF(p) 또는 F_p라고도 씁니다.
• [x]: 이 체의 원소를 계수로 하는, 부정원(변수) x에 대한 다항식 전체.

핵심: 모듈러 계수를 갖는 다항식

(Z/pZ)[x]의 모든 다항식은 {0, 1, …, p−1}에서 가져온 계수를 가집니다. 계수 연산은 p를 법으로 하므로 결과가 p 이상이 되면 다시 0부터 순환합니다. 눈금이 p개인 시계를 떠올리면 됩니다. 다항식을 더하거나 곱한 뒤 동류항을 정리하고, 계수를 p로 나눈 나머지로 줄이면 됩니다.

계산 예 (p = 3)

• 덧셈: (2x + 1) + (x + 2) = 3x + 3이고, 계수를 3으로 나눈 나머지로 줄이면 0입니다.
• 곱셈: (x + 2)(x + 1) = x² + 3x + 2 ≡ x² + 2입니다.
• 기약 다항식: x² + 1은 Z/3Z에서 근이 없으므로(0, 1, 2를 넣으면 1, 2, 2) 인수분해되지 않는 기약 다항식입니다.

중요한 성질

• 나눗셈 정리: 계수가 체에 속하므로 정수처럼 몫과 나머지를 갖는 다항식 나눗셈이 항상 가능하고, 유클리드 호제법으로 최대공약수를 구할 수 있습니다.
• 유일 인수분해: 모든 다항식은 기약 다항식들의 곱으로 (순서와 상수배를 제외하고) 유일하게 분해됩니다.
• 유한체 구성: 차수 n인 기약 다항식 f(x)로 나눈 나머지를 모으면 원소가 pⁿ개인 유한체 GF(pⁿ) = (Z/pZ)[x]/f(x)가 됩니다. 위의 예에서 (Z/3Z)[x]/(x² + 1)은 원소가 9개인 체입니다. p = 2인 경우가 AES 등에서 쓰는 GF(2ⁿ)입니다.
• 일반 정수 계수와의 차이: 예를 들어 Z/pZ에서는 (x + 1)^p = x^p + 1이 성립하는 등, 정수 계수 다항식과 다른 고유한 연산 규칙이 생깁니다.

암호와 부호 이론에서의 쓰임

• 비밀 공유: 샤미르의 비밀 공유는 Z/pZ 위의 다항식에 비밀을 상수항으로 넣고, 여러 점의 값을 참여자에게 나누어 줍니다. 정해진 수 이상의 값이 모이면 보간으로 다항식을 복원합니다.
• 유한체 구성: 타원곡선 암호와 여러 암호 알고리즘이 쓰는 확대체 GF(pⁿ)를 만드는 데 쓰입니다.
• 오류 정정 부호: 리드-솔로몬 부호, BCH 부호 같은 부호가 유한체 위의 다항식으로 설계됩니다.

고려할 점

• 매개변수 선택: 암호에서 보안은 충분히 큰 p나 적절한 다항식을 고르는 데 달려 있으며, 약한 매개변수를 고르면 취약점이 생길 수 있습니다.
• 구현 안전성: 계산 중 타이밍이나 전력 소비 차이를 악용하는 부채널 공격에 대비해 구현을 신중하게 설계해야 합니다.

(Z/pZ)[x]는 유한체와 그 위의 다항식을 다루는 출발점으로, 대수학, 암호, 부호 이론의 기본 도구입니다.