米高·O·拉賓希伯來語מִיכָאֵל אֹשֶׁר רַבִּין‎,英語:Michael Oser Rabin,1931年9月1日 )是一名以色列計算機科學家,1976年圖靈獎得主。

Quick Facts 米高·拉賓Michael Oser Rabin, 出生 ...
米高·拉賓
Michael Oser Rabin
Thumb
出生 (1931-09-01) 1931年9月1日93歲)
德國魏瑪共和國布雷斯勞(今波蘭弗羅茨瓦夫
知名於米勒-拉賓素數檢驗
拉賓密碼系統英語Rabin cryptosystem
不經意傳輸
拉賓-卡普字符串搜索算法
非確定有限狀態自動機
隨機化算法
獎項圖靈獎 (1976)
Paris Kanellakis Award英語Paris Kanellakis Award (2003)
以色列獎
艾邁特藝術科學與文化獎英語EMET Prize
哈維獎
丹·大衛獎
戴克斯特拉獎英語Dijkstra Prize
IEEE計算機協會查爾斯-巴貝奇獎英語International Parallel and Distributed Processing Symposium#IEEE Computer Society Charles Babbage Award
科學生涯
研究領域計算機科學
機構哈佛大學
希伯來大學
哥倫比亞大學
Close

生平

拉賓出生於德國布雷斯勞二戰後成為波蘭弗羅茨瓦夫),父親是一個拉比

1953年,他獲得希伯來大學理學碩士,1956年獲普林斯頓大學博士學位

1959年,拉賓和達納·斯科特共同發表了「有限自動機與其判定性問題」(Finite Automata and Their Decision Problems)的論文,提出了非確定自動機的觀點。他們也因此獲得了1976年的圖靈獎,並做「計算機複雜性」(Complexity of Computations)的演講。圖靈獎的引文是:

非確定自動機已經成為計算複雜度理論中的一個重要概念,特別是在描述P與NP問題複雜度類時。

1969年,拉賓證明N successors的二階邏輯可判定的[2]證明的關鍵部分暗示了奇偶遊戲英語Parity game的確定性。1975年,拉賓發明了米勒-拉賓檢驗,這是一個相當快速的隨機化算法(有較小的可能性錯誤),用於判斷一個大數是否是素數[3][4] 快速素數檢驗是目前大部分公鑰密碼體系的關鍵。1979年,拉賓發明了第一個非對稱密碼系統——拉賓密碼系統英語Rabin cryptosystem。它的安全性被證明和整數因式分解的複雜度相同。[5]1981年,拉賓提出了不經意傳輸技術。[6] 1987年,拉賓和理查德·卡普提出了一個著名的字符串搜索算法——拉賓-卡普算法[7]

參考

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.