튜링상 수상자 마이클 라빈 별세 — 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 알고리즘이나 표절 탐지기 같은 데서 여전히 쓰이거든요.