Разработка алгоритма и программы генерации Больших простых чисел

  • 16 мая 2011 г.
  • 565 Слова
Тест Соловея-Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число являетсяпростым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он не «реагирует» и отсеивает составные числа Кармайкла, накоторых всегда ошибается тест Ферма. Тест Соловея-Штрассена опирается на малую теорему Ферма и свойства символа Якоби. Рассмотрим данный математический аппарат.
Алгоритм реализации тестаСоловея-Штрассена

Для проверки простоты числа p в этом алгоритме используется символ Якоби (p – нечетное):
1) Выберите случайное число a, меньше р;
2) Если НОД(a,p) ≠ 1, то р - составное число и не проходит тест;
3)Вычислите j= a(p-1)/2 (mod p);
4) Вычислите символ Якоби J(a,p);
5) Если j ≠ J(a,p),то число р определенно не простое;
6) Если j= J(a,p),то вероятность того, что число р не является простым, не больше 50процентов.
Число а, которое не показывает, что р наверняка не является простым числом, называется свидетелем. Если р – составное число, вероятность числа а быть свидетелем не ниже 50 процентов. Повторяем этупроверку t раз с t различными значениями а. Вероятность того, что составное число преодолеет все t проверок, не превышает (〖1/2)〗^t.
Малая теорема Ферма: для любого простого числа p и любогонатурального числа a верно следующее:
ap ≡ a (mod p) , для любого a ∈ Z, где Z – множество всех целых чисел.
Символ Якоби J(a,р): Символ Якоби J(a,р) представляет собой обобщение символа Лежандра на составныемодули, он определяется для любого целого а и любого нечетного р. J(a,р) определен только, если р – нечетно.
Если p – простое число, то
1) J(a,p) =0, если a делится на p;
2) J(a,p)=1, если a - квадратичныйвычет по модулю p;
3) J(a,p)=-1, если a - квадратичный невычет по модулю p.
Если p – составное число, то:
J(a,р)= J(a, p1)* J(a, p2)*…* J(a, pm),...