미하엘 라빈

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 생애
- 2.1. 초기 생애 및 교육
- 2.2. 학문적 경력
3. 주요 업적
4. 수상 및 영예
5. 개인사
참조

1. 개요

미하엘 라빈은 폴란드 브로츠와프에서 태어난 이스라엘-미국 수학자이자 컴퓨터 과학자이다. 예루살렘 히브리 대학교에서 석사 학위를, 프린스턴 대학교에서 박사 학위를 받았으며, 하버드 대학교와 히브리 대학교의 교수를 역임했다. 비결정적 유한 오토마타, 밀러-라빈 소수 판별법, 라빈 암호 시스템, 라빈-카프 문자열 검색 알고리즘 등 컴퓨터 과학과 암호학 분야에서 중요한 업적을 남겼으며, 튜링상, 이스라엘 상, 댄 데이비드 상 등을 수상했다.

더 읽어볼만한 페이지

데이크스트라상 수상자 - 에츠허르 데이크스트라
네덜란드 출신의 컴퓨터 과학자이자 수학자인 에츠허르 데이크스트라는 데이크스트라 알고리즘 개발, 구조적 프로그래밍 옹호, 세마포어 개념 연구, THE 운영체제 개발 참여 등 컴퓨터 과학의 다양한 분야에 큰 공헌을 했다.
데이크스트라상 수상자 - 레슬리 램포트
레슬리 램포트는 분산 시스템 이론에 기여한 미국의 컴퓨터 과학자로, 논리 시계, 순차적 일관성 개념 정립, 팍소스 알고리즘 등 분산 시스템 알고리즘 개발, LaTeX 초기 개발 기여, TLA+ 언어 설계 등의 공로로 2013년 튜링상을 수상하고 미국 공학 한림원 및 미국 과학 한림원 회원으로 선출되었다.
이스라엘의 수학자 - 엘리야후 립스
엘리야후 립스는 라트비아 출신의 수학자이자 반체제 운동가로, 성경 암호 연구를 진행했으며, 예루살렘 히브리 대학교 교수로 재직하다가 2024년에 사망했다.
이스라엘의 수학자 - 로버트 아우만
로버트 욘 아우만은 이스라엘과 미국의 수학자이자 게임 이론 학자로, 반복 게임 분석에 대한 공헌으로 2005년 노벨 경제학상을 수상했으며, 예루살렘 히브리 대학교의 수학과 교수로서 게임 이론, 공통 지식, 탈무드 연구 등 다양한 분야에서 업적을 남겼다.
이론 컴퓨터 과학자 - 앨런 튜링
앨런 튜링은 제2차 세계 대전 중 에니그마 암호 해독에 기여하고 컴퓨터 과학 분야에 지대한 영향을 미친 영국의 수학자, 컴퓨터 과학자이며, 동성애 혐의로 유죄 판결을 받은 후 자살로 생을 마감했다.
이론 컴퓨터 과학자 - 에츠허르 데이크스트라
네덜란드 출신의 컴퓨터 과학자이자 수학자인 에츠허르 데이크스트라는 데이크스트라 알고리즘 개발, 구조적 프로그래밍 옹호, 세마포어 개념 연구, THE 운영체제 개발 참여 등 컴퓨터 과학의 다양한 분야에 큰 공헌을 했다.

미하엘 라빈 - [인물]에 관한 문서
기본 정보
마이클 라빈
출생일	1931년 9월 1일
출생지	브로츠와프, 독일
국적	이스라엘
분야	컴퓨터 과학
직장	하버드 대학교 예루살렘 히브리 대학교 컬럼비아 대학교
모교	예루살렘 히브리 대학교 (MSc) 펜실베이니아 대학교 프린스턴 대학교 (PhD)
박사 지도 교수	알론조 처치
박사 학위 논문 제목	그룹 이론 문제의 재귀적 해결 불가능성
박사 학위 논문 연도	1957년
업적
주요 업적	라빈 암호체계 라빈 지문 라빈 서명 알고리즘 라빈-카프 문자열 검색 알고리즘 라빈-스콧 멱집합 구성 아디안-라빈 정리 벌레캄프-라빈 알고리즘 밀러-라빈 소수판별법 초암호화 무한 트리 오토마타 S2S의 결정 가능성 비결정적 유한 오토마타 무지 전송 확률적 오토마타 펌핑 보조정리 무작위화 알고리즘 양방향 유한 오토마타 검증 가능한 난수 함수
수상
수상 내역	와이즈만 상 (1959년) 튜링상 (1976년) 하비 상 (1980년) 깁스 강연 (1985년) 이스라엘 상 (1995년) IEEE 컴퓨터 학회 찰스 배비지 상 (2000년) 파리 카넬라키스 상 (2003년) 에메트 상 (2004년) 괴델 강연 (2004년) 댄 데이비드 상 (2010년) 다익스트라 상 (2015년)
제자
주요 제자	주디트 바-일란 도브 가바이 모셰 마초버 사하론 셸라흐

2. 생애

미하엘 라빈은 1931년 폴란드 브로츠와프에서 랍비의 아들로 태어났다. 1953년에 예루살렘 히브리 대학교에서 석사 학위를, 1956년에는 프린스턴 대학교에서 박사 학위를 받았다.^[23] 현재 하버드 대학교 전산학과 토머스 왓슨(Thomas J. Watson Sr.) 석좌 교수이며 예루살렘 히브리 대학교 전산학과 교수이다.

1935년, 가족과 함께 영국 위임 통치령 팔레스타인으로 이주했다. 소년 시절 수학에 강한 관심을 보였고, 하이파의 최고 고등학교에 진학하여 수학자 엘리샤 네타냐후에게 배웠다.^[23] 제1차 중동 전쟁 (1948) 때 육군에 징집되었으나, 아돌프 프렌켈의 도움으로 1949년에 병역에서 해제되어 히브리 대학교에서 공부할 수 있게 되었다.^[23]

1950년대 말, IBM의 초청으로 뉴욕주웨스트체스터 군 램 이스테이트에서 데이비드 스콧과 함께 "Finite Automata and Their Decision Problems"(유한 오토마타와 그 결정 문제) 논문을 썼다.^[24] 비결정적 유한 오토마타를 활용하여 클리니의 결론을 재증명했다.^[23] 이후 계산 복잡도 이론의 원형이 되는 연구를 진행, 존 매카시가 제시한 퍼즐을 바탕으로 "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets"(함수를 계산하는 어려움의 정도와 귀납적 집합의 계층) 논문을 썼다.^[23]^[25] 비결정적 유한 오토마타는 P≠NP 문제 설명에 중요하게 사용된다.

예루살렘으로 돌아와 논리학을 연구하고 컴퓨터 과학의 기초를 구축했다. 히브리 대학교 부교수, 29세에 수학 연구소 소장, 33세에 정교수가 되었다.^[23] 1960년 벨 연구소에서 확률적 오토마타를 고안, 상태 수를 줄일 수 있음을 보였다.^[23]

1969년, n 후자의 2계 술어 논리가 결정성임을 증명했다.^[26] 1975년 매사추세츠 공과대학교에서 게리 밀러와 함께 밀러-라빈 소수 판별법을 발명했다.^[27]^[28] 2003년, 밀러와 라빈은 파리 카넬라키스 상을 수상했다.

1979년 라빈 암호를,^[29] 1981년 분실 통신을 발명했다.^[30] 1987년 리처드 카프와 함께 라빈-카프 문자열 검색 알고리즘을 개발했다.^[31] 이후 컴퓨터 보안 연구에 집중하고 있다. 미국 과학 아카데미, 프랑스 과학 아카데미, 왕립 학회 외국 회원이며, 지도 학생으로 사하론 셸라가 있다.

2. 1. 초기 생애 및 교육

미하엘 라빈은 1931년 당시 바이마르 공화국의 브레슬라우(현재 폴란드의 브로츠와프)에서 랍비의 아들로 태어났다.^[1] 1935년, 그는 가족과 함께 팔레스타인 위임통치령으로 알리야했다.^[1] 어린 시절부터 그는 수학에 매우 관심이 많았고, 그의 아버지는 그를 하이파 최고의 고등학교에 보냈는데, 그곳에서 그는 당시 고등학교 교사였던 수학자 엘리샤 네타냐후 밑에서 공부했다.^[1]

라빈은 1948년 하이파의 히브리 레알리 학교를 졸업하고 1948년 아랍-이스라엘 전쟁 중 군에 징집되었다. 예루살렘에서 수학 교수로 재직하고 있던 수학자 아브라함 프뢴켈이 군 지휘부에 개입하여, 라빈은 1949년 대학에서 공부하기 위해 제대했다.^[1] 이후, 그는 예루살렘 히브리 대학교에서 이학 석사 학위를 받았다. 그는 펜실베이니아 대학교에서 대학원 과정을 시작했고, 1956년 프린스턴 대학교에서 철학 박사 학위를 받았다.^[2]

2. 2. 학문적 경력

캘리포니아 대학교 버클리(1961-62)와 매사추세츠 공과대학교(MIT)(1962-63)에서 수학 부교수를 역임했다.^[3] 1969년, 무한 트리 오토마타를 도입하고 ''n'' 개의 후속자 (S2S는 ''n'' = 2일 때)의 단항 2차 이론이 결정 가능함을 증명했다.^[9] 이 증명의 핵심 구성 요소는 암묵적으로 패리티 게임의 결정성을 보여주었는데, 이는 보렐 계층의 세 번째 레벨에 속한다.

29세에 예루살렘 히브리 대학교 수학 연구소 부교수 겸 소장이 되었고, 33세에 정교수가 되었다.^[1] 1975년에는 예루살렘 히브리 대학교 총장 임기를 마치고 매사추세츠 공과대학교로 방문 교수로 갔다.^[10]^[11]

1981년 하버드 대학교 고든 맥케이 컴퓨터 과학 교수로 임용되었다.^[3] 현재 하버드 대학교 토머스 J. 왓슨 시니어 컴퓨터 과학 교수 및 예루살렘 히브리 대학교 컴퓨터 과학 교수이다. 2007년 봄 학기에는 컬럼비아 대학교에서 방문 교수로 ''암호학 입문''을 가르쳤다.

3. 주요 업적

1976년 데이나 스콧과 함께 튜링상을 수상했는데, 튜링상 위원회는 라빈과 스콧의 공동 논문 〈유한 자동장치와 판정문제(Finite Automata and Their Decision Problem)〉가 비결정론적 기계의 개념을 도입하여 이 분야의 후속 연구에 큰 영향을 주었다고 평가했다.^[24]

1975년에는 밀러-라빈 소수판별법을 개발했다. 이 알고리즘은 매우 빠른 속도로 주어진 수가 소수인지 판별하며, 공개열쇠암호에서 중요한 역할을 한다.^[27]^[28]

1979년에는 소인수 분해의 어려움에 기반하여 안전성이 증명된 최초의 비대칭 암호체계인 라빈 암호체계를 개발했다.^[29]

1987년에는 리처드 카프와 함께 라빈-카프 문자열 검색 알고리즘을 만들었다.^[31]

그 외에도 분실 통신 기술을 개발하고,^[30] n개의 후속자를 가지는 2계 술어 논리가 결정성임을 증명하는 등 다양한 업적을 남겼다.^[26] 최근에는 컴퓨터 보안을 연구하고 있다.

3. 1. 비결정적 유한 오토마타 (Nondeterministic Finite Automata)

1959년 데이나 스콧과 함께 쓴 논문 〈유한 자동장치와 판정문제(Finite Automata and Their Decision Problem)〉에서 비결정론적 기계의 개념을 도입했다.^[24] 이 개념은 계산 복잡도 이론의 핵심적인 개념으로, 특히 P-NP 문제를 설명할 때 중요하게 사용된다. 1976년에는 이 논문의 가치를 인정받아 데이나 스콧과 함께 튜링상을 수상했다.^[23]

3. 2. 밀러-라빈 소수 판별법 (Miller-Rabin Primality Test)

1975년에 개발된 밀러-라빈 소수판별법은 확률적 알고리즘으로서, 주어진 수가 소수인지 아닌지를 매우 빠른 시간에 검사하는 알고리즘이다. 아주 작은 확률로 오류가 발생할 가능성은 존재한다.^[27]^[28] 이 알고리즘은 공개열쇠암호에서 핵심적인 역할을 한다.

매사추세츠 공과대학교 객원 교수 시절, 게리 밀러가 확장된 리만 가설에 기초한 다항 시간의 소수 판별법을 고안한 것을 바탕으로, 라빈은 확장된 리만 가설에 의존하지 않는 밀러-라빈 소수 판별법을 발명했다.^[27]^[28] 공개 키 암호에는 RSA 암호처럼 큰 소수를 비밀 키로 하는 경우가 많아, 빠른 소수 판별법은 키 생성 구현에 중요하다.

2003년, 밀러와 라빈은 소수 판별법에서의 업적을 인정받아 로버트 M. 솔로베이, 볼커 슈트라센과 함께 파리 카넬라키스 상을 공동 수상했다.

3. 3. 라빈 암호 시스템 (Rabin Cryptosystem)

1979년에 라빈은 라빈 암호체계를 개발했다. 이것은 소인수 분해의 어려움에 기반하여 안전성을 증명한 첫 번째 비대칭 암호체계이다.^[29] 암호문을 해독하는 과정이 공개 키인 합성수의 소인수 분해를 하는것과 같다는 것이 증명되었다.

3. 4. 라빈-카프 문자열 검색 알고리즘 (Rabin-Karp String Search Algorithm)

1987년 리처드 카프와 함께 널리 알려진 문자열 검색 알고리즘 중 하나인 라빈-카프 문자열 검색 알고리즘을 개발했다.^[31] 이 알고리즘은 롤링 해시 기법을 활용하여 빠르고 효율적인 문자열 검색을 가능하게 한다.

3. 5. 기타 업적

1969년 무한 트리 오토마타를 도입하고 n개의 후속자(S2S)의 단항 2차 이론이 결정 가능함을 증명했다.^[26] 이 증명의 중요한 요소로, 보렐 계층의 세 번째 레벨에 있는 패리티 게임의 결정성이 포함되었다. 1981년에는 분실 통신(Oblivious Transfer) 기술을 개발하였다.^[30] 이는 송신자가 메시지를 보냈을 때, 송신자는 전송 여부를 알 수 없지만 수신자는 0과 1 사이의 확률로 메시지를 받는 기술이다. 최근에는 컴퓨터 보안 분야 연구에 주력하고 있다.

4. 수상 및 영예

1973년 로스차일드상을 수상했다.^[19]

1976년 튜링상을 데이비드 스콧과 공동 수상했다.^[32] 수상 이유는 다음과 같다.

> 「그들의 공동 저술 논문 "유한 오토마타와 그 결정 문제"에 대하여. 이 논문은 비결정적 머신이라는 매우 가치있는 개념을 도입했다. 이 고전적인 논문은 이 분야의 후속 연구자들에게 끊임없이 영감을 주었다」^[33]

1980년 하비상을 수상했다.

1995년 컴퓨터 과학 분야에서 이스라엘 상을 수상했다.^[34]

2010년 텔아비브 대학교 댄 데이비드 상 ("미래" 부문)을 레너드 클레인록, 고든 무어와 함께 컴퓨터 및 통신 분야에서 공동으로 수상했다.^[20]

2017년 하버드 대학교에서 명예 과학 박사 학위를 받았다.^[21]

미국 국립 과학 아카데미,^[15] 미국 철학회,^[16] 미국 예술 과학 아카데미,^[17] 프랑스 과학 아카데미, 왕립 학회의 외국인 회원이다.

5. 개인사

라빈은 컴퓨터 과학자인 딸 탈 라빈을 두고 있다.^[22]

참조

_[1] 논문 An Interview with Michael O. Rabin http://cacm.acm.org/[...] 2010-02
_[2] 웹사이트 Michael O. Rabin https://amturing.acm[...] amturing.acm 2023-08-14
_[3] 웹사이트 Michael O. Rabin - Curriculum Vitae https://www.seas.har[...] Harvard University 2017-03-31
_[4] 논문 Finite Automata and Their Decision Problems http://www.cse.chalm[...]
_[5] 간행물 Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets O.N.R., Hebrew University, Jerusalem
_[6] conference Mathematical theory of automata Amer. Math. Soc.
_[7] conference The intrinsic computational difficulty of functions
_[8] 논문 Paths, trees, and flowers
_[9] 논문 Decidability of second order theories and automata on infinite trees http://projecteuclid[...] 2007-11-24
_[10] conference Probabilistic algorithms
_[11] 논문 Probabilistic algorithm for testing primality
_[12] 논문 Digitalized signatures and public-key functions as intractable as factorization https://web.archive.[...] 1979-01
_[13] 서적 How to exchange secrets by oblivious transfer (Technical Report TR-81) http://eprint.iacr.o[...] Harvard University 2007-03-15
_[14] 논문 Efficient randomized pattern-matching algorithms http://portal.acm.or[...] 2007-03-15
_[15] 웹사이트 Michael O. Rabin http://www.nasonline[...] 2022-05-02
_[16] 웹사이트 APS Member History https://search.amphi[...] 2022-05-02
_[17] 웹사이트 Michael Oser Rabin https://www.amacad.o[...] 2022-05-02
_[18] 웹사이트 ACM Turing Award Citation http://awards.acm.or[...] 2012-07-14
_[19] 웹사이트 Israel Prize Official Site - Recipients in 1995 (in Hebrew) https://web.archive.[...]
_[20] 웹사이트 Dan David Prize Official Site - Laureates 2010 https://web.archive.[...]
_[21] 웹사이트 Harvard awards 10 honorary degrees http://news.harvard.[...] 2017-05-25
_[22] 웹사이트 Tal Rabin https://www.forbes.c[...] 2022-10-26
_[23] 뉴스 An Interview with Michael O. Rabin http://cacm.acm.org/[...] Dennis Shasha, Communications of the ACM 2010-02
_[24] 논문 Finite Automata and Their Decision Problems http://domino.watson[...]
_[25] 간행물 Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets O.N.R., Hebrew University, Jerusalem
_[26] 논문 Decidability of second order theories and automata on infinite trees http://projecteuclid[...]
_[27] conference Probabilistic algorithms
_[28] 논문 Probabilistic algorithm for testing primality
_[29] 논문 Digital signatures and public-key functions as intractable as factorization http://www.lcs.mit.e[...] 1979-01
_[30] 서적 How to exchange secrets by oblivious transfer (Technical Report TR-81) http://eprint.iacr.o[...] Harvard University
_[31] 논문 Efficient randomized pattern-matching algorithms http://portal.acm.or[...]
_[32] 논문 Finite Automata and Their Decision Problems http://ieeexplore.ie[...]
_[33] 웹사이트 ACM Turing Award Citation http://awards.acm.or[...] 2012-07-14
_[34] 웹사이트 Israel Prize Official Site - Recipients in 1995 (in Hebrew) http://cms.education[...] 2012-08-13
_[35] 웹사이트 Dan David Prize Official Site - Laureates 2010 http://www.dandavidp[...] 2012-08-13

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com