Леонард Макс Адлеман

Леонард Адлеман

англ. Leonard Adleman

Дата рождения

31 декабря 1945 года

Место рождения

Сан-Франциско, США

учёный

Леонард Макс Адлеман (Леонард Макс Эйдлмен, Лен Адлеман, англ. Leonard Adleman — американский учёный-теоретик в сфере компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии, соавтор системы шифрования RSA (широко используемого в приложениях компьютерной безопасности, включая протокол HTTPS) и ДНК-вычислений.

Научная карьера

Леонард Адлеман родился 31 декабря 1945 года в Калифорнии, вырос в Сан-Франциско.

В 1968 году получил степень бакалавра по математике в Калифорнийском университете в Беркли.

Затем работал программистом в Банке Америки. Пошёл в медицинскую школу, где был принят, однако потом решил стать физиком и начал брать уроки в Университете штата в Сан-Франциско.

В 1976 году получил степень доктора философии по электротехнике и компьютерным наукам в Калифорнийском университете в Беркли, написав диссертацию «Теоретические аспекты вычислительной сложности».

Затем устроился на работу в Массачусетский Технический Институт на кафедру математики. Изначально был нанят как инструктор, стал помощником профессора математики в 1977 году, а в 1979 году стал адъюнкт-профессором.

В 1980 году получил должность в Университете Южной Калифорнии на факультете компьютерных наук. В 1983 году стал профессором, а в 1985 году — получил звание профессора Генри Сальватори компьютерных наук. Кроме того, стал профессором молекулярной биологии.

На протяжении этого карьерного пути главной сферой его интереса и исследований была теоретическая компьютерная наука, в частности, сложность некоторых теоретических проблем, которые и стали основой для некоторых его известных работ по криптографии.

В 1976−1977 годах стал одним из разработчиков RSA (криптографического алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел), вместе с Рональдом Ривестом и Ади Шамир в Массачусетском технологическом институте.

В 1978 году вместе с Р. Ривест и А. Шамир журнале Ассоциации вычислительной техники опубликовал работу «Способ получения цифровой подписи и криптосистем с открытым ключом». Данная статья представляет первое олицетворение открытых ключей криптосистемы. Основными вычислениями, которыми пользуются для шифрования и дешифрования, являются возведение в степень по отношению к составному модулю. Этот документ вместе с работами Уитфилда Диффи и Мартина Хеллмана («Новые направления в криптографии») и Рафа Меркле («Безопасные связи по незащищенным каналам») рассматриваются как конструктивные работы в области криптографии с открытым ключом. RSA-система продолжает занимать центральное место в теоретических и практических разработках этой области. Свыше 400 миллионов копий RSA алгоритма в настоящее время установлены, и он стал основной криптосистемой, применяемой для обеспечения безопасности в интернете и всемирной паутине.

В 1983 году опубликовал статью «О различении простых чисел из составных чисел». Статья представляет детерминированный алгоритм, использующий «почти полиномиальное время» для проблемы нахождения и различения простых чисел. В частности, существует положительное вещественное с, что для достаточно больших n, алгоритм заканчивается за log n^c log(log(log(n))) шагов. Следующий наилучший из детерминированных алгоритмов строго экспоненциальный. Основные методы, используемые в алгоритме из алгебраической теории чисел и теории полей классов (высшие законы взаимности) смогли упростить реализацию алгоритма, что позволяет проверить простоту чисел из сотни цифр в несколько минут.

Также около 1983 года вместе с Фредом Коэном ввёл понятие «компьютерный вирус». Коэн и Адлеман решили опубликовать код вируса Коэна, предполагая, что это работа по подготовке и распространению информации. Адлеман полагал, что компьютерные вирусы могут открыть много возможностей и что потенциально польза, полученная от них в технологиях будущего, может перевесить негативные стороны их применения.

В 1985 году опубликовал статью «Первый случай теоремы Ферма».

В 1992 году опубликовал статью «Проверка простоты и двумерных абелевых многообразий над конечными полями».

В 1994 году в работе «Молекулярное вычисление решений к комбинаторным задачам» («Молекулярные вычисления решений комбинаторной задачи») Адлеман описывает экспериментальное применение ДНК как вычислительной системы. В ней Адлеман решает задачу о гамильтоновом пути для случая семи вершин, NP-сложную, сходную с задачей коммивояжёра. Несмотря на то, что для этого случая решение является тривиальным, эта работа впервые продемонстрировала успешное применение ДНК для алгоритмических вычислений. Было показано, что ДНК-вычисления имеют потенциал как средство решения некоторых других широкомасштабных комбинаторных задач поиска.

В 1996 году получил от Ассоциации вычислительной техники премию Канеллакиса за теорию и практику. За работу над открытыми ключами шифрования. Был избран членом Национальной инженерной академии.

В 2002 году Адлеману и его исследовательской группе удалось решить «нетривиальную» проблему при помощи ДНК-вычислений. В частности, они решили 20-переменную задачу выполнимости булевых формул, имеющую более 1 миллиона потенциальных решений. Они сделали это в манере, на подобии той, что Адлеман применил в своей работе 1994 года. Сначала была синтезирована смесь нитей ДНК — логическое отражение пространства решений задачи. Затем эту смесь обработали алгоритмически с помощью биохимических методов, отсеивая «неправильные» нити, оставляя только те нити, которые «удовлетворяют» проблеме. Анализ нуклеотидной последовательности этих оставшихся нитей показал «правильное» решения исходной задачи.

В том же 2002 году — лауреат премии Тьюринга — «За уникальный вклад по увеличению практической пользы систем шифрования с открытым ключом».

Как результат деятельности Адлемана в области молекулярной биологии, произвёл математическую модель иммунной недостаточности, вызванной вирусом СПИДа, что дало понимание того, как вирус работает, и открыло различные направления исследований для поиска путей лечения. Адлеман вместе с Дэвидом Вофси из Калифорнийского университета в Сан-Франциско описал результаты проверки их гипотезы в феврале 1993 года вопрос в журнале Синдромы приобретенного иммунного дефицита. Адлеман вошёл в лабораторию молекулярной биологии в Университете Южной Калифорнии и начал изучать методы современной биологии под руководством Николая Челяпова, который является главным научным сотрудником в собственной лаборатории в Адлемана.

Описал новый метод установления, является ли число простым.