Тест Рабина--Миллера. 
Реализация системы распространения ключей на основе алгоритма Диффи-Хеллмана

На сегодняшний день для проверки чисел на простоту чаще всего используется тест Рабина-Миллера, основанный на следующем наблюдении. Пусть число п нечетное и, где r — нечетное. Если п простое, то для любого, а? 2, взаимно простого с п, выполняется условие теоремы Ферма (аr = 1 (mod n)). Разложим число на множители:

Тогда в последнем произведении хотя бы одна из скобок делится на п, то есть либо аr=1(mod п), либо среди чисел, а, аr, …, найдется сравнимое с -1 по модулю п.

Обращение этого свойства лежит в основе теста Рабина-Миллера.

Алгоритм 5. Тест Рабина-Миллера, [Молдовян Н.А. и др., 2004].

Вход. Нечетное целое число п? 5.

Выход. «Число п, вероятно, простое» шли «Число п составное».

• 1. Представить п — 1 в виде, где число r нечетное.
• 2. Выбрать случайное целое число а, 2? а? п — 2.
• 3. Вычислить .
• 4. При и выполнить следующие действия.
• 4.1. Положить j = 1.
• 4.2. Если j? s — 1 и .
• 4.2.1. Положить y=y2 (mod n)
• 4.2.2. При у = 1 результат: «Числю п составное».
• 4.2.3. Положить j=j+1.
• 4.3. При результат: «Число п составное».
• 5. Результат: «Число п, вероятно, простое».

В результате выполнения теста для простого числа п в последовательности a (mod n), a2r (mod n), …, (mod n) обязательно перед 1 должна появиться -1 (или, что-то же самое, п — 1 (mod n)). Это означает, что для простого числа п единственными решениями сравнения y2 = 1 (mod n) являются у = ±1 (mod n). Если число n составное и имеет k> 1 различных простых делителей (то есть не является степенью простого числа), то по китайской теореме об остатках существует 2k решений сравнения у2 = 1 (mod n). Действительно, для любого простого делителя pi числа п существует два решения указанного сравнения: у = ±1 (mod рi).

Поэтому k таких сравнений дают 2k наборов решений по модулям pi, содержащих элементы ± 1.

Сложность алгоритма равна.

Код функции rabin (поверка на простоту):

/*mod — проверяемое значение,.

st — степень числа при передаче в функцию sstep ();

osn — основание при вычислении Пр: osnst (mod mod).

*/.

int rabin (){.

unsigned char c[33]={0};

int i, k, g, t, q, r, x, j, fl, w;

unsigned char d[33]={0};//для р.м. р-1.

srand (time (0));

for (i=0;i<=31;i++) st[i]=mod[i];

st[0]-=1;

for (i=0;i<=31;i++){.

d[i]=st[i];

}.

for (i=0;;i++){.

q=i+1;

r=0;

for (k=31;k>=0;k—){.

t=st[k]+(r<<8);

st[k]=(t>>1);

r=t%2;

}.

if (int (st[0])%2==1) break;

}//находим n-1=(2^s)*q где n-простое.

for (i=0;i<=6;i++){.

osn[i]=rand ();

}//генерируем основание.

step (c);

x=comp_sp (c, d);

if (x==2){.

return 1;

}.

x=rav (c);

if (x==0) return 1;

j=1;

while (j<=q-1){.

step2(c, c);

x=rav (c);

if (x==0) return 0;

j++;

}.

x=comp_sp (c, d);

if (x≠2){.

return 0;

}.

return 1;

}.