문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 체(대수학) (문단 편집) === 유한체(Finite field) === 지금까지 설명한 체의 예시는 모두 무한집합이었다. 왜냐하면 지금까지 말한 체는 모두 유리수의 집합 [math(\mathbb Q)]를 부분집합으로 갖는데, [math(\mathbb Q)]가 무한집합이기 때문이다. 그렇지만 [math(\mathbb Q)]와는 별개의 근원으로부터 출발한다면 유한집합이 되는 체도 만들 수 있다. 그 별개의 근원이란 다름 아닌 정수의 집합 [math(\mathbb Z)]이다. [math(\mathbb Z)] 자체는 나눗셈이 항상 잘 떨어지지 않으므로, 그 자신이 체가 될 수 없다는 것을 이미 알고 있다. 따라서 [math(\mathbb Z)]를 이용하여 새로운 체를 만들어 낸다는 발상은 꽤 놀라운 것이라고 할 수 있다. [math(\mathbb Z)]로부터 체를 만들어내는 방법은 바로 [[소수(수론)|소수]] [math(p)]로 나눈 나머지를 관찰하는 것이다. 여기에서는 예시를 들기 위해 [math(p=7)]인 경우만을 생각해보자. 이제 정수의 집합 [math(\mathbb Z)]의 원소를 모두 모아놓고, [[시계 산술|이들 중 7로 나눈 나머지가 같은 것은 '''그냥 같은 것으로(equivalent한 것으로) 취급한다!''']] 예컨대, 15를 7로 나눈 나머지와 8을 7로 나눈 나머지는 모두 1이므로, 그냥 15와 8은 '''같은 수'''라고 생각하는 것이다. 그리고 이를 표기하기 위해서는 [math(15\equiv 8\text{ (mod }7))]이라고 쓴다. 한편, 5와 9는 7로 나눈 나머지가 다르므로 [math(5 \not\equiv 9\text{ (mod }7))]이라고 쓸 수 있다. 이렇게 하고 나면, 정수를 7로 나눈 나머지는 0~6의 7가지만 가능하므로, 원래의 [math(\mathbb Z)]는 무한집합이었지만, 이제는 [math(\{0,1,2,3,4,5,6\})]이라는 유한집합이 되어버렸고, 이를 [math(\mathbb Z_7)]이라고 표기한다. (물론, [math(p)]가 다른 소수인 경우에도 [math(\mathbb Z_p)]라고 표기한다.) 이제 [math(\mathbb Z_7)]이 체가 된다는 것을 확인하자. 앞서 말했듯이 어떤 집합이 체가 되는지를 확인하려면 덧셈, 뺄셈, 곱셉, 나눗셈이 잘 이루어지는가를 확인하면 된다. [math(\mathbb Z_7)]의 덧셈은 [math(\mathbb Z)]에서 원래 쓰던 것을 그냥 가져올 것이다. 예를 들어, [math(15+8\equiv 23\text{ (mod }7))]과 같이 덧셈을 할 때에는 평범한 정수를 더하듯이 더해주면 된다. 뺄셈과 곱셈의 경우도 마찬가지로 원래 정수 [math(\mathbb Z)]에서 하던 뺄셈과 곱셈을 [math(\mathbb Z_7)]에 이식하는 것이 가능하다.[* 사실 이러한 이식 과정에서 연산 사이에 호환이 잘 이루어지는지를 추가적으로 확인해보아야 한다. 이는 두 정수 a, b가 주어졌을 때, a와 b를 각각 7로 나눈 나머지를 더한 후 7로 나눈 나머지를 취한 것과, a+b를 7로 나눈 나머지를 취한 것이 동일하다는 사실에 기인하고 있다. 곱셈도 마찬가지이다.] 이렇게 해서 [math(\mathbb Z_7)] 위의 덧셈, 뺄셈, 곱셈은 어렵지 않게 할 수 있다는 것을 확인하였다. 이제 마지막으로 남은 것은 이 위에서 나눗셈을 잘 할 수 있는지를 확인하는 것이다. 그런데 이것은 전혀 쉬운 일이 아니다. 왜냐하면 [math(\mathbb Z_7)]의 근원이 되는 [math(\mathbb Z)] 자체에, 덧셈, 뺄셈, 곱셈만 있었지, 나눗셈은 없었기 때문이다. 나눗셈을 하는 방법은 우리가 새롭게 정의해주어야 하는데, 이때 사용되는 것이 '''확장된 [[유클리드 호제법]]'''(Extended Euclidean algorithm)이다. 확장된 유클리드 호제법이란, 두 정수 [math(a,b)]가 주어졌을 때, 두 수의 최대공약수가 [math(g)]라고 하면, [math(am+bn=g)]가 되는 정수 [math(m,n)]을 언제나 '''빠르게''' 찾아낼 수 있는 알고리즘이다. (사실 저러한 정수 [math(m,n)]이 항상 존재한다는 사실부터가 [[충격과 공포]]다.) 그러면 이제 [math(\mathbb Z_7)] 위에서 나눗셈을 할 수 있다. 나눗셈은 역원을 곱하는 것이므로, 0 이외의 수가 항상 역수를 가진다는 것을 보이면 그것이 곧 나눗셈을 할 수 있다는 것을 보이는 것과 같다. 0이 아닌 원소 1, 2, 3, 4, 5, 6에 대해서 각각 역원을 찾으려면 어떻게 해야할까? 1~6은 모두 7보다 작은 자연수이고, 7은 소수이므로, 1~6은 모두 7과 서로소이다. 즉, 최대공약수가 1이다. 따라서 이 중 3의 역원을 계산하고자 한다면, 3과 7을 확장된 유클리드 알고리즘의 입력으로 넣어준다. 3과 7의 최대공약수는 1이므로, 알고리즘은 [math(3m+7n=1)]이 되는 정수 [math(m,n)]을 반환해준다. 그러면 이때의 [math(m)]이 바로 3의 역수, 즉 [[잉여역수]]가 된다. 왜냐하면 [math(3m\equiv 3m+0n\equiv 3m+7n\equiv 1\text{ (mod }7))]이기 때문이다. 실제로 계산을 해보면 [math(3\times 5\equiv 15\equiv 1\text{ (mod }7))]이므로 3의 잉여역수는 5가 되는 것을 알 수 있다. 따라서 [math(\mathbb Z_7)]는 체가 된다. 그리고 이는 위에서 예시로 보여주었던 체들과는 달리 유한집합이다. 이와 같이 유한집합이 되는 체를 유한체 또는 갈루아 체라고 부른다. 유한체는 이미 수학자들에 의해 완벽한 분류(classification)[* classification 문제는 수학의 곳곳에서 발견되는 아주 중요한 문제이다.]가 이루어져 있다. 보다 자세히 말하자면, 유한체의 원소의 개수는 모두 [math(p^n)] (단, [math(p)]는 소수)의 꼴로 표현되고, 원소 수가 [math(p^n)]개인 체는 오직 하나가 존재한다는 사실이 증명되어 있다.[* 존재성 증명: [math(\mathbb Z_p)]위의 다항식 [math(x^{p^n}-x=0)]과 이것의 해의 모임 [math(F)]를 생각하자. [math(\text{char}\left(\mathbb Z_p\right)=p)]이므로, [[1학년의 꿈|임의의 [math(\alpha,\beta \in F)]에 대하여 [math(\left(\alpha+\beta\right)^{p^{n}}=\alpha+\beta)]]]이다. 나머지 체의 공리들은 쉽게 보일 수 있다. 따라서, [math(F)]는 [math(\mathbb{Z}_p)]위의 다항식 [math(x^{p^{n}}-x=0)]의 분해체이다.][* 유일성 증명: [math(\left|F\right|=p^{n})]인 체 [math(F)]에 대해, [math(F^{\times})]는 곱셈군이므로, 모든 [math( \alpha\in F^{\times})]에 대해 [math(\alpha^{p^{n}-1}=\alpha^{\left|F^{\times}\right|}=1)]이다. 따라서, 모든 [math( \alpha\in F)]에 대해, [math(\alpha^{p^{n}}-\alpha=0)]이다. 즉, [math(F)]의 모든 원소는, [math(\mathbb{Z}_p)]위의 다항식 [math(x^{p^{n}}-x=0)]의 근이고, 이 방정식의 차수는 [math(p^{n}=\left|F\right|)]이므로, [math(F)]는 [math(\mathbb{Z}_p)]위의 다항식 [math(x^{p^{n}}-x=0)]의 분해체이다. 분해체의 유일성에 의해, [math(F)]는 유일하다.] 즉, 원소 수가 7개인 체는 위에서 밝혀낸 [math(\mathbb Z_7)] 하나뿐인 것이다. 위에서 설명한 방법을 사용하면 원소의 개수가 [math(p)]인 체는 모두 만들어낼 수 있는데, 어떻게 하면 [math(p^n)]개의 원소를 가지는 체를 만들어낼 수 있을까? 이는 조금 더 복잡하지만 정수를 소수로 나눈 나머지를 생각하는 대신, [math(\mathbb Z_p)]의 원소를 계수로 가지는 다항식을 [math(n)]차 기약다항식으로 나누는 방법을 사용하여 만들 수 있다. 유한체의 분류 문제가 완벽하게 해결되었다고 해서, 유한체는 비교적 단순한 대상이라는 '''오해'''가 있을 수도 있다. 전혀 그렇지 않다. 예를 들어, 유한체 위에서 곱셈이 잘 정의되기 때문에, 실수에서의 로그와 비슷한 것을 생각하여 [math(\mathbb Z_p)] 위에서의 로그를 생각해볼 수 있다. 예를 들어, [math(\mathbb Z_7)] 위에서 생각한다면 [math(\log_3 6\equiv 3)]이다. 이는 [math(3^3\equiv 27\equiv 6\text{ (mod }7))]이기 때문이다. 그렇지만 이렇게 로그를 계산하는 것은 소수 [math(p)]가 50자리 이상의 큰 수가 되고 나면 더이상 쉬운 문제가 아니다. 이와 같은 것을 이산 로그 문제(DLP)라고 하는데, 양자컴퓨터를 사용하지 않고서는 빠르게 계산하는 방법이 전혀 밝혀지지 않았기 때문에, 심지어는 이를 응용하여 암호 시스템을 만들 수 있을 정도이다! [[https://crypto.stackexchange.com/questions/9385/reduction-of-integer-factorization-to-discrete-logarithm-problem|이산 로그 문제와 소인수분해 문제가 동등함을 쉽게 밝힐 수 있고]], 이산 로그 문제의 다항 시간 해법을 알면 다항 시간 내에 끝나는 간편한 소인수분해 알고리즘을 만들 수 있다. 복잡한 정수론적 문제란 곧 새로운 암호 시스템 하나를 의미한다. 잘 알려져 있듯이, 소인수분해의 어려움은 널리 쓰이는 [[RSA]] 암호 시스템의 기초가 된다. 그러나 RSA는 양자컴퓨터가 개발되면 공격할 수 있기 때문에, 요즘 수학자들은 양자컴퓨터로도 풀기 어려운 [[격자점|격자(lattice)]] 문제에 기반하는 다른 암호 시스템의 안전성을 연구하고 있다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기