Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0.

 

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

 

(натуральные числа) можно записать в виде сумм степеней некоторых

 

иррациональных чисел. Пусть

w=2 +

3 и v

=2 -

3 . Докажем индукцией

 

 

по n, что

w2n

+v 2n

=Sn .

 

 

Очевидно,

 

w + v

 

=S 0 . Предположим, что

w2n -1

+v2n -1

=S n-1 .

 

Возводя в квадрат обе части равенства, получаем

 

w2n

+ 2(wv )

2n -1

+ v 2n

= S 2

n-1 . Поскольку wv

 

=1, то следует соотношение

 

n

n

w 2 + v 2

=S 2 n -1 -2 , что, по определению, дает S .

 

n

Описание алгоритма.

 

1. Ввод p. Если p < 3, то выход (не удовлетворяет условиям алгоритма).

 

2. Вычисление M(p) = 2p - 1 (программная реализация операции

 

возведения в степень рассмотрена в приложении 1).

 

3. Установить S = 4.

 

4. Для

"i =1, p -2

вычислить S = (S2 mod M(p)) - 2 (под операцией mod

 

подразумевается взятие остатка от деления левого параметра правым).

 

5. Если S mod (M(p)-1) º 0, то M(p) является простым, иначе составным. Выход.

 

Пример 1.8. Необходимо проверить на простоту число M(p) = 2p - 1, где

 

p = 11 - простое.

 

Число Мерсенна равно M(p) = 2p -1 = 211 -1 = 2047. Переменная цикла i

 

(из пункта 4) будет принимать значения

i =1, 9 . Представим шаги работы

 

алгоритма на основе трассировочной табл. 1.8.

 

Таблица 1.8. Трассировочная таблица

 

 

Шаг, i Условие: i£p-2   S2 mod M   (S2 mod M) - 2 Условие: S mod Mº0? до цикла - - - Да: 1£11-2 нет Да: 2£11-2 нет Да: 3£11-2 нет Да: 4£11-2 нет Да: 5£11-2 нет Да: 6£11-2 нет Да: 7£11-2 нет Да: 8£11-2 нет Да: 9£11-2 нет   Нет: 10>11-2: Выход   -   Нет→ составное

В результате получаем, что число M(p) = 211 − 1 = 2047 является составным.

Пример 1.9. Необходимо проверить на простоту число M(p) = 2 p - 1, где

 

p = 13.

 

Число Мерсенна равно M(p) = 2 p - 1 = 213 - 1 = 8191. Переменная цикла

 

i (из пункта 4) будет принимать значения

i =1, 11 . Представим шаги работы

 

алгоритма на основе трассировочной табл. 1.9:

 

Таблица 1.9. Трассировочная таблица

 

Шаг, i Условие: i£p-2   S2 mod M   (S2 mod M) - 2 Условие: S mod Mº0? до цикла - - - да: 1£13-2 нет да: 2£13-2 нет да: 3£13-2 нет да: 4£13-2 нет да: 5£13-2 нет да: 6£13-2 нет да: 7£13-2 нет да: 8£13-2 нет да: 9£13-2 нет да: 10£13-2 нет да: 11£13-2 да   нет: 12>13-2: Выход   -     да→простое

В результате получаем, что число M(p) = 213 − 1 = 8191 является простым.

 

Вопросы для самопроверки.

 

1. Что такое число Мерсенна?

 

2. Если p является составным или простым, то что можно сказать о числе M(p)?

 

3. Почему, если p является составным, то M(p) - составное?

 

4. Поясните суть теста Люка-Лемера.

 

5. Какие ограничения накладываются на входные значения теста Люка-Лемера, в том числе с учетом программной реализации на ЭВМ?

6. Сколько итераций может выполняться тест?

 

7. При каком условии пронимается решение о простоте числа M(p)?

 

8. Какая ошибка может случиться при проверке большого числа на простоту?

 

9. Для какого максимального числа p можно проверить простоту M(p) с помощью арифметики, встроенной в ЭВМ?

10. Какие математические операции используются в тесте Люка-Лемера?