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

Леонард Адлеман — американский учёный в области информатики и молекулярной биологии, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии (USC). Наиболее известен как один из создателей криптосистемы RSA (совместно с Роном Ривестом и Ади Шамиром), за что в 2002 году удостоен премии Тьюринга. Также внёс значительный вклад в развитие ДНК-вычислений и теории вычислительной сложности.

Биография

Ранние годы и образование

Леонард Макс Адлеман родился 31 декабря 1945 года в Сан-Франциско (штат Калифорния, США) в еврейской семье. Его отец работал бухгалтером, мать была домохозяйкой. Интерес к математике и естественным наукам проявился ещё в школьные годы.

В 1968 году он получил степень бакалавра по математике в Калифорнийском университете в Беркли. Затем продолжил обучение там же и в 1976 году защитил докторскую диссертацию (Ph.D.) по электротехнике и компьютерным наукам под руководством Мануэля Блума. Тема диссертации была посвящена теории вычислительной сложности и, в частности, проблеме распознавания простых чисел.

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

После получения докторской степени Адлеман работал в Массачусетском технологическом институте (MIT) в лаборатории компьютерных наук. В 1980 году он перешёл в Университет Южной Калифорнии, где впоследствии стал профессором кафедры компьютерных наук и кафедры молекулярной биологии. Его исследования охватывают широкий спектр областей: от криптографии и теории чисел до биоинформатики и нанотехнологий.

Основные достижения

Криптосистема RSA

Главным научным достижением Адлемана является создание в 1977 году криптосистемы с открытым ключом RSA. Название алгоритма составлено из первых букв фамилий авторов: Rivest, Shamir, Adleman. RSA стала первой практически применимой асимметричной криптосистемой, основанной на вычислительной сложности разложения больших целых чисел на простые множители. Алгоритм до сих пор широко используется для шифрования данных и цифровой подписи в интернете, банковских системах и электронной коммерции.

За эту работу в 2002 году Ривест, Шамир и Адлеман были удостоены премии Тьюринга — высшей награды в области информатики.

ДНК-вычисления

В 1994 году Адлеман опубликовал статью «Molecular Computation of Solutions to Combinatorial Problems» в журнале Science, где впервые экспериментально продемонстрировал возможность использования молекул ДНК для решения вычислительных задач. Он решил классическую задачу коммивояжёра (для 7 городов) с помощью биохимических реакций, закодировав данные в цепочках ДНК и используя ферменты для выполнения операций.

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

Теория вычислительной сложности

В 1970-х годах Адлеман совместно с Мануэлем Блумом и другими учёными внёс вклад в теорию сложности алгоритмов. В частности, он изучал свойства классов сложности P и NP, а также разработал понятие односторонних функций — функций, которые легко вычислить, но трудно обратить. Это понятие стало фундаментальным для современной криптографии.

Вклад в теорию чисел

Адлеман работал над алгоритмами проверки чисел на простоту. В 1977 году он совместно с Роном Ривестом и Альбертом Мейером предложил вероятностный тест простоты (тест Миллера — Рабина), который широко применяется в криптографических системах. Позже он участвовал в разработке детерминированного теста простоты AKS (названного по фамилиям авторов — Агравал, Кайал, Саксена), который стал первым полиномиальным детерминированным алгоритмом проверки простоты.

Награды и признание

• Премия Тьюринга (2002) — за создание криптосистемы RSA.
• Премия Париса Канеллакиса (1996) — за вклад в теоретическую информатику.
• Член Национальной академии наук США (2002).
• Член Американской академии искусств и наук (2006).
• Член Ассоциации вычислительной техники (ACM) (2002).

Интересные факты

• Адлеман известен своим чувством юмора. В 1999 году он опубликовал статью «Go To Statement Considered Harmful» (в ответ на знаменитую статью Эдсгера Дейкстры), где иронично защищал оператор безусловного перехода.
• В 2003 году он вместе с коллегами создал первый в мире «молекулярный компьютер» на основе ДНК, способный решать простые логические задачи.
• Адлеман является автором нескольких научно-популярных книг и статей, в которых объясняет сложные концепции доступным языком.
• В 2018 году он объявил о завершении своей академической карьеры и уходе на пенсию, однако продолжает заниматься консультированием и популяризацией науки.

Критика и ограничения

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

ДНК-вычисления, предложенные Адлеманом, пока остаются в основном экспериментальной областью. Основные проблемы — высокая стоимость синтеза ДНК, низкая точность биохимических реакций и сложность масштабирования. Практическое применение ограничено решением узкого круга задач.

Источники

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems». Communications of the ACM.
• Adleman, L. M. (1994). «Molecular Computation of Solutions to Combinatorial Problems». Science.
• Adleman, L. M., & Huang, M. D. (1992). «Primality Testing and Two Dimensional Abelian Varieties over Finite Fields». Springer.
• Премия Тьюринга: биография Леонарда Адлемана (ACM).
• Национальная академия наук США: профиль Леонарда Адлемана.