[암호학] 3. 자연수

갑자기 자연수?

수는 모든 학문의 기초가 되고 그 중 가장 생각하기 쉬운 자연수는 어디에든 나타나는 개념이다.

하지만 우리는 자연수란 무엇인가?라고 질문하면 쉽게 답하기 어렵다.

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이라고 표현하면 될 것이다.

 

소수는 암호에서 굉장히 많이 사용되고 있다.

앞으로 소수를 사용한 많은 연산과 개념들이 나오게 될 것이다.