Монтгомери, Питер
Питер Лоренс Монтгомери (25 сентября 1947[1], Сан-Франциско, Калифорния, США — 18 февраля 2020, Pong[d], Пхаяу, Таиланд[2][3]) — американский математик, известный благодаря своим публикациям по математической криптографии. Входил в исследовательскую группу криптографов в Microsoft Research. Ранее работал программистом в System Development Corporation[4]. Особенно значительный вклад внёс в метод факторизации с помощью эллиптических кривых. В 1992 году получил степень Ph.D. Его число Эрдёша равно 1.
Общие сведения
| Питер Монтгомери | |
|---|---|
| англ. Peter Montgomery | |
| Дата рождения | 25 сентября 1947[1] |
| Место рождения | |
| Дата смерти | 18 февраля 2020 (72 года) |
| Место смерти | |
| Страна | |
| Научная сфера | теория чисел |
| Место работы | |
| Образование | |
| Научный руководитель | David G. Cantor[d] |
Биография
Питер Лоренс Монтгомери родился 25 сентября 1947 года в Сан-Франциско[2]. В 1967 году он стал Putnam Fellow[2]. В 1969 году получил степень бакалавра, а в 1971 году — степень магистра в Калифорнийском университете в Беркли[2]. С 1972 года работал программистом в System Development Corporation (SDC)[2]. В 1992 году получил степень доктора философии (PhD) в Калифорнийском университете в Лос-Анджелесе (UCLA) под руководством Дэвида Г. Кантора[2][4]. С 1998 по 2014 год работал в исследовательской группе криптографии Microsoft Research[2]. Скончался 18 февраля 2020 года в Понге (Таиланд)[2].
Научный вклад
Алгоритмы умножения и обращения
В 1985 году Питер Монтгомери предложил алгоритм модульного умножения, который позволяет быстро выполнять умножение двух целых чисел по модулю. Основная идея метода заключается в замене вычислительно сложной операции деления на более быстрые побитовые сдвиги и сложения путём перевода чисел в специальное «представление Монтгомери»[5]. Алгоритм особенно эффективен при выполнении серии последовательных умножений (например, при модульном возведении в степень) и является важным компонентом криптосистем с открытым ключом[6].
Другим значимым вкладом учёного стал алгоритм одновременного обращения, известный как «трюк Монтгомери» (англ. Montgomery's trick или batch inversion). Этот метод позволяет эффективно вычислять мультипликативные обратные элементы по модулю для нескольких чисел одновременно[7]. Алгоритм заменяет несколько ресурсоёмких операций нахождения обратного элемента на одну такую операцию и несколько более быстрых модульных умножений (для инвертирования n элементов требуется одна операция инвертирования и около 3n умножений). Данный подход широко применяется для ускорения вычислений в криптографии[8][7].
Криптография на эллиптических кривых
В 1987 году Питер Монтгомери внёс значительный вклад в криптографию на эллиптических кривых, предложив специальную форму эллиптической кривой, получившую название «кривая Монтгомери». Она описывается уравнением [9][10].
Для вычислений на таких кривых учёный разработал алгоритм скалярного умножения, известный как «лестница Монтгомери» (англ. Montgomery ladder). Алгоритм отличается высокой вычислительной эффективностью, так как позволяет проводить операции, используя только x-координату точки. Кроме того, он обеспечивает устойчивость к атакам по сторонним каналам: за счёт выполнения одной и той же последовательности операций независимо от значения секретного ключа достигается константное время выполнения[11][12].
Факторизация целых чисел
Питер Монтгомери внёс значительный вклад в развитие алгоритмов факторизации целых чисел. Он усовершенствовал метод факторизации с помощью эллиптических кривых (ECM), предложив в своей диссертации 1992 года использовать методы быстрого преобразования Фурье (FFT) для ускорения второй фазы этого алгоритма[13].
Кроме того, учёный разработал модификацию метода квадратичного решета с использованием нескольких полиномов (Multiple Polynomial Quadratic Sieve, MPQS). Этот подход позволяет поддерживать значения полиномов небольшими, что существенно повышает эффективность процесса просеивания[14].
Память
В феврале 2020 года команда исследователей посвятила памяти Питера Монтгомери успешную факторизацию числа RSA-250[15]. В апреле 2020 года факультет математики Калифорнийского университета в Лос-Анджелесе (UCLA) опубликовал мемориальную статью, посвящённую учёному[4]. В апреле 2021 года статья памяти Монтгомери была опубликована в журнале Notices of the American Mathematical Society[16].