© Борисенко, мех-мат МГУ

Напомним необходимые нам результаты из элементарной теории чисел и алгебры

Малая теорема Ферма. Пусть p -- простое число. Тогда для всякого целого числа b, отличного от нуля, справедливо сравнение b^p-1 == 1 (mod p).

Малая теорема Ферма является непосредственным следствием теоремы Лагранжа (порядок любого элемента группы делит порядок группы) и того факта, что кольцо Z_p в случае простого p является полем, т.е. все его ненулевые элементы принадлежат группе обратимых элементов. Порядок группы обратимых элементов кольца Z_p равен p-1.

Простейший тест проверки простоты числа m состоит в проверке малой теоремы Ферма. Выберем произвольное целое число b (например, b = 2), и возведем его в степень m - 1 по модулю m. Если мы получим не единицу, то по малой теореме Ферма число m составное. Беда состоит в том, что если

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

то m -- простое число. Минимальный контрпример к этому утверждению был найден только в XVII веке:

но число 341 -- не простое, 341 = 11 * 31.

То, что 341 не удовлетворяет малой теореме Ферма, может быть показано с помощью других оснований:

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

Определение. Число m называется кармайкловым, если оно не простое и для всякого b, взаимно простого с m, выполняется утверждение малой теоремы Ферма:

Минимальные кармайкловы числа -- это 561, 1105, 1729, ...

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

Предложение 5. Пусть

представление целого числа m в виде произведения степеней простых. Число m является кармайкловым тогда и только тогда, когда

1) для всякого i показатель степени e_i = 1;

2) k >= 3;

3) для всякого i число p_i - 1 делит m - 1.

Доказательство. Докажем только обратную, наиболее интересную импликацию. Пусть число m удовлетворяет условиям 1-3.

Рассмотрим произвольное b, взаимно простое с m. По Китайской теореме об остатках, кольцо Z_m представляется в виде прямой суммы

При этом изоморфизме элемен b представляется в виде строки

Тогда

По малой теореме Ферма, для всякого i

поскольку (m - 1) делится на (p_i - 1).

Поэтому

т.е. b_m-1 == 1 (mod m).

Пример. Покажем, что число 561 является кармайкловым. Действительно, 561 = 3 * 11 * 17. Имеем

Следовательно, число 561 удовлетворяет условиям предложения 5.

Итак, для кармайкловых чисел тест простоты, основанный на теореме Ферма, не работает. Тем не менее его модификация, предложенная Рабином, применима к любым целым числам.

Тест Рабина является вероятностным. Это означает, что он использует датчик случайных чисел и, таким образом, работает не детерминированно. Для входного целого числа m тест Рабина может выдать один из следующих двух ответов.

1. Число m является составным.

2. Не знаю.

В случае первого ответа число m действительно является составным, тест Рабина предъявляет доказательство этого факта. Второй ответ может быть выдан как для простого, так и для составного числа m. Однако для любого составного числа m вероятность второго ответа не превышает 1/4. Ценность теста Рабина состоит именно в неравенстве, ограничевающем сверху вероятность второго ответа для произвольного составного числа m.

Таким образом, если мы применим 100 раз тест Рабина к числу m и получим 100 ответов "не знаю", то можно с большой вероятностью утверждать, что число m простое. Более точно, вероятность получения ста ответов "не знаю" для составного числа m не превышает (1/4)¹⁰⁰, т.е. практически равна нулю. Тем не менее тест Рабина не предъявляет доказательства того, что число m простое.

Перейдем непосредственно к изложению теста Рабина. Мы проверяем простоту входного числа m. Допустим сразу, что число m нечетное. (Существует только одно четное простое число -- 2.) Тогда число m - 1 четное. Представим его в виде

Используя алгоритм быстрого возведения в степень по модулю m, вычислим следующую последовательность элементов кольца Z_m:

     x0 == bs (mod m),                                 (1)
     x1 == x0 * x0 (mod m),
     x2 == x1 * x1 (mod m),
     ...
     xt == xt-1 * xt-1 == bm - 1 (mod m)

Тест Рабина выдает ответ 'm -- составное число' в случае, если

1) x_t =/= 1 (mod m), или

2) в последовательности x₀, x₁, x₂, ..., x_t имеется фрагмент вида ..., *, 1, ... где звездочкой обозначено число, отличное от единицы или минус единицы по модулю m.

В противном случае тест Рабина выдает ответ "не знаю". Последовательность x₀, x₁, ..., x_t в этом "плохом" случае либо начинается с единицы, либо содержит (-1) где-нибудь не в конце.

Cуществует алгоритм, доказывающий простоту, со сложностью O(ln³n), согласно которому необходимо провести тест Рабина со всеми числами

Этот алгоритм, опираясь на недоказанный факт, в принципе может 'соврать' в отношении доказательства простоты, хотя если тест Рабина говорит, что число составное, значит так оно и есть. На практике он работает очень даже неплохо.

1. Если тест Рабина выдает ответ 'm -- составное число', то m действительно является составным.

2. Вероятность ответа 'не знаю' для составного числа m не превосходит 1/4.

Доказательство. Докажем только первое утверждение. Если x_t =/= 1 (mod m), то m не удовлетворяет малой теореме Ферма и, следовательно, не является простым. Если же последовательность (1) содержит фрагмент ..., a, 1, ..., где a =/= +-1 (mod m), то имеем

Если бы m было простым, то кольцо Z_m являлось бы полем.

Но в любом поле есть только два квадратных корня из единицы: это единица и минус единица. (По теореме Безу, число корней многочлена не превосходит его степени, квадратные корни из единицы -- это корни многочлена x² - 1.) Следовательно, число m не является простым.

{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <relf@os2.ru>, 2:5015/60@FidoNet}
{Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000].
Вероятность ошибки (то, что составное число будет названо простым) меньше
4^(-Rounds).}

const Rounds=20;

function mulmod(x,y,m:longint):longint; assembler;
asm
{$IFDEF USE32}
  mov eax,x
  mul y
  div m
  mov eax,edx
{$ELSE}
  db $66; mov ax,word ptr x
  db $66; mul word ptr y
  db $66; div word ptr m
  mov ax,dx
  db $66; shr dx,16
{$ENDIF}
end;

function powmod(x,a,m:longint):longint;
var r:longint;
begin
  r:=1;
  while a>0 do
  begin
    if odd(a) then r:=mulmod(r,x,m);
    a:=a shr 1;
    x:=mulmod(x,x,m);
  end;
  powmod:=r;
end;

function isprime(p:longint):boolean;
var q,i,a:longint;
begin
if odd(p) and (p>1) then
begin
  isprime:=true;
  q:=p-1;
  repeat q:=q shr 1; until odd(q);
  for i:=1 to Rounds do
  begin
    {$IFDEF USE32}
	 a:=Random(p-2)+2; {$ELSE} a:=2+Trunc(Random*(p-2)); {$ENDIF}
    if powmod(a,p-1,p)<>1 then
    begin
      isprime:=false; break;
    end;
    a:=powmod(a,q,p);
    if a<>1 then
    begin
      while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
      if a=1 then
      begin
        isprime:=false; break;
      end;
    end;
  end;
end else isprime:=(p=2);
end;

var t:longint;
begin
  Randomize; {Don't forget to reset Random Generator!}
  for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);end.