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

Схема алгоритма на базе малой теоремы Ферма

Схема алгоритма на базе малой теоремы Ферма

Тест на основе малой теоремы Ферма

Построение больших простых чисел.

Теорема

Если верна расширенная гипотеза Римана, то достаточно проверять все a из {2, 3, …, [2log2 n ]+1} (см. [3]).

Малая теорема Ферма [7] утверждает, что если n простое число, то выполняется условие: при всех a Î {2,3, …, n – 1} имеет место сравнение An - 1 º 1 mod n.

На основании этой теоремы можно построить вероятностный алгоритм проверки на простоту числа n.

Если для некоторого целого a из интервала [2, n] соотношение an - 1 º 1 mod n не выполняется, то число n – составное. Если же теорема выполняется, то вывод, что число n простое, сделать нельзя, так как теорема дает лишь необходимое условие. Поэтому, если

для некоторого a имеет место соотношение an - 1 º 1 mod n, то говорят, что число n является псевдопростым по основанию a [1]. Существует бесконечно много пар чисел a и n, где n – составное и псевдопростое. Вообще для любого a > 1 существуют бесконечно много псевдопростых чисел по основанию a [1]. Вообще, справедливы следующие два утверждения. Если пара (2, n) удовлетворяют сравнению an-1 º 1 mod n, то и пара чисел (2, 2n - 1) также ему удовлетворяют.

· Для любого простого числа n и любого a > 2 такого, что (a2 - 1, n) = 1, число (a2n - 1)/(a2 - 1) является псевдопростым по основанию a.

Определение. Составные числа n, для которых при всех основаниях выполняется сравнение an - 1 º 1 mod n, называются числами Кармайкла.

Дано число n и параметр g = 1 для идентификации

результата проверки.

1) делается случайный выбор целого числа a из интервала [2, n];

2) используя алгоритм Эвклида, вычисляется НОД для чисел a и n;

3) если НОД больше 1, то выполняется шаг 7;

4) для числа a проверяется сравнение an - 1 º 1 mod n;

5) если сравнение не выполняется, то определяется параметр g = 0 (число составное) переход на шаг 7.

6) если сравнение выполнено, то можно повторить тест;

7) выдать результат проверки (g = 0 – число составное).

При завершении работы алгоритма возможны следующие выводы:

· число n – составное (g = 0);

· если g = 1, то число n является либо простым, либо составным и числом Кармайкла.

Здесь уместно заметить [7], что числа Кармайкла достаточно редки. Так существуют всего 2 163 чисел Кармайкла, которые не превосходят 25 000 000 000, и всего 16 чисел, которые не превосходят числа 100 000.

Пусть дано нечетное число p. Надо проверить является ли число p простым.

1. Выбирается случайное число a, меньшее p.

2. Если НОД (a, p) ¹ 1, то p – составное число.

3. Вычисляется сравнение L(a, p) º a(p - 1)/2 mod p.

4. Вычисляется символ Якоби J(a, p).

5. Если L(a, p) ¹ J(a, p), то число p – составное.

6. Если L(a, p) = J(a, p), то вероятность того, что

число p – составное не превышает 50 %.

Если проверка повторяется k раз, то вероятность

того, что число p – составное, не превышает 1/2k.

Обоснование алгоритма Рабина - Миллера можно

найти в [3]. Здесь дадим только самые общие

соображения. Известно, что если число p – простое, то

уравнение x2 º 1 mod p имеет лишь два решения: x º ±1

mod p. Итак, пусть p – нечетное целое число, которое

надо проверить на простоту. Если p – простое, то по

теореме Ферма для любого целого a взаимно простого с

p выполняется сравнение am - 1 º 1 mod p. Так как p - 1 –

четно, то получаем a(m - 1)/2 º ±1 mod p. Если оказывается,

что (m - 1)/2 – четно, то можно повторить рассуждение,

при котором получим, что a(m - 1)/4 º ±1 mod p, и т. д.

Поэтому, чтобы проверить на простоту нечетное

число p, выбираем случайным образом число a из

интервала [1, p - 1] и вычисляем a^t (mod p), a^2t (mod p0, …, a^bt (mod p), где t – нечетное и число b = 2s. Если одно из этих чисел не совпадает с +1 или -1, то можно сделать вывод, что число p является числом составным. Если значения чисел совпадают с +1 или -1, то повторяем этот тест k раз. После повторения этого теста k раз вероятность того, что составное число p не будет выявлено, не превосходит 1/4k. После высказанных соображений перейдем к формулировке алгоритма Рабина - Миллера.

Дата добавления: 2013-12-13