Деррик Генри Лемер¶

Деррик Генри Лемер (англ. Derrick Henry Lehmer; 23 февраля 1905, Беркли, Калифорния — 22 мая 1991, там же) — американский математик, известный работами в области теории чисел, вычислительной математики и криптографии. Внёс значительный вклад в развитие алгоритмов для проверки простоты чисел, факторизации и построения генераторов псевдослучайных чисел. Лемер разработал ряд тестов простоты (включая тест Люка — Лемера), а также создал один из первых механических компьютеров для решения теоретико-числовых задач.

¶Биография

Деррик Генри Лемер родился в семье математика Деррика Нормана Лемера (1867—1938), который был известен работами по теории чисел и последовательностям. С детства проявлял интерес к математике и механике. В 1927 году окончил Калифорнийский университет в Беркли, где получил степень бакалавра. Затем продолжил обучение в Чикагском университете, где в 1930 году защитил докторскую диссертацию под руководством Леонарда Юджина Диксона. Тема диссертации была связана с асимптотическими оценками для некоторых арифметических функций.

В 1930—1931 годах Лемер работал в Стэнфордском университете, а затем переехал в Брауновский университет (Провиденс, Род-Айленд), где преподавал до 1940 года. В этот период он начал разрабатывать механические устройства для вычислений, в частности, для факторизации чисел. В 1940 году вернулся в Калифорнийский университет в Беркли, где проработал до выхода на пенсию в 1972 году. Во время Второй мировой войны Лемер участвовал в проектах по криптоанализу, сотрудничая с правительственными организациями США.

¶Научные достижения

¶Тесты простоты

Лемер известен прежде всего разработкой тестов простоты, основанных на последовательностях Люка. Совместно с Эдуардом Люка он создал тест Люка — Лемера для проверки простоты чисел Мерсенна (чисел вида \(2^p - 1\), где \(p\) — простое). Этот тест остаётся основным методом для поиска больших простых чисел Мерсенна. Лемер также обобщил тест на другие типы чисел, такие как числа Ферма и числа Прота.

В 1927 году Лемер опубликовал работу, в которой предложил алгоритм для проверки простоты чисел, основанный на вычислении определённых рекуррентных последовательностей. Этот алгоритм лёг в основу современных тестов простоты, используемых в криптографии.

¶Факторизация

Лемер внёс вклад в разработку методов факторизации больших чисел. Он создал механический факторизатор — устройство, которое использовало вращающиеся шестерни для перебора делителей. Это устройство позволяло находить делители чисел длиной до 10–12 десятичных знаков. Впоследствии Лемер разработал электронные алгоритмы факторизации, включая метод квадратичного решета, который стал предшественником современного метода решета числового поля.

¶Генераторы псевдослучайных чисел

Лемер предложил один из первых алгоритмов генерации псевдослучайных чисел — линейный конгруэнтный генератор (ЛКГ). В 1949 году он опубликовал работу, в которой описал метод, основанный на рекуррентной формуле: \[ X_{n+1} = (a \cdot X_n + c) \mod m, \] где \(a\), \(c\) и \(m\) — целые числа. Этот метод стал основой для многих генераторов, используемых в компьютерных симуляциях и криптографии.

¶Криптография

Во время Второй мировой войны Лемер работал над методами взлома шифров, в частности, немецкой шифровальной машины «Энигма». Он разработал алгоритмы для анализа частотности и поиска ключей. После войны его работы по теории чисел нашли применение в криптографии с открытым ключом, в частности, в алгоритме RSA.

¶Вычислительные устройства

Лемер был одним из пионеров в создании специализированных вычислительных машин. В 1930-х годах он построил механический компьютер для факторизации чисел, который назывался «факторизатор Лемера». Устройство состояло из системы зубчатых колёс и позволяло автоматически перебирать делители. В 1940-х годах он перешёл к электронным вычислениям, используя реле и лампы.

В 1950-х годах Лемер разработал программу для вычисления простых чисел на компьютере IBM 701. Он также участвовал в создании первых компьютерных библиотек для теории чисел.

¶Публикации и наследие

Лемер опубликовал более 100 научных статей и несколько книг, включая «A Guide to Tables in the Theory of Numbers» (1941) и «Computer Programming and Numerical Analysis» (1961). Его работы оказали влияние на развитие вычислительной теории чисел, криптографии и компьютерной алгебры.

В честь Лемера названы:

• Последовательность Лемера — рекуррентная последовательность, используемая в тестах простоты.
• Числа Лемера — числа, связанные с последовательностями Люка.
• Премия Лемера — награда, присуждаемая Американским математическим обществом за выдающиеся работы в области теории чисел.

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

• Лемер был одним из первых, кто применил компьютеры для поиска простых чисел. В 1952 году он нашёл простое число Мерсенна \(2^{521} - 1\), которое на тот момент было самым большим известным простым числом.
• Он был страстным коллекционером математических таблиц и книг. Его личная библиотека насчитывала более 10 000 томов.
• Лемер известен тем, что разработал алгоритм для вычисления числа \(\pi\) с высокой точностью, используя метод Монте-Карло.

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

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

¶Источники

• Lehmer, D. H. (1949). «Mathematical methods in large-scale computing units». Proceedings of the Second Symposium on Large-Scale Digital Calculating Machinery.
• Lehmer, D. H. (1951). «On the factorization of large numbers». Bulletin of the American Mathematical Society.
• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms.
• Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective.
• «Derrick Henry Lehmer» (1991). Biographical Memoirs of the National Academy of Sciences.