---
title: "튜링상 수상자 마이클 라빈 별세 — Miller-Rabin·Rabin-Karp의 그 라빈"
published: 2026-04-15T18:07:46.000Z
canonical: https://jeff.news/article/1795
---
# 튜링상 수상자 마이클 라빈 별세 — Miller-Rabin·Rabin-Karp의 그 라빈

비결정적 유한 오토마타(NFA)와 Miller-Rabin 소수 판정, Rabin-Karp 문자열 검색을 만든 컴퓨터 과학자 Michael O. Rabin이 4월 14일 향년 94세로 별세했다. 1976년 Dana Scott과 함께 ACM 튜링상을 공동 수상했으며, 무작위 알고리즘과 암호학의 토대를 다진 인물이다.

> [!IMPORTANT]
> 1976년 튜링상 공동 수상자, 비결정적 유한 오토마타(NFA)·Miller-Rabin 소수 판정·Rabin-Karp 문자열 검색의 그 라빈임. 학부 알고리즘 수업에서 한 학기에 이름이 세 번씩 나오는 인물이 떠남.

- 컴퓨터 과학자 Michael O. Rabin이 4월 14일 향년 94세로 별세
  - 1931년 폴란드(당시 독일령) 브레슬라우 출생, 1935년 가족과 함께 팔레스타인으로 이주
  - 헤브루대 석사, 펜실베이니아대 박사 과정을 거쳐 1956년 프린스턴에서 박사학위 취득
  - 29세에 헤브루대 수학연구소장, 33세에 정교수, 1981년부터 하버드 Gordon McKay 컴퓨터과학 석좌

### 비결정적 오토마타 — 튜링상의 그 논문

- 1959년 IBM 여름 연구에서 Dana Scott과 함께 「Finite Automata and Their Decision Problems」 작성
  - 비결정적 유한 오토마타(NFA) 개념을 처음 도입한 논문
  - "여러 상태를 동시에 가능성으로 들고 다닐 수 있는 기계"라는 발상이 후일 P/NP 정의의 토대가 됨
  - 두 사람은 이 업적으로 1976년 ACM 튜링상 공동 수상

- 다음 해 같은 별장에서 John McCarthy가 던진 "스파이·가드·패스워드" 퍼즐을 풀다가 「Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets」 발표
  - 계산복잡도 이론의 시초로 평가받음
  - 1966년에는 polynomial time(다항 시간) 개념을 별도로 정립 (Cobham, Edmonds도 같은 시기 독자적으로 제안)

### 무작위 알고리즘의 시대를 연 사람

- 1960년 Bell Labs 방문 중 동전 던지기로 상태 전이를 결정하는 확률적 오토마타(probabilistic automata) 도입
  - 어떤 정규 언어는 결정적 오토마타로 표현하면 상태 수가 폭증하지만, 확률을 도입하면 지수적으로 줄어듦을 보임
  - "무작위성이 계산 자원을 절약할 수 있다"는 무작위 알고리즘 패러다임의 원형

- 1975년 MIT 방문 중 Miller-Rabin 소수 판정법 발명
  - Gary Miller의 결정적 알고리즘은 일반화 리만 가설(GRH)이 참이라고 가정해야 작동했음
  - 라빈은 가설을 떼어내고 무작위 알고리즘으로 재설계 — 오류 확률이 미세하지만 실용적으로 무시 가능
  - 오늘날 RSA 등 공개키 암호의 키 생성에서 사실상 표준 — 큰 소수를 빠르게 골라내는 핵심
  - 2003년 Miller, Rabin, Solovay, Strassen이 이 업적으로 Paris Kanellakis Award 공동 수상

### 암호학과 문자열 검색의 토대

- 1978년 Rabin signature 알고리즘 — 보안성이 정수 인수분해 난해성과 동등함이 수학적으로 증명된 최초의 비대칭 암호 시스템

- 1981년 oblivious transfer(OT)의 약한 변형 재발명
  - 송신자가 메시지를 보내면 수신자는 0과 1 사이 어떤 확률로만 그 메시지를 알게 되고, 송신자는 수신 성공 여부를 알 수 없음
  - 오늘날 다자간 안전 계산(MPC), 영지식 증명, 프라이버시 보존 ML의 빌딩블록

- 1987년 Richard Karp와 함께 Rabin-Karp 문자열 검색 알고리즘 발표
  - rolling hash 기법으로 유명 — 부분 문자열 해시를 한 칸씩 밀어가며 O(1)로 갱신
  - 다중 패턴 검색, 표절 탐지에 여전히 현역

- 1969년 무한 트리 오토마타 도입, n-successor 단항 2차 이론(S2S)의 결정 가능성 증명
  - 증명 과정에서 parity game의 결정성을 암묵적으로 보임 (Borel hierarchy 3단계)

### 수상과 유산

- 1995년 이스라엘 상(컴퓨터과학), 2010년 Tel Aviv대 Dan David Prize(Leonard Kleinrock·Gordon Moore와 공동), 2017년 하버드 명예박사
- 미국 국립과학아카데미·미국 학술원·프랑스 과학아카데미·왕립학회 외국인 회원
- 딸 Tal Rabin도 저명한 암호학자 (IBM Research 출신, 펜실베이니아대 교수) — 분산 암호 분야의 대가

---

## 기술 맥락

학부 알고리즘·이산수학 수업에서 한 학기 안에 그의 이름이 최소 세 번은 나와요. NFA, Miller-Rabin, Rabin-Karp. 이게 다 한 사람 머리에서 나왔다는 게 새삼 놀랍죠.

비결정적 오토마타가 단순히 "여러 상태를 동시에 가질 수 있는 기계"인 게 아니에요. 진짜 핵심은 "검증은 빠른데 찾기는 어려운 문제"라는 NP 클래스의 개념적 토대를 만들었다는 거예요. 라빈과 Scott이 1959년 이걸 깔지 않았다면 P vs NP 문제 자체가 다른 모습이었을 거예요.

확률적 알고리즘 분야도 마찬가지인데요. 결정적으로 풀면 너무 비싼데 "가끔 틀려도 되는" 무작위성을 도입하면 빨라지는 문제들이 있다는 발상 — 이게 1960년 Bell Labs에서 라빈이 처음 보여준 거거든요. Miller-Rabin은 그 발상의 가장 실용적인 결실이고, 우리가 HTTPS로 안전하게 통신할 수 있는 이유 중 하나예요. 브라우저가 RSA 키 만들 때 뒤에서 돌아가는 게 결국 이 알고리즘이에요.

oblivious transfer는 1981년 당시엔 좀 이상한 개념처럼 보였는데, 지금은 federated learning, 프라이버시 보존 ML, 블록체인의 영지식 증명 같은 영역에서 다시 핵심 빌딩블록으로 부활하고 있어요. 라빈이 깔아놓은 토대 위에서 40년 뒤에야 본격 응용이 터지는 셈이에요.

Rabin-Karp도 마찬가지예요. KMP보다 평균 성능이 좋다고 단정하긴 어렵지만, 다중 패턴을 동시에 찾을 때 rolling hash가 빛을 발해요. 깃의 일부 diff 알고리즘이나 표절 탐지기 같은 데서 여전히 쓰이거든요.

## 핵심 포인트

- 1976년 Dana Scott과 ACM 튜링상 공동 수상 — 비결정적 유한 오토마타(NFA) 도입 공로
- Miller-Rabin 소수 판정법 — 일반화 리만 가설 가정을 떼어낸 randomized 알고리즘, RSA 키 생성에 표준으로 쓰임
- Rabin-Karp 문자열 검색 — rolling hash로 유명, 다중 패턴 검색에 여전히 현역
- Rabin signature — 정수 인수분해 난해성과 동등함이 증명된 최초의 비대칭 암호 시스템
- oblivious transfer 재발명 — 오늘날 MPC, 영지식 증명, 프라이버시 보존 ML의 빌딩블록

## 인사이트

한 사람의 이름이 학부 알고리즘 한 학기에 세 번 나오는 경우는 흔치 않다. 라빈은 결정성·확률성·암호의 세 갈래에서 모두 토대를 깔았고, 1981년 OT처럼 40년 뒤 영지식 증명 시대에야 빛을 발하는 작업도 있다. 이론과 실용을 동시에 정조준한 드문 경력이다.