Hacker News 2026.04.19 22

마이클 라빈 별세: 무작위 알고리즘과 암호학의 거장이 남긴 것

컴퓨터 과학의 한 시대가 저물다

튜링상 수상자이자 현대 이론 컴퓨터 과학의 뼈대를 세운 마이클 라빈(Michael O. Rabin) 교수가 세상을 떠났습니다. 1931년 독일에서 태어나 이스라엘에서 자란 그는, 스승 알론조 처치의 지도 아래 프린스턴에서 박사학위를 받고 하버드와 히브리대학교에서 평생 연구를 이어온 분이에요. 1976년엔 "비결정론적 유한 오토마타(Nondeterministic Automata)"에 대한 공동 연구로 대니 스콧과 함께 튜링상을 받았는데, 튜링상이 뭐냐면 "컴퓨터 과학계의 노벨상"이라 불리는 최고의 권위 있는 상이에요.

라빈의 이름은 컴퓨터 공학을 공부한 사람이라면 어디선가 한 번쯤 만나게 돼요. 알고리즘 수업, 암호학, 오토마타 이론, 문자열 검색까지 그의 손이 닿지 않은 분야를 찾기 어려울 정도예요.

비결정론의 아이디어: NFA와 DFA

라빈이 스콧과 함께 제안한 비결정론적 유한 오토마타(NFA) 개념은 지금도 컴파일러와 정규표현식(regex) 엔진의 심장부에 들어 있어요. 이게 뭐냐면, 상태 기계가 한 입력에 대해 "여러 경로를 동시에 탐색할 수 있다"고 가정하는 모델이에요. 현실의 기계는 하나씩 처리할 수밖에 없지만, 이 "가상의 동시 탐색" 개념은 알고리즘을 훨씬 간결하게 표현할 수 있게 해주죠. NFA는 항상 결정론적 오토마타(DFA)로 변환 가능하다는 그의 증명은, 오늘날 우리가 쓰는 grep, awk, 자바스크립트의 정규식 엔진이 돌아가는 근거가 돼요.

무작위 알고리즘이라는 혁명

라빈이 남긴 가장 큰 유산 중 하나는 무작위 알고리즘(Randomized Algorithm)이에요. 당시까지 알고리즘은 "정해진 입력에 정해진 출력을 낸다"는 결정론이 당연했는데, 라빈은 "동전을 던져서 답을 추측하고, 틀릴 확률을 천문학적으로 낮추자"는 발상을 학계에 확산시켰어요.

대표 작품이 밀러-라빈 소수 판정법(Miller-Rabin primality test)이에요. 어떤 수 n이 소수인지 확인하는 건 암호학의 기본인데, 수백 자리짜리 큰 수를 정직하게 나눠보려면 시간이 엄청 걸려요. 밀러-라빈은 무작위로 "증인(witness)" 몇 개를 뽑아 테스트해서, 오답 확률을 $4^{-k}$ 수준으로 떨어뜨려요. $k$를 40 정도만 해도 틀릴 확률이 우주의 원자 수보다 적어져요. RSA 키를 생성할 때 내부적으로 이 알고리즘이 돌아가고 있어요. 여러분이 HTTPS로 은행 사이트에 접속할 때마다 라빈의 아이디어가 작동하는 셈이죠.

또 하나는 라빈-카프 문자열 검색(Rabin-Karp algorithm). 긴 문서에서 특정 패턴을 찾을 때, 문자열을 숫자 해시로 바꿔놓고 롤링 해시(rolling hash, 한 칸씩 밀면서 해시값을 갱신하는 기법)로 빠르게 비교하는 알고리즘이에요. 표절 검사, DNA 서열 매칭, 웹 크롤러의 중복 페이지 탐지 같은 곳에서 지금도 쓰이고 있어요.

암호학에 새긴 이름들

라빈은 암호학 쪽에도 큰 족적을 남겼어요. 라빈 암호시스템은 RSA와 비슷한 시기에 제안된 공개키 암호인데, "해독 난이도가 큰 수의 소인수분해 난이도와 동등하다"는 수학적 증명이 붙은 첫 시스템 중 하나예요. 또 하이퍼플레인(Hyper Encryption)이라는 개념으로 "양자컴퓨터가 나와도 안전한 암호"를 일찍이 고민했고, 오블리비어스 트랜스퍼(Oblivious Transfer)라는 프리미티브도 제안했는데요. 이건 뭐냐면, 송신자는 여러 메시지를 보내는데 수신자가 그중 하나만 받을 수 있고 송신자는 어느 걸 받았는지 모르게 하는 프로토콜이에요. 오늘날 다자간 안전 연산(MPC)과 영지식 증명의 기본 블록이 되죠.

업계 맥락: 그의 아이디어는 어디까지 퍼졌는가

블록체인, 프라이버시 보호 머신러닝, 연합학습(Federated Learning), 동형암호(Homomorphic Encryption) 같은 최신 키워드들이 전부 라빈이 깔아놓은 기초 위에 서 있어요. 무작위성을 계산의 자원으로 활용한다는 아이디어는 현대 AI의 확률적 경사 하강법(SGD)이나 몬테카를로 트리 탐색(MCTS)에도 연결돼요. 그가 제자로 길러낸 학자들 중엔 실릭 밸리 인프라를 떠받치는 이들이 많고, 대표 제자 중 한 명이 지금 알고리즘 교과서의 대가로 불리는 개발자들이에요.

한국 개발자에게 주는 의미

CS 전공자라면 알고리즘 강의에서 반드시 한 번쯤 그의 이름을 만나게 돼요. 그런데 현업 개발자 입장에서도 "무작위성을 두려워하지 말자"는 메시지는 여전히 유효해요. 완벽한 결정론을 고집하다 보면 풀리지 않던 문제가, 확률적 접근으로 전환하는 순간 현실적인 시간에 풀리거든요. 블룸 필터, HyperLogLog, 스케치 알고리즘 같은 실무 도구들이 다 이 철학의 후예예요.

RSA 라이브러리나 정규표현식 엔진을 쓸 때 한 번쯤, "이 코드 뒤엔 1970년대에 누군가 제안한 아이디어가 있다"는 걸 떠올려보시면 좋겠어요.