X Международная студенческая научная конференция Студенческий научный форум - 2018

Несколько столетий шла погоня за простыми числами. Математики старались открыть самое большое их известных простых чисел. Можно было бы выбрать несколько больших чисел, не имеющих очевидных делителей, например 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ, как мы вскоре убедимся, не очень эффективен. Теперь эта погоня утихла, она идет только в одном направлении, оказавшемся удачным.

Простые числа Мерсенна являются простыми числами специального вида:

М_р = 2p– 1,

где р — другое простое число (в честь французского монаха Мерена Мерсенна (1588–1648), который долго и упорно занимался проблемой совершенных чисел).

Если вычислять числа для различных простых чисел р, то видно, что не все они оказываются простыми. Например,

М₂ = 2² — 1 = 3 = простое,

М₃ = 2³ — 1 = 7 = простое,

М₅ = 2⁵ — 1 = 31 = простое,

М₇ = 2⁷ — 1 = 127 = простое,

М₁₁ = 2¹¹ — 1 = 2047 = 23 89.

Способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел Мp для различных простых чисел р.

М₁₂₇ = 170141183460469231731687303715884105727

Простые числа Мерсенна, меньшие этого числа, задаются значениями р, указанными выше, а также значениями

р = 61, р = 89, р = 107.

Эти 12 простых чисел Мерсенна были вычислены с помощью только карандаша и бумаги, а для вычисления следующих использовались механические настольные счетные машины. Результаты были неутешительными, среди них не оказалось новых простых чисел Мерсенна [2].

Далее задача была переложена на плечи ЭВМ. Создание все более высокопроизводительных ЭВМ дало возможность продолжить поиск новых простых чисел Мерсенна. Д. X. Лемер установил, что значения

р = 521, р = 607, р = 1279, р = 2203, р = 2281

дают простые числа Мерсенна. Дальнейшие поиски также увенчались успехом. Ризель (1958) показал, что р = 3217, дает простое число Мерсенна, а Гурвиц (1962) нашёл еще два таких значения:

р = 4253, р = 4423.

Огромного успеха добился Гиллельс (1964), который нашел простые числа Мерсенна, соответствующие значениям:

р = 9689, р = 9941, р = 11213.

Итак, общее количество составило 23 простых числа Мерсенна, и, так как мощности ЭВМ продолжают увеличиваться [1].

Над поиском максимально больших простых чисел в своё время бились Катальди, Декарт, Ферма, Мерсенн, Лейбниц, Эйлер и многие другие математики. Были созданы многие разделы теории чисел (малая теорема Ферма и квадратичный закон взаимности). В 20-м веке этот поиск привёл к созданию новых быстрых способов перемножения целых чисел: в 1968 году математик Фолкер Штрассен придумал, как использовать для этого быстрое преобразование Фурье. Сейчас этот метод известен как алгоритм Штрассена, его улучшенная версия используется в программном обеспечении GIMPS и повсеместно для быстрого перемножения матриц [2].

На данный момент самое большое известное простое число имеет 3376 цифр.

Список используемых источников

1. Простые числа. [Электронный ресурс] – Режим доступа: http://www.tinlib.ru/matematika/priglashenie_v_teoriyu_chisel/p4.php

2. Числа Марсенна. [Электронный ресурс] – Режим доступа: https://wiki2.org/ru/Числа_Мерсенна

Код для цитирования: Скопировать