인수분해 알고리즘
인수분해 알고리즘
  • 김장천
  • 승인 2010.03.18 16:19
  • 댓글 0
이 기사를 공유합니다

수학자들은 불규칙한 자연의 겉모습에 숨겨진 규칙성을 찾아내어 이를 수학적으로 재해석하고자 시도하였다.

1975년 ‘프랙탈’이라고 이름붙인 이론은 오늘날 실생활에서 금속의 경도나 강도를 측정하는 일에서부터 우주론, 생태학에 이르기까지 광범위한 영역으로 적용 범위를 넓혀가고 있다. 실제로 극히 최근까지도 수학은 학문의 세계에서 집안일을 도맡아 처리하면서도 바깥출입이 제한된 안방마님과 같은 존재였고, 늘 경기에 출전하지만 뒷전에 머물러 선수들의 활약상을 지켜보던 축구경기 감독과 같은 신세였다. 왜냐하면, 복잡한 논리, 추상적인 용어, 알아듣지 못할 방정식 등 수학이 갖는 일반적인 특징이 화려한 플레이를 기대하는 관객의 눈길을 끌지 못하기 때문이다. 그런데 최근 수학이 지식 산업 시대, 정보화시대의 새로운 첨병으로 떠오르고 있는 것이다.

예전에는 기초과학과 실생활의 부가 가치 창출이라는 목표 사이에서 응용과학이라는 중간단계가 있었다. 그러나 최근 그 중간단계가 빠른 속도로 무너지고 있다. 반면에 과거 무대의 뒷전에 머물러 있던 기초과학, 특히 수학이 무너진 틈새를 비집고 나와 직접 부가가치를 창출하고 있다. 앞서 소개한 암호학과 소수의 관계가 대표적인 예다.

1과 자신으로만 나누어지는 수를 소수라고 한다. 수학에서는 소수에 대한 연구는 오랫동안 소수 자체의 아름다움을 추구하는 순수한 입장을 견지한 연구였다. 그런데 지금은 전혀 다른 상황이다. 오늘날 소수에 대한 각종 연구는 첨단 컴퓨터 이론과 함께 컴퓨터 암호기술의 핵심을 이룬다. 순수수학의 진영에서 단숨에 응용수학의 진영으로 전향한 것이다. 소수는 무한히 많고, 또 조금만 큰 수가 되면 찾아내기가 굉장히 어려워서 암호로 쓰기에 안성맞춤이기 때문이다.

잘 알려져 있듯이 1에서부터 10까지 사이의 소수는 4개(2,3,5,7)이다. 계속해서 소수를 찾아보면, 11, 13, 17, 19, 23, 29, 31, 37,...적어도 두 자리로 이루어진 숫자들 가운데 소수를 찾기는 어렵지 않다. 그런데 숫자가 점점 커질수록 소수를 골라내는 일은 점점 더 어려워진다. 현재 80자리 수를 소인수분해를 하는데 는 슈퍼컴퓨터로도 하루 정도 시간이 걸리는 것으로 알려졌다. 지난 수세기 동안 수학자들은 소수를 찾는 일에 무진 애를 써 왔다. 바로 이 같은 과정을 통해서 확인한 사실이 컴퓨터가 등장한 이후 해독의 난해함을 기본 생명으로 하는 암호기술에 그대로 적용된 것이다.

수학계에서는 두 100자리 소수들의 곱으로 된 200자리 합성수는 제아무리 뛰어난 컴퓨터의 공격으로도 결코 허물어지지 않는다고 믿고 있다.

암호기술은 군사, 외교, 국방 분야는 물론 전자 상거래와 계약, 심지어 개인 간 편지 주고받기에 이르기까지 사회생활의 모든 영역에서 사용되고 있다. 소수는 특히 첨단 정보화 사회가 된 오늘날에는 정보를 보호하는 암호에 사용되고 있다. 최근에 사용되는 암호는 대부분 소수를 이용한 공개 열쇠 암호 방식으로 만들어져 있다.

공개 열쇠 암호 방식은 암호를 만드는 방식은 공개되지만 그 암호를 원래의 문장으로 돌려놓는(이 과정을 복호라고 한다) 열쇠를 알아내기가 거의 불가능한 방식이다. 이런 방식이 가능한 이유는 큰 정수를 소인수 분해하는 것이 매우 어렵기 때문이다. 예를 들어 어떤 두 소수를 곱한 수 4067351을 이용하여 암호를 만들었다는 것을 공개한다. 그런데 암호를 원래의 문장으로 돌려놓기 위해서는 이 수가 어떤 두 소수의 곱으로 되어 있는지 알아야 한다.

사실 이 수는 두 소수 1733과 2347의 곱이다. 그런데 두 소수 1733과 2347을 주고 이들의 곱 4067351을 계산하는 문제는 아주 쉽지만, 거꾸로 4067351이 어떤 두 소수의 곱으로 되어 있는지를 찾는 소인수분해 문제는 매우 어렵다. 실제로 사용되는 공개 열쇠 암호 방식은 예를 든 방법보다 훨씬 복잡하고 정교하지만, 소인수분해가 어렵다는 암호의 근본 원리는 같다.

1977년에 공개열쇠 암호 방식이 처음 발표될 당시, 예로 들었던 두 소수를 곱한 수(수가 너무 크기 때문에 여기서는 생략한다)를 인수분해 하는데 약 40,000,000,000,000,000년이 걸릴 것으로 예상했다.

그러다가 1994년에 인수분해 알고리즘이 개발되며 인수분해를 좀 더 빨리 할 수 있게 되었는데, 다행스럽게도 인수분해 알고리즘을 이용해도 100년 이상 걸린다. 그래서 공개열쇠 암호방식은 오늘날 은행의 저금통장의 비밀번호에서부터 인터넷에서 사용되는 ID와 암호 등 다양하게 이용되고 있다. 그러나 인수분해 알고리즘이 계속해서 발전하고 있기 때문에 그에 대응하여 더 큰 소수가 필요하게 되었다. 그래서 소수를 연구하는 수학자들은 더 큰 소수를 찾기 위해 지금도 노력하고 있다.

수학의 위력은 이처럼 거의 모든 사물의 특징, 원리를 수학적 방법론으로 이해하고 이를 증명한다는데 있다. 수학이 단순한 공식이나 외우는 학문이 아니라, 현상을 이해하고 사고하는 학문이라고 말해지는 까닭이 바로 여기에 있다. 수학은 수학자들이 익히 다루어 왔던 숫자 그 자체, 삼각형, 사각형, 등 도형과 원, 곡선, 공간은 물론 심지어 비누막이나 물방울, 하다못해 실로 만든 매듭, 미술작품이나 음악소리까지도 연구 대상으로 삼아 발전을 거듭해 왔다.

앞으로도 수학은 자신의 연구 성과를 나눔으로써 인접 학문들에게 마음씨 좋은 시어머니 노릇을 톡톡히 할 것이 틀림없다. 그러나 수학이 자신의 역할을 수행하는 방식은 크게 달라질 것이라고 수학자들은 단언한다.

댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.