경문수학산책 2 수학 : 새로운 황금시대 (1)|

경문수학산책 2, 수학 : 새로운 황금시대(Mathematics : The New Golden Age), Keith Devlin 지음, 허민 옮김, 415쪽, 1995년 초판, 1999년 개정

 

서문에서 지은이는 어느 학문분야에 대하여도 ‘가장 위대한 시대’를 정확하게 말할 수 없다고 전제하면서도 지금 이 순간을 수학의 새로운 황금시대라고 할 수 있다는 관점에서, 1960년 이후 이루어진 발전 가운데에서 일반독자를 대상으로 언론매체에서도 관심을 가질 수 있고 적절한 수준에서 설명할 수 있는 주제만을 선택하여 많은 수학지식이 필요한 경우를 최소화하려고 하였다고 하면서, 수학에 대한 관심과 약간의 인내심만 있으면 대부분의 내용을 읽을 수 있다고 한다.

 

모두 11개의 단원으로 구성되어 있는데, 옮긴이는 이들 주제가 현대수학의 전부를 의미하는 것은 결코 아니지만, 현대 수학을 조망하기에는 충분하다고 한다.

 

하지만 이 책을 읽어 짐작하는 것만으로도 여간 어려운 것이 아니고, 더구나 비록 한 때의 흥미로 삼아 하는 일이라고는 하지만 그 윤곽을 써서 간추리는 것은 매우 버거운 것이다.(사람에 따라 쉬운 것일 수 있다.) 참으로 탁월한 프로그램인 ‘나모 웹에디터(Namo Web Editor)’의 도움으로 수식의 표현에 근접한 것은 이전에 비하여 나아진 것이라고 하겠다. 

 

1. 소수, 소인수분해, 암호

  (1) 가장 큰 소수

현재까지 발견된 가장 큰 소수는 2^n-1의 형태를 하고 있다. n이 커질수록 그 소수는 매우 거대하게 된다. 이러한 수는 컴퓨터에 의하여 다루어지는데, 일반적으로 수퍼 컴퓨터가 이용되지만 개인용 컴퓨터에 의한 공동작업이 이용되기도 한다. 개인용 컴퓨터에 의한 공동작업은 월트먼(George Woltman)이 시작한 GIMPS(Great Internet Mersenne Prime Search)라는 연구계획에 의한 것이다. 이 연구계획은 인터넷으로 전세계에서 많은 지원자를 모아서 새로운 소수를 찾으려고 시도하는 계획이며, 각 회원에게는 관련 프로그램이 제공된다.

 

  (2) 소수

자연수를 그 성질에 따라 분류하는 방법은 여러 가지가 있는데, 그 가운데에서 가장 중요한 방법의 하나가 소수인 자연수와 소수가 아닌 자연수로 분류하는 것이다. 자연수 n이 1과 n 자신으로만 나누어 떨어질 때, n을 ‘소수’라고 하며, 소수 이외의 수를 ‘합성수’라고 한다. 전통적으로 1은 소수도 아니고 합성수도 아니라고 간주한다. 유클리드는 그의 원론 제Ⅸ권에서 1보다 큰 자연수는 소수이거나 소수들을 나열하는 순서를 무시하면 소수들의 곱으로 표현된다고 하는 현재 ‘산술의 기본정리’라고 부르는 명제를 증명하였다. 예를 들면 75,900은 일곱 개의 ‘소인수’의 곱이며, 등호의 오른쪽을 ‘소인수 분해’라고 한다.

75,900=2×2×3×5×5×11×23

'산술의 기본정리'는 소수가 기본적인 구성요소로써 이것들로부터 모든 자연수가 구성된다는 사실을 알려준다. 소수는 화학의 원소 또는 물리학의 소립자와 같다.

 

소수에 대한 가장 기본적 질문은 소수가 얼마나 자주 나타나는가 하는 것이다. 자연수의 열을 따라 나아갈수록 소수의 분포는 점점 더 희박해진다. 그러나 소수는 사라지지 않는다. 유클리드는 세련된 수학적 추론의 본보기로 남아있는 논법을 이용해서 이 사실을 증명하였다. P₁ = 2, P₂ = 3, P₃ = 5, ……등 크기의 순서대로 나열된 소수의 목록을 상상하자. 목표는 이 목록이 한없이 계속되어 P_n째의 단계에 있더라도 이 목록에는 P_n보다 큰 다른 소수가 존재한다는 사실을 증명하는 것이다. P₁부터 P_n까지의 모든 소수를 곱한 값에 1을 더하여 얻는 수를 주목한다.

N= P₁ P₂ P₃ P₄ …… P_n + 1

분명히 N은 P_n보다 크다. 만약에 N이 소수라면 P_n보다 큰 소수가 존재하는 것이 된다. 그런데 N이 소수가 아니라면 이 수는 어떤 소수 P로 나누어 떨어져야만 한다. 그러나 N은 P_1, P_2, P_3,……, P_n 등 어떠한 소수로 나누더라도 1이 남으므로 N은 소수가 분명하다. 이로써 P_n보다 큰 소수가 존재하는 결과가 증명되는 것이다. 따라서 모든 경우에 P_n보다 큰 소수가 존재하고, 소수의 목록은 한없이 계속된다고 결론지을 수 있다. 그러나 이러한 수가 소수가 아닌 경우도 있다.

N₆ = 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031 = 59×509이 그 예이다.

어느 누구도 N= P₁ P₂ P₃ P₄ …… P_n + 1 꼴의 수 가운데에 소수나 합성수가 무수하게 많이 있는지를 모르고 있다.

 

소수에 관한  유명한 미해결의 문제의 하나로 ‘골드바흐의 추측’이 있다. 골드바흐(Christian Goldbach)는 1742년 오일러(Leonhard Euler)에게 보낸 편지에서 2보다 큰 모든 짝수가 두 소수의 합이라고 추측하였다. 이 추측은 4×10¹¹ 까지의 모든 짝수에 대하여 참이라는 사실이 컴퓨터의 조사로 입증되었지만 현재까지 완전하게 증명도 부정도 되고 있지 않다.

 

  (3) 소수판정법

어떤 수 n의 소수여부를 확인하는 확실한 방법은 ‘예비 나눗셈’(trial division)이다. 곧 n이 나누어 떨어질 때까지 2, 3, 5, 7,……로 계속하여 나누어 보아, 그 수가 n의 제곱근에 이르도록 n이 나누어 떨어지지 않으면 n은 소수이다. 그러나 이 방법은 n이 커질수록 적용하기 어려워진다.

 

큰 수의 소수 여부를 판정하는 가장 훌륭한 방법은 1980년에 애들먼(Leonhard M. Adleman), 포머런스(Carl Pomerance),루멜리(R. S. Rumely),코헨(H. Cohen), 렌스트라(H. W. LENSTRA. JR) 등의 수학자가 개발한 ‘APRCL판정법’이다. 이 판정법의 핵심적 개념은 페르마(Pierre de Fermat)가 발견하였다. 어떤 수 P가 소수이면 P보다 작은 임의의 수 a에 대하여 a^p-1-1은 P로 나누어 떨어진다. 예를 들어 P = 7과 a = 2를 택하면 a^p-1 - 1 = 2⁶ - 1 = 64 - 1 = 63으로, 63은 7로 나누어 떨어진다. 그러나 여기에는 예외가 존재하여 페르마의 성질을 가진 합성수인 ‘의소수(pseudoprime)’가 있다. 그 가장 작은 수가 341이다. a를 2 대신에 3 또는 5로 사용하더라도 소수 판정의 문제를 방해하는 의소수가 등장한다.

 

이러한 판정법을 사용할 때 수 2^n-1을 실제로 계산할 필요는 없다. 단지 2^n-1을 n 으로 나누었을 때의 배수는 무시하고 나머지만을 계산하면 충분하다. A를 B로 나누었을 때의 나머지를 표기하는 표준적 방법은 A mod  B이다. 예를 들어 5 mod 2 = 1이다. 이 방법을 이용하여 수 61의 소수여부를 판정하여 본다.

(2⁶⁰ - 1) mod 61

이 값이 0이 아니면 61은 소수가 아니며, 이 값이 0이면 61은 소수이거나 의소수이다. 2⁶ = 64이므로 2⁶ mod 61 = 3이다. 2³⁰ = (2⁶)⁵이므로 2³⁰ mod 61 = 3⁵ mod 61 = 243 mod 61 = 60이다. 다시 2⁶⁰ = (2³⁰)²이므로 2⁶⁰ mod 61 = 60² mod 61 = 3600 mod 61= 1이다. 따라서

(2⁶⁰ - 1) mod 61=0

그러므로 수 61은 소수이거나 의소수라는 것이 밝혀진다.

 

APRCL판정법은 의소수에 속지 않기 위하여 페르마의 판정법을 수정하여 사용하는데 여기에 대하여는 대단히 심오한 수학이 요구된다.

 

  (4) 메르센 소수

17세기 프랑스의  수도승 메르센(Marin Meresenne)은 1644년에 출판된 ‘물리수학론(Cogitata Physica-Mathematica)’의 머리말에서  M_n = 2ⁿ - 1꼴의 수가 n = 2, 3, 5, 7, 13, 17, 31, 67, 127, 257에 대하여 소수이고, 257보다 작은 다른 모든 n에 대하여는 합성수라고 하였다. 이러한 수를 ‘메르센 수’라고 한다. 비록 이 주장에 부분적으로 실수가 있기는 하지만 메르센 수는 매우 거대한 소수를 얻는 훌륭한 방법을 제공한다. 소수인 메르센 수를 ‘메르센 소수’라고 한다. 초등대수학을 이용하면 n 자체가 소수가 아니면 M_n도 소수가 아니라는 사실을 알 수 있다. 보다 더 큰 메르센 소수를 찾으려는 노력은 컴퓨터의 도움을 얻어서 계속되고 있다. 그리고 컴퓨터의 성능을 시험하는 데에 메르센 소수 사냥 프로그램이 사용된다.

 

메르센 수의 소수 여부를 판정하는 데에 이용되는 방법은 매우 간단하다. 이 방법은 1876년에 기본적 개념을 발견한 루카스(Eduorard Lucas)와 레머(Derrick Lehmer)의 이름을 따서 루카스 - 레머 판정법으로 불린다. 메르센 수 M_n의  소수여부를 판정하기 위하여 다음의 법칙에 따라 U(0), U(1), ……, U(n - 2)를 계산한다.

U(0) = 4

U(K+1) = [U(K)² - 2] mod = M_n

마지막으로 U(n - 2) = 0이면 M_n은 소수이고,  U(n - 2) ≠ 0이면 M_n 은 소수가 아니다. 예를 들어 M₅의 소수 여부를 알아 본다.

U(0) = 4

U(1) = (4² - 2) mod 31 = 14 mod 31 = 14

U(2) = (14² - 2) mod 31 = 194 mod 31 = 8

U(3) = (8² - 2) mod 31 = 62 mod 31 = 0

그러므로 M₅는 틀림 없이 소수이다.

 

  (5) 소인수 분해

함성수로 밝혀진 수의 인수를 어떻게 찾을 수 있을까? 예비 나눗셈과 같은 시행착오방법은 이용하기 어렵다. 페르마의 소인수 분해방법이 있다.

n = uv라고 하고,

,

로 놓는다.

0 ≤ y < x ≤ n이고, u = x + y, v = x - y 이므로

n = x² - y² = (x + y)(x - y)

y² = x² - n으로 쓸 수 있다.

n = (x + y)(x - y)에 해당하는 x와 y를 찾기 위하여 n의 제곱근보다 크거나 같은 가장 작은 수 k로부터 출발하여 k + 1, k + 2,……의 값을 차례로 시도하면서 x² - n 이 완전 제곱인지를 살피는 것이다.

 

페르마의 방법을 쓸모 있게 변형시킨 방법은 n = x² - y²을 만족시키는 x와 y를 찾지 않고, 그 대신에 x² - y² 이 n으로 나누어 떨어지는 x와 y를 찾는다. 이러한 수들이 존재한다면 x + y와 x - y가  모두 n의 인수를 가질 가능성이 매우 높다. 예를 들면 10² - 4²은 21로 나누어 떨어지고, 두 약수 10 + 4 = 14 = 2×7과 10 - 4 = 6 = 2×3으로부터 소인수분해 21 = 7×3을 얻는다.

1920년대에 크라이치크(Kraitchik)는 x와 y의 적절한 값을 작은 수들을 이어 맞추어 얻을 수 있다고 주장하였다. 에를 들어 111을 인수 분해할 때 조사를 통하여 다음을 알 수 있다.

11² mod 111 = 121 mod 111 = 10 = 2×5

14² mod 111 = 196 mod 111 = 85 = 5×17

16² mod 111 = 256 mod 111 = 34 = 2×17

이 사실은 (11×14×16)² - (2×5×17)² = 2,634×2,294가 111로 나누어 떨어짐을 의미한다. 그러므로 111의 인수를 고대 그리스 시대부터 유클리드 알고리즘으로 알려진 공약수를 찾는 간단한 방법을 이용해서 찾을 수 있다.

2294 mod 111 = 74

111 mod 74 = 37

74 mod 37 = 0

그러므로 37은 111과 2,294의 공약수이고, 마찬가지로 3은 111과 2,634의 공약수이다. 따라서 111 = 3×37이다.

 

  (6) 페르마 수

n째 ‘페르마 수’는 2에 2n을 거듭 제곱한 다음에 1을 더하여 얻는다. 즉

이다. 이러한 수에 대한 관심은 1640년에 페르마가 메르센에게 쓴 편지에서 주장 한 내용 때문에 발생하였다. 페르마는 F₀부터 F₄까지의 각수가 소수라는 사실을 지적한 뒤에 F_n 꼴의 수가 모두 소수라고 주장하였다. 그러나 이 주장은 옳지 않다. 오일러는 F₅ = 4,294,967,297 이 소수가 아님을 밝혔다.  현재까지 5에서 23까지의 n의 모든 값에 대하여 F_n은 합성수라는 사실이 밝혀졌으며, 4보다 큰 n 의 모든 값에 대하여 합성수라고 추측되고 있다.

 

페르마 수는 효과적으로 소수 여부를 판정할 수 있는 또 다른 예를 제공하는데, 유명한 ’프로스(Proth)의 정리’를 이용하는 방법이 있다.  페르마 수 F_n 이소수이기 위한 필요충분조건은

mod F_n = -1

이다. 최근에는 합성수로 이루어진 페르마 수의 소인수 분해에 있어서 여러 사람에 의하여 중요한 발전이 이루어지고 있다,

 

  (7) 놀라운 수학적 발상

19세의 가우스는 정n각형을 자와 컴퍼스만으로 작도할 수 있는 필요충분조건은 어떤 수 k에 대하여 n = 2^k이거나 n = 2^kp₁p₂……p_r이라는 사실을 증명하였다. 여기의 p₁p₂……p_r은 서로 다른 페르마 소수이다. 특히 임의의 페르마 소수 p에 대하여 정p각형을 작도할 수 있다. F₂ = 17도 페르마 소수이므로  가우스의 결과는 정17각형을 자와 컴퍼스로 작도할 수 있음을 보여준다. 가우스는 이 발견을 대단히 자랑스럽게 생각하여 자신의 비석에 정17각형을 새겨달라고 하였다.

 

  (8) 완전수

피타고라스학파는 수 6과 같이 자신을 제외한 약수의 합이 자신과 같은 수를 ‘완전수’라고 불렀다.

6 = 1+2+3

 

그리스 수학자 니코마코스(Nicomachus)는 당시에 알려진 4개의 완전수 6, 28, 496, 8,128을 나열하였는데, 이에 의거하여 n째 완전수는 n자리의 수이고, 교대로 6과 8로 끝난다는 추측이 등장하였다. 그러나 이 두 가지의 추측은 옳지 않다. 다섯 자리의 완전수는 없으며, 다섯 째 완전수 33,550,336과 여섯째 완전수 8,589,869,056은 모두 6으로 끝난다. 하지만 짝수인 완전 수는 모두 6또는 8로 끝난다. 유클리드는 원론 제Ⅸ권에서 2ⁿ-1이 소수이면 2^n-1(2ⁿ-1)은 완전수라는 사실을 기원 전 300∼350년경에 증명하였다. 2천 년 뒤에 오일러가 짝수인 모든 완전수가 이런 꼴임을 보임으로써 메르센 소수와 완전수 사이의 밀접한 관계가 입증되었다. 홀수인 완전수는 발견되지 않았으며, 모든 완전 수는 필영적으로 짝수일 것이라는 추측이 있다. 만약에 홀수인 완전수가 존재한다면, 그 수는 반드시 10¹⁰⁰보다 크고 적어도 11개의 서로 다른 소인수를 가져야 한다.

 

모든 완전수는 ‘삼각수’로서 수 n에 대하여 n(n + 1)/2의 꼴이다. 6 이외의 다른 완전수의 각 자리의 수를 더하면 9의 배수보다 1만큼 많으며, 따라서 완전수의 ‘자릿수 근(digital root)’은 1이다. 또 모든 완전수는 에와 같이 연속한 홀수들의 세제곱의 합이다.

28 = 1³ + 3³

496 = 1³+3³+5³+ 7³

 

그리고 완전수 n의 모든 약수의 역수의 합은 언제나 2이다. 예를 들면 6의 약수는 1, 2, 3, 6인데 ,그 역수의 합은 다음과 같다.

 

  (9) 암호

암호체계는 설계와 보안유지의 어려움 때문에 항상 두 가지 요소 즉 암호화과정과 ‘열쇠(key)’로 구성된다. 암호화 프로그램은 선택된 열쇠에 근거하여 통신문을 암호화하며, 이에 따라 열쇠를 알고 있어야만 암호문을 해독할 수 있다. 전형적인 ‘열쇠체계’에서 전송자와 수신자는 나중에 통신문을 전송하는데에 사용할 비밀열쇠에 대하여 미리 합의한다. 이러한 암호체계의 예로 미국에서 설계한 DES(Data Encryption Standard)가 있는데 이것은 2진법의 표현으로 56자리의 수를 열쇠로 사용한다. 그러나 이 체계는 아직 만나지 못한 개인 사이 특히 국제적 은행업무나 교역의 통신에는 적절하지 못하다.

 

1975년에 디피(Whitfield Diffie)와 헬만(Martin Hellman)은 ‘공개열쇠암호체계(public key cryptography)'를 제안하였는데, 이 체계의 암호화기법은 하나는 암호화에 사용되고 다른 하나는 해독에 사용되는 두 개의 열쇠를 필요로 한다. 이에 따라 리베스트(Ronald Rivest)와 샤미르(Adi Shamir) 및 애들먼은 그들의 머리글자를 딴 ‘RSA체계’를 설계하였다. 이 RSA방법에 사용되는 암호해독열쇠는 사용자가 선택한 두 개의 거대한 소수로 이루어진다. 통신문의 암호화는 거대한 두 소수의 곱셈에 해당하고 쉽다. 그러나 통신문의 해독은  반대방향인 소인수 분해에 해당되고 어렵다. 확실히 이러한 체게의 안전은 소인수 분해의 어려움에 의존한다.

 

수학자 포머런스는 ‘이차 체 방법(Quardatic Sieve Method)’이라는 새로운 소인수 분해방법을 개발하여 컴퓨터에서 구현되도록 하였다. 포머런스의 이차 체는 크라이치크의 ‘인수 기저(factor base)’인 x의 후보 값들을 계산하는 효과적인 방법을 제공한다. 이 방법의 변형으로 데이비스와 몽고메리(Peter Montgomery)가 개발한 다중 다항(Multiple Polinomial) 이차 체 방법이 있는데 이것은 포머런스의 원래의 방법에 등장하는 x² - n 대신에 일반적인 이차 다항식인 (ax + b)² - n을 이용한다.  이 새로운 방법을 이용하면 여러 개의 서로 다른 이차 체를 독립적으로 시행할 수 있고, 이에 따라 계산을 분리해서 여러 대의 서로 다른 컴퓨터에서 계산을 시행할 수 있다. 다중 다항 이차 체와 인터넷의 결합이 129자리의 수로 이루어진 암호의 소인수 분해를 가능하게 하였다.

 

(*주 1) ‘골드바흐의 추측’을 소재로 한 같은 이름의 소설이 있다.

(*주 2) 현재 제42번째의 메르센 소수인 25964951까지 밝혀졌다고 한다.

[출처] 경문수학산책 2 수학 : 새로운 황금시대 (1)|작성자 얼쑤