마이클 O. 라빈: 컴퓨터를 우연과 친숙하게 만든 사람
열 살이나 열한 살 무렵, 영국 위임통치령 팔레스타인에서 마이클 라빈은 자신보다 나이가 많은 학생들도 풀지 못한 기하학 문제를 해결했다. 이는 그가 남은 세기 동안 다른 모든 사람들이 절대적인 확실성을 요구한다고 가정했던 문제들에 대해 우아하고 예상치 못한 경로를 찾아내는 데 보낼 지성의 초기 징후였다. 오토마타 이론, 암호학, 정수론 전반에 걸쳐 반복된 라빈의 특징적인 움직임은 기계에 추측이나 동전 던지기를 허용하는 것이 신뢰성을 떨어뜨리는 것이 아니라 오히려 더 강력하게 만들 수 있다는 점을 알아차린 것이었다. 이 아이디어는 그가 처음 제안했을 때 거의 이단으로 간주되었다.
브레슬라우에서 팔레스타인의 랍비 가정으로
라빈은 1931년 9월 1일 당시 독일령이었고 현재는 폴란드 브로츠와프인 브레슬라우에서 태어났다. 랍비였던 그의 아버지는 유럽에서 닥쳐올 최악의 사태를 앞두고 1935년 가족을 팔레스타인으로 이주시켰다. 그는 하이파의 히브리 리알리 학교에 다녔으며, 나중에 테크니온 교수가 된 수학자 엘리샤 네타냐후 밑에서 공부했고, 10대 시절 이미 고급 수학 세미나를 소화하고 있었다. 1953년 예루살렘 히브리 대학교에서 수학 석사 학위를 받았으며, 에미 뇌터가 원래 제기했던 미해결 문제를 해결하는 논문을 썼다. 그 후 미국으로 건너가 프린스턴 대학교에서 박사 학위를 받았고, 1957년 논리학자 알론조 처치의 지도하에 학위를 마쳤다.
추측할 수 있는 기계
라빈의 가장 중요한 초기 논문은 다나 스콧과 공동 집필하여 1959년에 발표한 "유한 오토마타와 그 결정 문제"로, 비결정적 유한 오토마타라는 개념을 도입했다. 이는 입력값을 만났을 때 효과적으로 자신의 여러 복사본으로 분기하여 여러 가능한 계산 경로를 동시에 추적할 수 있는 이론적 기계이다. 이 논문은 이러한 비결정적 기계가 훨씬 더 강력해 보임에도 불구하고 계산 능력 면에서 일반적인 결정적 기계와 정확히 동일하다는 것을 증명했으며, 이는 컴퓨터 과학이 계산 자체를 생각하는 방식을 재구성한 기초적인 결과였다. 컴퓨터 학회(ACM)는 라빈이 30세가 되기 전에 쓴 이 이론에 대해 1976년 튜링상을 수여했다. 이는 컴퓨터 과학의 최고 영예이다.
우연에 신뢰성을 가르치다
라빈은 계산에 의도적으로 무작위성을 주입하는 것이 신뢰성을 떨어뜨리지 않으면서 더 빠르거나 간단하게 만들 수 있다는 관련 있고 더 낯선 아이디어로 계속 돌아왔다. 1960년경 벨 연구소에서 그는 동전 던지기를 사용하여 상태 전이를 결정하는 확률적 오토마타를 도입하여, 결정적 기계보다 지수적으로 적은 상태로 특정 언어를 표현할 수 있음을 보여주었다. 이 직관은 1975년 밀러-라빈 소수 판별법으로 성숙했다. 이는 게리 밀러의 이전 결정론적 연구를 바탕으로 한 무작위 알고리즘으로, 거대한 숫자가 소수인지 판별하는 데 사용되며 현대 인터넷에서 사용되는 암호 시스템을 뒷받침할 만큼 빠르고 신뢰할 수 있다. 라빈의 버전은 밀러가 의존했던 증명되지 않은 일반 리만 가설에 대한 의존성을 제거한 것으로 유명하다. 2003년 카넬라키스상은 이 연구 분야에 대한 밀러, 라빈, 로버트 솔로베이, 폴커 슈트라센의 공동 기여를 인정했다.
어려운 수학으로 구축된 자물쇠
라빈의 암호학은 소수 판별을 넘어섰다. 1978년 그는 라빈 암호 시스템을 고안했는데, 이는 보안이 큰 정수의 인수분해 난이도와 수학적으로 동등함이 증명될 수 있는 최초의 비대칭 암호 스킴으로 주목받았다. 이는 당시 대부분의 암호 시스템이 주장할 수 있었던 것보다 더 강력한 보증이었다. 1981년 그는 '오블리비어스 전송(Oblivious Transfer)'을 공식화했는데, 이는 송신자가 수신자가 실제로 정보를 얻었는지 알 수 없도록 정보를 보낼 수 있는 암호 프로토콜로, 안전한 다자간 계산의 구성 요소가 되었다. 1987년 리처드 카프와 함께 라빈-카프 문자열 검색 알고리즘을 공동 개발했는데, 이는 롤링 해시 기술로 대규모 텍스트 내에서 패턴을 찾는 효율성 때문에 오늘날에도 학부 알고리즘 과정에서 가르치고 있다.
두 나라에 걸친 경력
라빈의 학문적 삶은 이스라엘과 미국 사이에서 병행되었다. 예루살렘 히브리 대학교에서 30대 초반에 수석 강사에서 정교수로 승진했고, 수학 연구소장을 역임했으며, 1972년부터 1975년까지 대학 총장을 지냈다. 미국에서는 1981년부터 하버드 대학교에서 고든 맥케이 교수직, 이어 토머스 J. 왓슨 시니어 교수직을 역임했으며, MIT, 버클리, 컬럼비아 대학교에서 객원 교수를 지냈다. 그는 미국 국립과학원, 미국 예술과학 아카데미, 미국 철학 학회, 프랑스 과학 아카데미, 왕립 학회 회원으로 선출되었으며, 1995년 이스라엘 상, 2010년 댄 데이비드 상을 수상했고, IEEE 찰스 배비지 상과 다익스트라 상을 포함한 영예를 안았다.
마이클이 천재라고 불리는 이유
라빈이 천재로 간주되는 이유는 50년 경력 전반에 걸쳐 인식 가능한 특징이 있기 때문이다. 확실성이 필요하다고 가정했던 문제가 의도적으로 무작위성이나 비결정성을 도입함으로써 더 빠르게 해결되거나 더 강력해질 수 있음을 반복적으로 식별해낸 것이다. 이 통찰력은 처음에는 동시대 사람들에게 범주 오류처럼 보였는데, 무작위성은 신뢰할 수 있는 계산의 자원이 아니라 적으로 널리 취급되었기 때문이다. 오토마타 이론, 소수 판별, 암호 프로토콜 설계에 독립적으로 적용된 이 통찰력은 각각 하나만으로도 상당한 경력을 표시할 수 있는 결과를 낳았다. 여러 개를 만들어낸 것이 바로 튜링상 위원회와 이후의 카넬라키스상, 배비지상, 다익스트라상이 명시적으로 기린 내용이다. 기록상 이에 대한 심각한 반론은 거의 없다. 일부 튜링상 수상자들의 명성이 단 하나의 논문에 기반을 둔 것과 달리, 라빈의 명성은 수십 년에 걸쳐 독립적으로 검증되고 여전히 사용되는 결과물 위에 구축되었다. 밀러-라빈 테스트는 오늘날 교과서뿐만 아니라 암호 라이브러리 내부에서 실행되고 있다. 유일한 주의 사항이 있다면 스콧과 함께 쓴 가장 유명한 단일 논문이 진정한 파트너십에서 나왔다는 사실인데, 이는 이 분야에서 가장 날카로운 개인적 통찰력조차도 보통 고독한 천재가 아니라 협력을 통해 도달했다는 점을 상기시켜 준다.
유산
라빈은 2026년 4월 14일 94세의 나이로 세상을 떠났으며, 말년까지 하버드 대학교와 히브리 대학교 모두에서 명예 교수로 재직했다. 그의 딸 탈 라빈 역시 저명한 암호학자가 되어 무작위성과 비밀에 대한 가족의 특별한 매력을 새로운 세대로 이어갔다. 그의 이름을 딴 알고리즘(밀러-라빈, 라빈-카프, 라빈 암호 시스템)은 컴퓨터가 숫자를 테스트하거나, 문자열을 검색하거나, 비밀을 유지해야 하는 곳 어디에서나 여전히 활발하게 일상적으로 사용되고 있다. 이는 기초 이론 컴퓨터 과학이 작성된 지 수십 년이 지난 후에도 여전히 가시적인 일상 업무를 수행하고 있는 드문 사례이다.
