17567

Проверка чисел на взаимную простоту: расширенный алгоритм Эвклида, малая теорема Ферма, тест Рабина-Миллера

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа №3.1 Тема: Проверка чисел на взаимную простоту: расширенный алгоритм Эвклида малая теорема Ферма тест Рабина Миллера. Цель: Ознакомиться с процедурой нахождения наибольшего общего делителя использующей расширенный алгоритм Эвклида. Изучить

Русский

2013-07-04

250 KB

54 чел.

Лабораторная работа №3.1

Тема: Проверка чисел на взаимную простоту: расширенный алгоритм Эвклида, малая теорема Ферма, тест Рабина-Миллера.

Цель: Ознакомиться с процедурой нахождения наибольшего общего делителя, использующей расширенный алгоритм Эвклида. Изучить принцип проверки целых чисел на простоту с применение тестов Ферма и Миллера-Рабина.

Задание

  1.  Рассмотреть процедуру проверки чисел на простоту с помощью тестов Ферма и Миллера-Рабина.
  2.  Рассмотреть схему нахождения наибольшего общего делителя с использованием расширенного алгоритма Эвклида.
  3.  Реализовать программно тест Ферма. Проверить на простоту целые числа в диапазоне [3,200].
  4.  Реализовать программно тест Миллера-Рабина. Проверить на простоту целые числа в диапазоне [3,200]. Сравнить результат с полученным в задании 3.
  5.  Реализовать программно расширенный алгоритм Эвклида. Найти наибольший общий делитель чисел, заданных преподавателем. Сделать вывод об их взаимной простоте.

Теоретические сведения

Нахождение наибольшего общего делителя

Алгоритм Эвклида

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

Во-первых, мы говорим, что целое число b делит целое число а, если существует еще одно целое число с такое, что а = bс. В этом случае мы говорим также, что b является делителем или множителем, числа а, а а, в свою очередь, - кратным, числа b. Все это - различные способы сказать одно и то же. Разумеется, определить, является ли b делителем числа а, можно, подсчитав остаток от деления а на b и проверив, равен ли он нулю.

Пусть а и b - натуральные числа. Наибольший общий делитель чисел а и b - это наибольшее целое число d, на которое и а, и b делятся; тогда мы пишем d = НОД(а, b). Если НОД(а, b) = 1, то мы называем числа а и b взаимно простыми. Определение наибольшего общего делителя подсказывает следующий алгоритм его вычисления. Если числа а и b заданы, то найдем все положительные делители числа а и все положительные делители числа b. Выберем все числа, входящие в оба множества, и возьмем наибольшее из них. Оно и будет наибольшим общим делителем. Эта процедура совсем проста, однако, как мы увидим далее, она чрезвычайно неэффективна при больших а и b. Проблема состоит в том, что неизвестно ни одного простого алгоритма разложения целых чисел на множители.

К счастью, наибольший общий делитель можно подсчитать и другим, весьма эффективным способом, описанным Эвклидом в предложениях 1 и 2 книги VII своих «Элементов». Алгоритм Эвклида действует следующим образом. Разделим а на b с остатком; назовем этот остаток r1. Если r1 ≠ 0, то разделим b на r1 с остатком; пусть r2 - остаток второго деления. Аналогично, если r2 ≠ 0, то разделим rl на r2 и получим новый остаток r3. Таким образом, i-ый цикл алгоритма состоит из одного деления с остатком, причем делимое равно остатку, полученному в (i-2)-ом цикле, а делитель - остатку, полученному в (i - 1)-ом цикле. Цикл повторяется до тех пор, пока мы не получим нулевого остатка; наименьший ненулевой остаток является наибольшим общим делителем чисел а и b.

Применим алгоритм Эвклида для вычисления наибольшего общего делителя чисел 1234 и 54. Деления с остатком выглядят так:

1234 = 54 × 22 + 46;

54 = 46 × 1 + 8;

46 = 8 × 5 + 6;

8 = 6 × 1 + 2;

6 = 2  × 3 + 0.

Последний ненулевой остаток равен 2, поэтому

НОД(1234,54) = 2.

Отметим, что непoлные частные не принимают непосредственного участия в подсчете наибольшего общего делителя. Опишем теперь алгоритм Эвклида.

Алгоритм Эвклида

Ввод: натуральные числа а и b, а ≥ b.

Вывод: наибольший общий делитель чисел а и b.

Шаг 1. Положить А = а и R = В = b.

Шаг 2. Заменить значение R остатком от деления А на В и перейти к шагу 3.

Шаг 3. Если R = 0, то сообщить: «наибольший общий делитель чисел а и b равен В, и остановиться; в противном случае перейти к шагу 4.

Шаг 4. Заменить значение А на значение В, значение В на значение R и возвратиться к шагу 2.

Таким образом, для вычисления наибольшего общего делителя нам необходимо лишь выполнить несколько делений с остатком. Но почему наибольший общий делитель совпадает с последним ненулевым остатком в последовательности делений? Да и вообще, почему в последовательности остатков всегда появится нуль? Заметим, что если бы нуль не появлялся, то процедура никогда бы не остановилась.

Начнем со второго вопроса. Тем самым мы докажем, что

алгоритм всегда завершает работу. Предположим, что для того, чтобы найти наибольший общий делитель чисел а и b, мы проделали следующие деления с остатком:

а = bql + rl и 0  rl < b;

b = rlq2 + r2 и 0  r2 < rl;

rl = r2q3 + r3 и 0 ≤ r3 < r2;

r2 = r3q4 + r4 и 0 ≤ r4 < r3;

............ . .. . ........... .

Забудем на минуту про левый столбец. В правом столбце стоит последовательность остатков. Заметим, что в ней всякий остаток меньше предыдущего, а также, что все остатки неотрицательны. Переписав неравенства друг за другом, мы получаем цепочку

b > rl > r2 > r3 . . . ≥ 0.                                                         (1)

Поскольку между b и нулем есть лишь конечное число целых чисел, последовательность остатков не может продолжаться бесконечно. Однако в конце ее может стоять только нуль, а значит, алгоритм наверняка остановится.

С помощью рассуждения из предыдущего параграфа можно получить верхнюю оценку на число делений, необходимое для вычисления наибольшего общего делителя. Вернемся к неравенствам (1). Каждое число в последовательности строго меньше предыдущего. Поэтому наибольшее возможное значение остатка в каждом делении на единицу меньше значения остатка на предыдущем делении. Если бы в каждом цикле это наибольшее возможное значение достигалось, то для получения нулевого остатка нам потребовалось бы b делений. Ясно, что это и есть наихудший возможный случай. Поэтому при применении алгоритма Эвклида к паре чисел а ≥ b число делений не превосходит b.

На самом деле, несложно показать, что при b > 3 число делений всегда меньше b. Зафиксируем число n. Тогда задачу лучше переформулировать так: для каких наименьших взаимнопростых а и b вычисление НОД(а, b) требует n делений? Заметим, что для того, чтобы числа а и b были минимально возможными, частные на каждом шаге тоже должны быть минимально возможными. Если теперь предположить, что делитель меньше делимого, то ясно, что наименьшее возможное частное двух целых чисел равно 1. Предположим, что мы выполнили n делений до получения нулевого остатка. Тогда последовательность остатков имеет вид

b > rl > r2 > r3 . . . ≥ 0.

Мы уже видели, однако, что в наихудшем возможном случае все неполные частные равны 1. Запишем теперь все деления, начиная с последнего. В силу взаимной простоты чисел мы получаем

rn-1 = 1;

rn-3 = rn-2×1 +1;

rn-4 = rn-3×1 +rn-2;

………………

a = b×1 + 1.

Вот как выглядит последовательность остатков при n = 10:

34, 21, 13, 8, 5, 3, 2, 1, 1, 0.

Значит, наименьшая пара взаимно простых чисел а и b, для подсчета наибольшего общего делителя которых необходимо 10 делений с остатком, это а = 34 и b = 21. Заметьте, что хотя число b = 21 и наименьшее, все равно оно больше, чем n = 10.

Доказательство корректности алгоритма Эвклида

Мы показали, что алгоритм обязательно остановится. Действительно, он не может выполнить больше делений с остатком, чем меньшее из двух введенных чисел. Но почему последний ненулевой остаток в точности равен наибольшему общему делителю? Чтобы это понять, нам понадобится один вспомогательный результат из тех, что математики называют леммами.

Лемма. Пусть а и b – натуральные числа. Предположим, что существуют такие целые числа g и s, при которых а = bg + s. Тогда НОД(а, b) = НОД(b, s).

Воспользуемся этой леммой и покажем, что последний ненулевой остаток в алгоритме Эвклида действительно равен наибольшему общему делителю. Применяя алгоритм к целым числам а ≥ b > 0 и предполагая, что остаток после n-го деления равен нулю, имеем

а = bql + rl и 0 ≤ rl < b;

b = rlq2 + r2 и 0 ≤ r2 < rl;

rl = r2q3 + r3 и 0 ≤ r3 < r2;

r2 = r3q4 + r4 и 0 ≤ r4 < r3;

............ . .. . ........... .                                                  (2)

 rn-4 = rn-3qn-2 + rn-2 и 0 ≤ rn-2 < rn-3;

rn-3 = rn-2qn-1 + rn-1 и 0 ≤ rn-1 < rn-2;

rn-2 = rn-1qn-2 и rn-1 = 0.

 

На этот раз мы будем смотреть только на то, что происходит в левом столбце. Последнее равенство означает, что rn-2 делится на rn-1. Поэтому наибольший общий делитель этих двух чисел равен rn-1. Другими словами, НОД(rn-2, rn-1) = rn-1.

Теперь в действие вступает лемма. Применяя ее к предпоследнему равенству, мы заключаем, что

НОД(rn-3 ,rn-2) = НОД(rn-2, rn-1),

причем последняя величина, как мы видели, равна rn-1. Повторное применение леммы, на этот раз к предыдущему равенству, дает

НОД(rn-4 ,rn-3) = НОД(rn-3, rn-2),

что опять равно rn-1. Продолжая действовать таким же образом до вершины столбца, мы заключаем, что НОД(а, b) = rn-1, что требовалось доказать.

Расширенный алгоритм Эвклида

У алгоритма Эвклида, описанного в ранее, есть еще один вариант, более мощный. Мощный в данном случае не означает более быстрый. Достоинство нового варианта в том, что наибольший общий делитель - лишь часть выходных данных. Пусть а и b - натуральные числа, а d – их наибольший общий делитель. Расширенный алгоритм Эвклида подсчитывает не только d, но и два целых числа α и β таких, что

α×а + β×b = d.                                                                   (3)

Отметим, что  (за исключением нескольких тривиальных случаев) если α оказывается положительным, то β - отрицательное, и наоборот.

Лучше всего вычислять эти числа, добавив некоторые инструкции в обычный алгоритм Эвклида так, чтобы d, α и β подсчитывалисьались одновременно. Именно поэтому новая процедура называется расширенным алгоритмом Эвклида. Приводимый здесь вариант этого алгоритма принадлежит Кнуту, автору знаменитой книги «Искусство программирования>. Напомним, что алгоритм Эвклида состоит из последовательности делений с остатком. Наибольший общий множитель представляет собой последний ненулевой остаток в этой последовательности. Значит, нам надо найти способ записывать последний ненулевой остаток в виде (3).

Суть алгоритма Кнута в том, что нам не следует ждать, пока мы дойдем до последнего ненулевого остатка; вместо этого нам стоит записывать в таком виде каждый из получающихся остатков. Такие действия должны приводить, по-видимому, к большому количеству дополнительной работы. Как мы увидим позднее, это не совсем так.

Предположим, что для вычисления наибольшего общего делителя чисел а и b мы выполнили последовательность делений (2). Перепишем ее, сопровождая каждую операцию записью предполагаемого представления остатка:

а = bql + rl и rl = ax1 + by1;

b = rlq2 + r2 и r2 = ax2 + by2;

rl = r2q3 + r3 и r3 = ax3 + by3;

r2 = r3q4 + r4 и r4 = ax4 + by4;

............ . .. . ........... .                                                       (2)

rn-3 = rn-2qn-1 + rn-1 и rn-1 = axn-1 + byn-1;

rn-2 = rn-1qn-2 и rn = 0.

Числа x1,..., xn-1 и у1,... , уn-1 мы b хотим определить. Необходимую информацию удобно свести в таблицу:

Отметим прежде всего, что таблица начинается с двух строчек, которым в ней не следовало бы быть. Действительно, стоящие в первом столбце этих строк числа не являются остатками в каких-либо операциях деления. Мы даем этим строчкам номера -1 и 0, подчеркивая тем самым их «незаконность». Вскоре мы обоснуем их необходимость.

Что же мы хотим сделать? Мы хотим заполнить столбцы х и у. Предположим на минуту, что мы получили таблицу заполненной до некоторой, скажем до (j - 1)-ой, строки. Для заполнения j-ой строки необходимо прежде всего разделить rj-2 на rj-l. В результате получатся rj и qj - первые два элемента j-ой строки. Не будем забывать, что rj-2 = rj-lqj + rj и 0 ≤ rj < rj-l. Таким образом,

rj = rj-2 - rj-lqj.                                                                         (5)

Из строчек j - 1 и j - 2 мы можем взять значения xj-2, xj-l, yj-2 и yj-l. Можно записать

rj-2 = aхj-2 + bуj-2  и rj-l = aхj-l + byj-l.

Подставляя эти значения в (5), получаем

rj = (aхj-2 + byj-2) - (aхj-l + bуj-l)qj = a(хj-2 - qjхj-l) + b(yj-2 - qjyj-l).

Поэтому

xj = xj-2 - qjxj-l и yj = yj-2 - qjyj-l.

Заметим, что для вычисления хj и yj нам понадобились только частное qj и данные из двух строк таблицы, непосредственно предшествующих j-ой. Вот почему алгоритм Кнута такой эффективный. Для заполнения очередной строки достаточно знать две строчки, непосредственно предшествующие ей; все остальные строчки хранить не обязательно.

Итак, мы получили рекуррентную процедуру. Все, что необходимо - это научиться ее запускать. Именно для этого мы и добавили в таблицу две «незаконные» строки. Найти в них значения х и у очень просто. Придавая им тот же смысл, что и в остальных строках, мы должны получить

а = ax-l + by-l и b = ах0 + bу0.

Поэтому можно просто положить

x-l = 1, y-l = 0, х0 = 0 и у0 = 1,

и процедуру можно запускать. В результате цепочки делений с остатком мы получим равенство НОД(а, b) = rn-l и вычислим такие целые числа xn-l и yn-l, что

d = rn-l = axn-l + byn-l.

Значит α = xn-l и β = yn-l Заметим, что, зная а и d = rn-l, мы можем найти β по формуле

β = (d - aα)/b.

Поэтому достаточно вычислять только первые три столбца таблицы.

Приведем численный пример. Если а = 1234 и b = 54, то (полная) таблица выглядит так:

Поэтому α = -7, β = 160 и  (-7)×1234 + 160×54 = 2.

Пришло время разобраться, почему алгоритм дает правильный ответ и почему он завершает свою работу. Как и подразумевается названием, расширенный алгоритм Эвклида представляет собой просто алгоритм Эвклида из предыдущего параграфа, дополненный инструкциями для вычисления значений х и у. Поэтому он останавливается, и наибольший общий делитель составляет часть выходных данных. Кроме того, в каждой строке числа из столбцов х и у удовлетворяют равенству типа (3), в котором число d заменено остатком из соответствующей строки. В частности, равенство (3) выполняется, если в качестве β и α взять числа из столбцов х и у строки, отвечающей последнему ненулевому остатку.

Расширенный алгоритм Эвклида приводит к следующей теореме.

Теорема. Пусть d – наибольший общий делитель натуральных чисел а и b. Тогда существуют такие целые числа β и α, что:

α×а + β×b = d.

                                                             

Заметим, что пара чисел β и α , упомянутая в теореме, не единственная. На самом деле таких пар бесконечно много. Например, возьмем β и α , для которых α×а + β×b = d, и рассмотрим какое-нибудь целое k. Тогда, как несложно проверить,

(α + kb)×а + (β – kab = d.

Приложив столько усилий к вычислению β и α, разумно задаться вопросом, для чего эти числа могут понадобиться. Знание этих чисел необходимо для получения большого числа принципиально важных результатов, включая выбор ключей в системе шифрования RSA.

Проверка чисел на простоту

Простые числа необходимы для почти всех алгоритмов шифрования с открытым ключом, например:

  •  В RSA нам нужны простые числа р и q для определения парметра открытого ключа n = рq.
  •  В системе Эль-Гамаля необходимо простое число р и простое q.
  •  В криптосистеме, использующей эллиптические кривые, требуется эллиптическая кривая над конечным полем, порядок которой делится на большое простое число q.

Тестирование чисел на простоту можно выполнить с помощью довольно простых алгоритмов: теста Ферма или теста Миллера-Рабина.

Теорема Ферма

Теорему Ферма часто также называют «малой теоремой Ферма». Она гласит, что если р – простое число, а а – любое целое, то р делит ар – а. Частный случай этой теоремы известен уже сотни лет, но Ферма был первым, кто доказал теорему в полной общности. Начнем с перевода формулировки теоремы на язык сравнений. Теорема Ферма. Пусть р - положительное простое число и а - целое; тогда

ар = а (mod р).

Чтобы доказать теорему с помощью математической индукции, нам нужно найти утверждение Р(n), к которому можно применить метод. Вот оно:

np = n (mod р)

для натурального n.

Отметим, что утверждение Р(n) говорит о верности сравнения только для натуральных чисел, т.е. положительных целых n. Таким образом, мы не доказываем теоремы в полной общности. Однако, любое целое число сравнимо по модулю р с каким-то неотрицательным целым, меньшим р. Поэтому достаточно проверить теорему для 0 ≤ а ≤ р - 1. В частности, теорема будет доказана, если показать справедливость утверждений Р(n) для всех n ≥ 1.

Разумеется, Р(l) истинное высказывание, поскольку 1p = 1. Таким образом, база индукции выполнена. Для индуктивного перехода от Р(n) к Р(n + 1) нам нужно выявить связь между этими утверждениями. Она обеспечивается биномиальной теоремой. Доказательство становится намного проще, если мы выделим из него вспомогательное утверждение, в действительности являющееся вариантом бинома Ньютона для целых чисел по модулю р.

Лемма. Пусть р - положительное простое число, а и b - целые; тогда

(а + b)p == аp + bp (mod р).

Доказательство леммы. Как следует из формулы бинома Ньютона,

Таким образом, для доказательства леммы достаточно показать, что

А это, в свою очередь, будет немедленно следовать из делимости биномиальных коэффициентов  на р при 1 ≤ i ≤ р - 1. По определению,

Поскольку биномиальные коэффициенты - целые числа, знаменатель дроби должен делить числитель. Кроме того, если 1 ≤ i ≤ р - 1, то р не является делителем числа i!. Поэтому сомножитель р из числителя дроби не может сократиться ни с каким сомножителем знаменателя. Значит, знаменатель обязан делить произведение (р - 1) . . . (р - i + 1). Отсюда  -  число кратное р, что и требовалось доказать.

Теперь можно вернуться к доказательству теоремы Ферма. Предположение индукции: np = n (mod р) для некоторого натурального n.

В качестве индуктивного перехода нам нужно показать, что (n + l)p = n + 1 (mod р). По лемме

(n + 1)p = np+1p = np+1 (mod p).

По предположению индукции, np можно заменить на n. Проделав это, мы получаем: (n+l)p = n + 1 (mod р), что мы и хотели показать.

Согласно теореме, если р простое число, а а –  целое, то аp = а (mod р). Предположим теперь, что а не делится на р.

Тогда, ввиду простоты р, числа а и р взаимно просты, и из теоремы обратимости следует, что а обратимо по модулю р. Пусть а* – обратный к а элемент. Умножая на а* сравнение аp = а (mod р), имеем

а*×а×ap-1 = а*×а (mod р).

Но а*×а = 1 (mod р), и окончательно ap-1 = 1 (mod р). Именно этот вариант уравнения из теоремы Ферма мы будем использовать в дальнейшем чаще всего. Для будущих ссылок сформулируем его в виде утверждения.

Теорема Ферма. Пусть р – положительное простое число, а а - целое, не делящееся на р; тогда ap-1 = 1 (mod р).  

Заметим, что тест Ферма может лишь убедить нас в том, что число n имеет делители, но не в состоянии доказать его простоту. Действительно, рассмотрим составное число n = 11 × 13 = 341, а основание в тесте Ферма выберем равным 2. Тогда 2340 = 1 mod 341, в то время как число 341 не простое. В этом случае говорят, что nпсевдопростое число (в смысле Ферма) по основанию 2. Существует бесконечно много псевдопростых чисел по фиксированному основанию, хотя они встречаются реже, чем простые. Подводя итог сказанному, выпишем алгоритм теста Ферма:

Если на выходе этого алгоритма напечатано «составное, а», то мы с определенностью можем заявить, что число п не является простым, и что а свидетельствует об этом факте, т. е. чтобы убедиться в истинности высказывания, нам достаточно провести тест Ферма по основанию а. Такое а называют свидетелем того, что п составное. Если же в результате работы теста мы получим сообщение: «правдоподобно простое», то можно заключить: п — составное с вероятностью ≤1/2k.

Возьмем, например, число n = 43 040 357. Оно является составным, что можно проверить тестом Ферма по основанию а = 2. Действительно, 243040356 (mod43040357) = 9888212 ≠ 1.

В качестве следующего примера рассмотрим число п = 2192 — 264 — 1. Алгоритм выдаст на печать «правдоподобно простое», поскольку мы не сможем найти свидетеля обратному. Фактически, это число является простым, так что нет ничего удивительного в том, что мы не смогли найти свидетеля его делимости.

Тем не менее, существуют составные числа, относительно которых тест Ферма выдаст ответ «правдоподобно простое», для всех взаимно простых с п оснований а. Такие числа называются числами Кармайкла. К сожалению, их бесконечно много. Первые из них — это 561, 1105 и 1729. Числа Кармайкла обладают следующими свойствами:

- они нечетны,

- имеют по крайней мере три простых делителя,

- если р делит число Кармайкла n, то р - 1 делит n - 1.

Чтобы получить представление об их распределении, посмотрим на числа, не превосходящие 1016. Среди них окажется примерно 2,7×1014 простых чисел, но только 246683≈2,4×105 чисел Кармайкла.

Следовательно, они встречаются не очень часто, но и не настолько редко, чтобы их можно было игнорировать.

Тест Миллера - Рабина

Из-за существования чисел Кармайкла тест Ферма применяют крайне неохотно. Существует модификация теста Ферма, называемая тестом Миллера - Рабина, которая обходит проблему составных чисел, для которых не находится свидетеля. Это не означает, что легко найти свидетеля для каждого составного числа, это значит, что такой свидетель в принципе должен быть. Кроме того, тест Миллера-Рабина принимает составное число за простое с вероятностью 1/4 для любого случайного основания а. Поэтому многократное повторение теста позволяет уменьшить вероятность ошибки до любой наперед заданной величины. Приведем тест Миллера – Рабина на псевдокоде.

 

Рассмотрим. В чем заключается тест Миллера.

Пусть n > 0 – нечетное целое. Выберем целое число b, удовлетворяющее неравенству 1 < b < n - 1, и назовем его основанием. Поскольку n - нечетное, n - 1 должно быть четным числом. Первый шаг теста Миллера состоит в определении такого показателя k ≥ 1, для которого n-1 = 2kq, где q не делится на 2. Иначе говоря, мы должны найти наибольшую степень двойки, делящую n - 1, и соответствующее частноe q.

Далее тест вычисляет вычеты по модулю n у следующей последовательности степеней:

bq, b2q, ..., , .

Разберемся, какими свойствами обладает эта последовательность в случае простого n. Итак, пока не будет оговорено особо, n - простое число. Теорема Ферма говорит нам, что

= bn-1 = 1 (mod n).

3начит, если n - простое, то последний вычет в последовательности всегда равен 1. Конечно, единица среди вычетов может встретиться и раньше. Пусть j - наименьший показатель, для которого  = 1 (mod n). Если j ≥ 1, то

 -1 = (- 1) (+ 1) .

По предположению, число n - простое и (так как оно делит разность квадратов  -1) делит либо (- 1), либо (+ 1). С другой стороны, в силу выбора показателя j, число n не может делить - 1. Остается только одна возможность: n - делитель числа + 1, т.е.  = -1 mod n .

Эти рассуждения показывают, что в случае простого n среди последовательности степеней bq, b2q,..., ,  найдется по крайней мере одна, сравнимая с -1 по модулю n. Хорошо, но не слишком. Дело в том, что наше рассуждение основывалось на предположении: j > 0. Если j = 0, то bq = 1 (mod n). А у нас нет простого способа разложения числа bq - 1 на множители, поскольку q нечетно. Значит, если n – простое, то с последовательностью вычетов по модулю n,  должно произойти одно из двух: либо первый же вычет равен 1, либо среди них появится n -1. В противном случае (не будет ни того, ни другого) число n должно быть составным.

Последовательность вычетов, используемая в тесте Миллера, довольно легко вычисляется, потому что каждый вычет (за исключением первого) –  квадрат предыдущего. Отсюда вытекает, что как только в последовательности вычетов по модулю n встретится n - 1, все остальные вычеты будут равны 1.

у нас появился еще один тест, который позволяет нам показать разложимость данного числа, но работающий только при удачном стечении обстоятельств. Тем не менее, тест Миллера более эффективен, нежели тест Ферма. Чтобы понять почему, заметим, что последовательность степеней, выписанная для псевдопростого n по основанию b, должна иметь член, сравнимый с 1 по модулю n. А так как n не простое, то существует хороший шанс, что этой степени не будет предшествовать другая, сравнимая с n - 1. В этом случае тест Миллера обнаружит разложимость числа. Приведем алгоритм, реализующий тест Миллера.

Тест Миллера

Ввод: нечетное натуральное n и основание b, где 1 < b < n-1.

Вывод: одно из двух сообщений: «n составное» или «ничего определенного сказать нельзя».

Шаг 1. Последовательно делим n -1 на 2 пока не получим нечетного частного. В результате найдем положительное целое k и нечетное q, для которых n - 1 = 2kq.

Шаг 2. Присвоим i нулевое значение, а r значение вычета bq по модулю n.

Шаг 3. Если i = 0 и r = 1, или i > 0, а r = n - 1, то вывести сообщение: «ничего определенного сказать нельзя»; в противном случае переходим к шагу 4.

Шаг 4. Увеличиваем i на 1 и заменяем r на r2 по модулю n; переходим к шагу 5.

Шаг 5. Если i < k, то возвращаемся к шагу 3; в противном случае выдаем сообщение: «n составное».

В случае неопределенного сообщения возможны две ситуации: либо n простое, либо составное. К сожалению, второй случай реально встречается.

Рассмотрим несколько примеров, причем начнем с хороших новостей. Мы видели ранее, что 341 –  псевдопростое по основанию 2, так что это хороший объект для теста Миллера. Прежде всего, 340 = 22×85. Теперь нам нужно найти вычеты по модулю 341 у степеней 2 с показателями 85 и 170:

285 = 32 (mod 341),

2170 = 1 (mod 341).

Это позволяет тесту дать заключение: «число составное».

Более наглядный пример дает нам число Кармайкла 561. Подвергнем его тесту Миллера по основанию 2. Простые вычисления показывают, что 560 = 24×35. Выпишем последовательность вычетов степеней 2 по модулю 561:

и в этом случае тест сообщит нам о разложимости числа.

Хотя 561 - число Кармайкла, мы обнаружили, что оно составное, применив наименьшее из возможных оснований. Теперь плохие новости. Применим тест Миллера по основанию 7 к 25. Поскольку 24 = 23×3, последовательность степеней и их остатков имеет вид:

Так что тест здесь не может сказать ничего определенного, несмотря на то, что разложимость числа 25 видна невооруженным взглядом. Конечно, основание 7 мы выбрали не случайно, если бы основанием было 2, то тест бы узнал в двадцати пяти составное число.

Пусть n > 0- нечетное целое число и 1 < b < n - 1. Если n составное, а тест Миллера его не распознал, то оно называется строго nсевдоnростым по основанию b. Вышеприведенный пример показывает, что 25 - строго псевдопростое по основанию 7. Легко увидеть, что строго псевдопростое число по основанию b является псевдопростым по этому же основанию.

Как мы уже отметили, число 25 не является строго псевдопростым по основанию 2. Наименьшее строго псевдопростое число по основанию 2 - это 2047. Более того, существует только 1282 строго псевдопростых чисел по основанию 2, лежащих между 1 и 109, что дает хорошее представление об эффективности данного теста. Конечно, можно применять тест Миллера по нескольким основаниям, что существенно увеличит его эффективность. Например, наименьшее строго псевдопростое одновременно по основаниям 2,3 и 5 это 25326001.

Более того, не существует «строго Кармайкловских чисел».

Это следует из результата М. О. Рабина (Rabin).

Теорема Рабина. Пусть n > 0 – нечетно натуральное число. Если тест Миллера, примененный к n для более, чем n/4 оснований, не распознает в n составного числа, то это число – простое.

Контрольные вопросы

  1.  Какие числа называются простыми?
  2.  Какие числа называют взаимнопростыми?
  3.  Кратко опишите алгоритм Эвклида.
  4.  Сформулируйте лемму, на которую опирается доказательство корректности алгоритма Эвклида.
  5.  Почему наибольший общий делитель совпадает с последним ненулевым остатком в последовательности делений?
  6.  Кратко опишите расширенный алгоритм Эвклида.
  7.  В решении каких задач криптологии необходима проверка чисел на простоту.
  8.  Сформулируйте теорему Ферма.
  9.  Что такое псевдопростые числа и числа Кармайкла? Перечислите свойства чисел Кармайкла.
  10.  Какие недостатки теоремы Ферма вы можете назвать?
  11.  Кратко опишите тест Миллера.
  12.  Сформулируйте теорему Рабина.
  13.  В чем недостаток теста Миллера-Рабина?

Варианты практических заданий

№ варианта

Задание 5

№ варианта

Задание 5

А

В

А

В

1

51

329

16

34

551

2

560

172

17

1148

334

3

123

78

18

1098

258

4

854

133

19

257

1089

5

695

135

20

251

86

6

341

952

21

125

458

7

93

624

22

1654

885

8

177

254

23

665

894

9

1023

653

24

332

993

10

114

854

25

2056

962

11

145

786

26

274

563

12

113

92

27

79

596

13

284

777

28

774

483

14

954

201

29

1003

856

15

810

667

30

119

1684


 

А также другие работы, которые могут Вас заинтересовать

69217. Статистика оплати праці 50.5 KB
  Оплата праці - сполучний елемент між державою, підприємством і окремою особою; це стимул до зростання продуктивності праці; один з елементів витрат на виробництво продукції; рівень матеріального добробуту працівників.
69218. Статистика основных фондов 28 KB
  ОПФ это здания сооружения передаточные устройства машины и оборудование транспортные средства производственный инвентарь и принадлежности хозяйственный инвентарь рабочий и продуктивный скот многолетние сады и насаждения капитальные затраты по улучшению земель...
69219. Статистичні показники 158 KB
  Статистичний показник це кількісна характеристика соціальноекономічних явищ та процесів в умовах якісного визначення тобто це міра якісного і кількісного відображення певної властивості соціальноекономічного явища чи процесу.
69220. Статистика продукції 138.5 KB
  Промислова продукція - це прямий корисний результат промислово-виробничої діяльності підприємства (фірми), виражений у формі продуктів або виробничих послуг. Отже, звідси: продукція є результатом діяльності підприємства, тому сировина та матеріали, що ще не вступили у виробництво...
69221. Статистичне спостереження, його суть, форми та помилки 112 KB
  Форми статистичного спостереження його види та способи проведення. Програмно методологічні та організаційні питання статичного спостереження. Помилки статистичного спостереження та заходи щодо їх усунення.
69222. Вибірковий метод 437 KB
  Причини і умови застосування та організації вибіркового спостереження. Так для визначення втрат при збиранні урожаю суцільне спостереження потребує значних затрат часу та коштів а при перевірці якості продукції наприклад жирності молока схожості зерна його не можна провести...
69223. Статистичні методи вивчення взаємозв’язків 398.5 KB
  Кореляційно-регресійний аналіз зв’язку його завдання і основні етапи. Оцінка щільності та істотності кореляційного зв’язку. При функціональному зв’язку кожному можливому значенню факторної ознаки відповідає чітко визначене значення результативної ознаки тобто...
69224. Статистичне вивчення динаміки соціально-економічних явищ 507.5 KB
  Для будь-якого динамічного ряду характерні перелік хронологічних дат моментів або інтервалів часу і конкретні значення відповідних статистичних показників які називають рівнями ряду. Приймаючи будь-який інтервал за одиницю послідовність рівнів можна записати так: де число рівнів довжина динамічного ряду.
69225. Предмет, метод та завдання статистики 187.5 KB
  Статистика - самостійна суспільна наука, яка має свій предмет и метод дослідження. Виникла вона з практичної необхідності суспільного життя. Уже в давньому світі з’явилась необхідність підраховувати чисельність жителів держави; рахувати людей, пригодних до військової справи...