Тестирование чисел на простоту и построение больших простых чисел

  • 24 февр. 2013 г.
  • 816 Слова
Лабораторная работа № 6

Тестирование чисел на простоту и построение больших простых чисел

Цель работы
Освоить основные программные методы тестирования чисел напростоту.

Указание к работе
Ознакомиться с приведенными ниже методическими указаниями, а также с литературой [2], [8], [14]–[16], [18].

Метод пробных делений
Если n –составное, то n = a ∙ b, где 1 = b)
a %= b;
if (a == 0)
return 0;
if (a == 1)
return 1;


if (a < 0)
if ((b-1)/2 % 2 == 0)
return Jacobi (-a, b);else
return –Jacobi(-a, b);


if (a % 2 == 0)
if (((b*b - 1) / 8) % 2 == 0)
return +Jacobi (a/2, b);
else
return -Jacobi (a/2, b);g = gcd (a, b); // g = НОД (a, b)
assert (odd (a));
if (g == a)
return 0;
else
if (g != 1)
return Jacobi(g, b) * Jacobi (a/g, b);
elseif (((a-1) * (b-1) / 4) % 2 == 0)
return +Jacobi (b, a);
else
return –Jacobi (b, a);
}



Тест Леманна
Далее приведена последовательностьдействий при проверке простоты числа n:
1. Выбрать случайное число a, меньшее n.
2. Вычислить [pic].
3. Если t ≠ +1 или t ≠ –1, то n не является простым.
4. Если t ≡ +1 или t ≡ –1, товероятность того, что число n не является простым, не больше 0.5.
Повторите эту проверку k раз. Если результат вычислений равен 1 или –1, но не всегда равен 1, то n является простым числом свероятностью ошибки 0.5k.

Тест Рабина–Миллера
Пусть n – нечетное и n – 1 = 2S ∙ t, t – нечетное. Если число n является простым, то при всех a ≥ 2 выполняется сравнение an–1 ≡ 1 (mod n). Поэтому,рассматривая элементы [pic] можно заметить, что либо среди них найдется равный –1 (mod n), либо at ≡ 1 (mod n).
На этом замечании основан следующий вероятностный тест...