미하엘 라빈
미하엘 라빈
מִיכָאֵל עוזר רַבִּין | |
출생 | 1931년 9월 1일 바이마르 공화국 브로츠와프 | (92세)
---|---|
국적 | |
출신 학교 | 예루살렘 히브리 대학교 (M.S. 1953) 프린스턴 대학교 (Ph.D. 1956) |
주요 업적 | 밀러-라빈 소수판별법 라빈 암호체계 분실 통신 라빈-카프 문자열 검색 알고리즘 비결정성 유한 상태 기계 확률적 알고리즘 |
수상 | 튜링상 (1976) 파리 카넬라키스 상 (2003) 이스라엘 상 에메트 상 하비 상 댄 데이비드 상 다익스트라 상 |
분야 | 컴퓨터 과학 |
소속 | 하버드 대학교 예루살렘 히브리 대학교 컬럼비아 대학교 |
박사 지도교수 | 알론조 처치 |
박사 지도학생 | Moshé Machover 사하론 셸라흐 Dov Gabbay Giuseppe Persiano |
미하엘 오제르 라빈(히브리어: מִיכָאֵל עוֹזֶר רַבִּין, 영어: Michael Oser Rabin 마이클 오저 라빈[*], 1931년 9월 1일 ~ ) 박사는 이스라엘의 저명한 전산학자이다. 튜링상 수상자이기도 하다.
학력
[편집]- ~1948년: 하이파고등학교 졸업
- ~1953년: 예루살렘 히브리대학교 전산학 석사
- ~1956년: 프린스턴 대학교 전산학 박사
생애
[편집]라빈은 오늘날 폴란드 영토인 브로츠와프에서 랍비의 아들로 태어났다. 1953년에 예루살렘 히브리 대학교에서 석사를 마쳤고, 1956년에는 프린스턴 대학교에서 박사 학위를 받았다.
현재 하버드 대학교 전산학과 토머스 왓슨(Thomas J. Watson Sr.) 석좌 교수이며 예루살렘 히브리 대학교 전산학과 교수이다.
업적
[편집]1976년에 라빈과 데이나 스콧은 1959년에 쓴 논문의 가치를 인정받아 튜링상을 수상했다. 라빈과 스콧의 공로는 다음과 같다. (튜링상 위원회의 공식 논평)
- 라빈과 스콧의 공동 논문 〈유한 자동장치와 판정문제(Finite Automata and Their Decision Problem)〉는 비결정론적 기계의 개념을 도입했고 이것은 매우 값진 의미를 가진다. 그들의 모범이 되는 논문은 이 분야의 관련된 연구를 위한 마르지 않는 영감의 원천이다.
비결정론적 기계는 계산 복잡도 이론에서 핵심적인 개념이다. 비결정론적 기계가 중요한 의미를 가지는 예에서 가장 유명한 것이 바로 P-NP 문제이다.
1975년에는 밀러-라빈 소수판별법을 개발했다. 이 알고리즘은 확률적 알고리즘으로서 오류가 발생할 아주 작은 확률이 있지만 매우 빠른 시간안에 주어진 수가 소수인지 아닌지 검사하는 알고리즘이다. 이와 같이 빠른 시간안에 소수를 판별하는 것은 공개열쇠암호에서 핵심적인 역할을 한다.
1979년에는 라빈 암호체계를 개발했다. 이것은 소인수 분해의 어려움에 기반하여 안전성을 증명한 첫 번째 비대칭 암호체계이다.
1981년에는 oblivious transfer라는 기술을 개발하였다. 이것은 어떤 사람이 메시지를 보냈을 때, 보내는 사람은 제대로 전송되었는지 알 수 없지만 받는 사람은 0에서 1 사이의 확률로 메시지를 제대로 전송받는 기술이다.
1987년에는 리처드 카프와 함께 가장 널리 알려진 문자열 검색 알고리즘의 한가지인 라빈-카프 문자열 검색 알고리즘을 만들었다.
라빈의 최근 연구과제는 컴퓨터 보안이다.