Леонард Макс Адлеман
Биография
Адлеман родился в Калифорнии в 1945 году, вырос в Сан-Франциско. После получения школьного образования он поступил в Калифорнийский университет в Беркли. Это был не первый его выбор по поводу академической карьеры – изначально, он хотел стать химиком, потом доктором, пока окончательно не остановился на профессии математика. Адлеман получил степень бакалавра по математике в 1968 году. После присуждения этой ученой степени работал программистом в Банке Америки. В это же время он пошел в медицинскую школу, где он был принят, но изменил свое мнение, решив стать физиком. Поэтому Адлеман начал брать уроки в Университете штата в Сан-Франциско. Но и физика ему пришлась не по душе. “ Я не люблю делать эксперименты, мне нравится думать о вещах”, – говорил он. Затем он вернулся в Беркли, где он получил степень доктора философии по электротехнике и компьютерным наукам в 1976 году и написал диссертацию “Теоретические аспекты вычислительной сложности”. После этого Адлеман устроился на работу в Массачусетский Технический Институт на кафедру математики. Изначально он был нанят как инструктор, стал помощником профессора математики в 1977 году и, наконец, адъюнкт-профессором (associate professor) в 1979 году. В 1980 году Адлеман занял должность в Университете Южной Калифорнии на факультете компьютерных наук. В 1983 году стал профессором, а в 1985 году - получил звание профессора Генри Сальватори компьютерных наук (the Henry Salvatori professor of Computer Science). Одновременно с этим он являлся профессором молекулярной биологии.
На протяжении этого карьерного пути основной сферой интереса и исследований Адлемана была теоретическая компьютерная наука, в частности, сложность некоторых теоретических проблем, которые и стали основой для некоторых его известных работ по криптографии. Он был одним из разработчиков RSA криптосистемы, совместно с Рональдом Ривестом и Ади Шамир. Данный алгоритм шифрования был разработан ими в 1976 году в Массачусетском технологическом институте. За свой вклад в изобретение RSA криптосистемы Адлеман, вместе с Рональдом Ривестом и Ади Шамир, стал обладателем награда Париса Канеллакиса (Paris Kanellakis) за теорию и практику 1996 года и премии Тьюринга 2002 года, которую часто называют Нобелевской премией компьютерных наук.
В 1994 году в работе «Молекулярное вычисление решений к комбинаторным задачам» (Molecular Computation of Solutions To Combinatorial Problems) он описывает экспериментальное применение ДНК как вычислительной системы. В ней он решает задачу о гамильтоновом пути для случая семи вершин, NP-сложную, сходную с задачей коммивояжёра. Несмотря на то, что для этого случая решение является тривиальным, эта работа впервые продемонстрировала успешное применение ДНК для алгоритмических вычислений. Было показано, что ДНК-вычисления имеют потенциал как средство решения некоторых других широкомасштабных комбинаторных задач поиска. В 2002 году он и его исследовательской группе удалось решить "нетривиальную" проблему с помощью ДНК-вычислений. В частности, они решили 20-переменную задачу выполнимости булевых формул, имеющую более 1 млн. потенциальных решений. Они сделали это в манере, подобной той, что Адлеман использовал в своей фундаментальной работе 1994 года. Сначала была синтезирована смесь нитей ДНК - логическое отражение пространства решений задачи. Затем эту смесь обработали алгоритмически с помощью биохимических методов, отсеивая "неправильные" нити, оставляя только те нити, которые "удовлетворяют" проблеме. Анализ нуклеотидной последовательности этих оставшихся нитей показал «правильное» решения исходной задачи.
Адлеман еще известен, как человек, который придумал термин “компьютерный вирус” после встречи с одним из них, созданным его учеником Фредом Коеном (Fred Cohen) в 1983 году. Коен и Адлеман решили опубликовать код этого вируса, предполагая, что это работа по подготовке и распространению информации. Адлеман чувствовал, что компьютерные вирусы могут открыть много возможностей и что потенциально польза, полученная от них в технологиях будущего, может перевесить негативные стороны их использования.
Как результат его деятельности в области молекулярной биологии, Адлеман произвел математическую модель иммунной недостаточности, вызванной вирусом СПИДа. Это дало понимание того, как вирус работает, а также открыло различные направления исследований для поиска путей лечения. Адлеман вместе с Дэвидом Вофси (David Wofsy) из Калифорнийского университета в Сан-Франциско описал результаты проверки их гипотезы в феврале 1993 года вопрос в журнале Синдромы приобретенного иммунного дефицита. К сожалению, отзывы исследовательского сообщества к идеям Адлемана были необнадеживающими. Не испугавшись, Адлеман решил приобрести более глубокое понимание биологии ВИЧ для того, чтобы быть более убедительным. Он вошел в лабораторию молекулярной биологии в Университете Южной Калифорнии и начал изучать методы современной биологии под руководством Николая Челяпова (Nickolas Chelyapov), который в настоящее время является главным научным сотрудником в собственной лаборатории в Адлемана.
Адлеман также описал новый метод установления, является ли число простым (этой частью работы он больше всего гордится). Также он был консультантом по математике, которая касается криптографии, для голливудского фильма “Тихушники” (“Sneakers”).
В начале двадцать первого века Адлеман по-прежнему работал в Университете Южной Калифорнии. Сейчас он живет со своей женой в Лос-Анджелесе, от которой у него трое детей.
Награды и почетные звания
- 2006 - Адлеман был избран членом Американской академии искусств и наук.
- 2002 - премиия Тьюринга.
- 2000 - Премия в области компьютеров и коммуникаций имени Кодзи Кобаяси (IEEE Kobayashi Award for Computers and Communications). (совместно с Рональдом Ривестом и Ади Шамир)
- 2000 - звание заслуженного профессора Университета Южной Калифорнии.
- 1996 - от Ассоциации вычислительной техники награда Париса Канелакиса за теорию и практику. За работу над открытыми ключами шифрования. (совместно с Рональдом Ривестом, Ади Шамир, Уитфилдом Диффи, Мартином Хеллманом и Рафом Меркле)
- 1996 - избран членом Национальной инженерной академии.
- 1995 - заслуженный выпускник Факультета компьютерных наук и инженерного университета Калифорнии, Беркли.
- 1985 - получил звание профессора Генри Сальватори компьютерных наук.
- 1991 - Лауреат Университета Южной Калифорнии.
- 1978 – награда за лучшую работу IEEE группы по теории информации “Способ получения цифровой подписи и криптосистемы с открытым ключом”. (совместно с Рональдом Ривестом и Ади Шамир)
Разработки и избранные публикации с их кратким описанием
- "Способ получения цифровой подписи и криптосистем с открытым ключом", журнал Ассоциации вычислительной техники, 21 (2) :120-126, (февраль) 1978 года. (c Р. Ривест, А. Шамир).
Эта статья представляет первое олицитворение открытых ключей криптосистемы. Основными вычислениями, которыми пользуются для шифрования и дешифрования, являются возведение в степень по отношению к составному модулю. Этот документ вместе с работами Уитфилда Диффи и Мартина Хеллмана (“Новые направления в криптографии”) и Рафа Меркле (“Безопасные связи по незащищенным каналам”) рассматриваются как конструктивные работы в области криптографии с открытым ключом. RSA-система продолжает занимать центральное место в теоретических и практических разработках этой области. Более 400 миллионов копий RSA алгоритма в настоящее время установлены, и он является основной криптосистемой, используемой для обеспечения безопасности в интернете и всемирной паутине.
- "О различении простых чисел из составных чисел", Annals of Mathematics, 117, 173-206, 1983.
Эта статья представляет детерминированный алгоритм, использующий "почти полиномиальное время” для проблемы нахождения и различения простых чисел. В частности, существует положительное вещественное с, что для достаточно больших n, алгоритм заканчивается за log n^c log(log(log(n))) шагов. Следующий наилучший из детерминированных алгоритмов строго экспоненциальный. Основные методы, используемые в алгоритме из алгебраической теории чисел и теории полей классов (высшие законы взаимности) смогли упростить реализацию алгоритма, что позволяет проверить простоту чисел из сотни цифр в несколько минут.
- "Первый случай теоремы Ферма", Invent. Math 79:409-416, 1985. (с R. Heath-Brown)
Эта работа была впоследствии заменена блестящими работами Эндрю Уайлс о доказательстве Теоремы Ферма.
- "Проверка простоты и двумерных абелевых многообразий над конечными полями", Springer Verlag Lecture Notes In Mathematics 1512, 142 страниц, 1992 год. (с А. Huang)
- "Молекулярные вычисления решений комбинаторной задачи", Наука (Science), 266: 1021-1024 (11 ноября) 1994 года.