갑자기 자연수?
수는 모든 학문의 기초가 되고 그 중 가장 생각하기 쉬운 자연수는 어디에든 나타나는 개념이다.
하지만 우리는 자연수란 무엇인가?라고 질문하면 쉽게 답하기 어렵다.
1,2,3같이 개수를 셀 수 있는 수 아닌가요?
위와 같은 답은 생각하긴 쉽지만 모호한 답이다.
자연수를 엄밀하게 정의하기 위해 보통 페아노 공리계를 말하곤 한다.
https://namu.wiki/w/%EC%9E%90%EC%97%B0%EC%88%98#s-2.1
수학도 그렇고 과학도 그렇고 이공계학문은 공리에서 시작한다. 이를 Axiomatic Approach라고 한다.
자연수도 위와 같은 공리에서 시작했고 자연수를 확장해 정수, 유리수, 실수가 탄생하게 된 것이다.
아무튼 가장 널리 사용되는 자연수는 페아노 공리계를 사용해 귀납적으로 정의를 할 수 있다.
그 밑에 0을 포함하는 공리계라고 해서 범자연수라는 체계가 있다.
0을 자연수에 포함하면 많은 부분에서 편리함을 느낄 수 있기 때문에 이러한 수체계도 사용한다고 한다.
여담으로 여러 알고리즘 문제에서 자연수 대신 양의 정수를 사용하는 이유가 위와 같이 자연수 체계가 여러개이기 때문이다.
Interesting Natural Numbers
Every Natural Number is Interesting.
네 모든 자연수는 흥미롭습니다.
약간 의미부여긴 하지만 아래와 같이 생각해보자.
1 : 첫 번째 자연수
2 : 첫 번째 소수
3 : 첫 번째 홀수 소수
4 : 첫 번째 제곱수
5 : 첫 번째 서로 다른 소수의 합
...
이런식으로 의미를 부여할 수 있다.
어떤 자연수든 첫 번째인 역할을 한다는 것이다.
그렇다고 모든 자연수에 대해 Interesting Number라고 할 수 있나요?
proof
귀류법을 사용한다.
자연수 안에 어떤 uninteresting number $x$가 존재한다고 하자.
여러개일 수 있는데 $x$는 그 중 가장 작은 값이라고 한다.
그럼 $x$는 처음으로 나오는 uninteresting number이다.
결국
$x$ : 첫 번째 uninteresting number
라는 interesting number가 된다. $\Box$
뭔가 이상한데 그럴듯하다.
사실 증명이라고 썼지만 엄밀한 증명은 아니라고 한다.
그냥 넘어가자....
Prime Number
자연수중에서 Interesting이라고 하면 Prime Number(소수)를 빼놓을 수 없다.
소수는 1과 자기자신만으로 나누어 떨어지는 수
2, 3, 5, 11...이 있다.
0은 왜 소수가 아닐까?
소수에 정의에 의하면 자기자신으로 나누어 떨어질 수 있어야 한다고 한다.
범자연수체계를 사용하더라도 0으로 나누는게 정의되지 않는다.
그래서 소수가 아니다.
1은 왜 소수가 아닐까?
이는 여러 논쟁이 오갔다고 하는데 결론적으로 1이 소수일경우 다른곳에서 불편한 점이 너무 많기 때문이라고 한다..
그래서 소수가 아니게 되었다.
2는 왜 소수일까?
2는 유일한 짝수인 소수이다.
2도 빼면 소수는 홀수로만 이루어져 있어 굉장히 예쁜(?)집합이 될 수 있지만 2는 도저히 뺄 이유가 없다.
1은 뺄만한 분야와 이유가 있다고 하지만 2는 그런게 없다고 한다.
그래서 소수가 되었다.
2를 빼고 싶으면 odd prime이라고 표현하면 될 것이다.
소수는 암호에서 굉장히 많이 사용되고 있다.
앞으로 소수를 사용한 많은 연산과 개념들이 나오게 될 것이다.
'기타 > 암호학' 카테고리의 다른 글
[암호학] 5. 집합론 2 (0) | 2022.12.13 |
---|---|
[암호학] 4. 집합론 1 (0) | 2022.12.09 |
[암호학] 2. Halting Problem (0) | 2022.12.04 |
[암호학] 1. 암호란 무엇인가? (1) | 2022.12.02 |
[암호학] 0. 암호학 (0) | 2022.12.02 |