Interested Article - Рабин, Михаэль

Михаэль Озер Рабин ( нем. Michael Oser Rabin , ивр. מִיכָאֵל עוזר רַבִּין ‎, род. 1 сентября 1931 , Вроцлав ) — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга .

Биография

Михаэль Рабин родился в 1931 году в семье уроженца Проскурова , раввина Исраэля Аврахама Рабина в Бреслау (ныне Вроцлав ), принадлежавшем тогда Пруссии . В 1935 году его семья эмигрировала в Палестину . В 1953 году он получил степень магистра наук , окончив учёбу в Еврейском университете в Иерусалиме . Три года спустя, в 1956 году , защитил диссертацию в Принстонском университете и стал доктором философии .

Занимаелся исследованиями в области компьютерной безопасности и преподаёт в Иерусалиме и Гарварде . Имеет звания почётного профессора в следующих вузах:

К его знаменитым ученикам относится Саарон Шелах , ныне профессор в Иерусалиме, лауреат премии Вольфа по математике.

Его дочь Таль Рабин руководит научной группой Cryptography and Privacy Research Group в компании IBM .

Достижения

В 1969 году Рабин обобщил на случай более одной функции следования, чем показал разрешимость соответствующей теории второго порядка . В ходе ведения доказательства он доказал детерминированность игр на чётность ( англ. parity games )

В 1975 году Гари Миллер разработал новый тест простоты, который был модифицирован Рабином в 1980 году. Тест Миллера — Рабина вероятностный полиномиальный алгоритм, способный очень эффективно, но с ненулевой вероятностью ошибки, проверить число на простоту . Четыре года спустя, Майкл Рабин разработал первую асимметричную криптосистему , сложность взлома которой сравнима с проблемой факторизации целых чисел .

В 1981 году Рабин изобрёл протокол передачи данных с забыванием ( англ. oblivious transfer ) — надёжную технику передачи информации, при которой отправитель не получает подтверждения того, дошло ли сообщение до получателя. В 1987 году, вместе с Ричардом Карпом , Рабин разработал знаменитый алгоритм поиска образца (подстроки) в строке .

Награды

См. также

Примечания

  1. . Дата обращения: 16 сентября 2008. 2 октября 2008 года.
  2. . Дата обращения: 16 сентября 2008. 25 мая 2011 года.
  3. от 18 июня 2007 на Wayback Machine (англ.)
  4. от 6 января 2011 на Wayback Machine , , 16 декабря 2004 года (англ.)

Ссылки

  • (недоступная ссылка с 13-05-2013 [3941 день] — ) (англ.)
  • Karp, RM; Rabin, MO (March 1987). «Efficient randomized pattern-matching algorithms». IBM Journal of Research and Development. 31 (2): 249—260.
Источник —

Same as Рабин, Михаэль