Материал: Лекция 2 Генерирование простых чисел [восстановлен]

‬Тест Ферма

‬Вспомним малую теорему Ферма, которая гласит, что если n простое число и n не делит a, то a n-1 = 1 mod n. Поэтому необходимо выполнить следующие шаги:

‬1. Сгенерировать тестируемое число n и выбрать параметр «секретности» t.

‬2. Сгенерировать случайное числоa1 : 2 ≤ a1 ≤ n −1.

‬3. Вычислить r = a1n-1 mod n.

‬4. Если r ≠1 , тогдаn – составное число.

‬Если r = 1, то перейти к шагу 2 и повторить все то же самое с числом a2

итак далее, вплоть до повторения t шагов. При получении

a1n-1 =1 mod n, a2n-1 =1 mod n, …, arn-1 =1 mod n, считать n простым числом.

‬Данный тест может привести к ошибке, когда на всех шагах это условие выполняется, но число n тем не менее является составным.

‮Пример 2. Если n = 341, то легко проверить, что

‮2340 mod 341 = 1, то есть оно проходит условие т. Ферма, но n = 11· 31 .

‮Проверку нужно продолжить при других значениях а. 3340 mod 341 = 56.

‮ Случай, когда для любых чисел a1 , a2 , , at составное число n проходит тест, является особым. Такие числа n называются числами Кармайкла при условии, что gcd (a, n) = 1. Наименьшее число Кармайкла – это число n = 561 = 3· 11· 17 . Числа Кармайкла встречаются, однако, довольно редко.

‮Всего имеется 2163 числа Кармайкла в диапазоне 1 до 25 109, а в диапазоне 1 до 1 105 всего 16 таких чисел: 561,1105,1729….75361. В тесте Ферма эти числа не различимы.

‮Утверждение 5. При использовании теста Ферма, если число n не

является числом Кармайкла, вероятность ошибки тестирования будет равна 2−t , гдеt – число шагов.

‮ Таким образом, выбирая параметр «секретности» t достаточно большим, можно обеспечить высокую надежность тестирования простых чисел.

‬ Тест Миллера–Рабина.

‬

‬Пусть заданы тестируемое нечетное число n и параметр «секретности» t. Данный тест базируется на следующем утверждении, доказываемом в теории чисел [2, 3].

‬

‬Утверждение 6. Пусть n нечетное простое число и пусть для него справедливо представление: n – 1 = 2s · r , где s, r – числа, причем r – нечетное. Пусть a – такое, что gcd(a, n) = 1, тогда: ar = 1 mod n или

Тест Миллера–Рабина представляет комбинацию двух тестов:

проверки квадратным корнем и теста Ферма

Тест проверка квадратным корнем

В модульной арифметике, если n –простое числодиницы, то квадратный1 корень из

е modn = +1 или -1. Если n составное число, то квадратный корень можетбыть +1, -1 и другие числа.

(Напомним, что в модульной арифметике

-1=n-1(modn)

Примеры