Рожков_Ниссенбаум_ТЧМК_лекции

7.4. Числа Мерсенна.

Теорема 1

Если число вида p=aⁿ—1 – простое 1)a – четное;

2) n – простое.

Доказательство:

Четность а очевидна, так как иначе р было бы четным, а значит, составным.

Допустим, что n – не простое n=mk. Тогда

=a^k⁽^m^—1)+a^k⁽^m^—2)+…+a^k+1Z.

Тогда (a^k—1)\(aⁿ—1), значит р – не простое число. Предположение неверно, значит верно обратное.

□

Простые числа вида M_p=2^p—1, где р – простое число, называются числами Мерсенна.

Теорема 2

Число вида M_p=2^p—1, где р>2 – простое число, является простым в последовательности, определенной равенствамиu₀=4, u_i₊₁=(u_i²—2) mod M_p, выполняется u_p_—2≡0(mod M_p).

■

Из Теорем 1 и 2 следует

Тест Лукаса-Лемера для чисел Мерсенна

Вход: Число Мерсенна M_n=2ⁿ—1.

Ш.1. Пробными делениями проверить, имеет ли n делители между «2» и . Если имеет, идти на Выход с сообщением «M_n – составное число».

Ш.2. Задать u=4.

Ш.3. n—2 раза вычислить u=(u²—2) mod M_n.

Ш.4. Если u=0, то «M_n – простое число», иначе «M_n – составное число».

Выход.

В настоящее время особое внимание уделяется двойным числам Мерсенна MM_p=2^Mp –1, например 7=M₃=MM₂. Алгоритм построения таких чисел следующий: сначала строится сравнительно небольшое простое число Мерсенна M_p, а затем по нему – двойное число Мерсенна MM_p, которое проверяется на простоту тестом Лукаса-Лемера минуя первый шаг.

Аналогично строятся тройные и т.д. числа Мерсенна. Например, тройным числом Мерсенна является 127=M₇=MMM₂.

Не для всех чисел Мерсенна существуют двойные и тройные числа. Например, MM₁₃ не является простым.

Первыми простыми числами Мерсенна являются M₂=3, M₃=7, M₅=31, M₇=127, M₁₃=8191, M₁₇, M₁₉, M₃₁.

На данный момент (2007 г.) не доказана конечность или бесконечность количества простых чисел Мерсенна.

Содержание