В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа для 25% всех возможных значений базиса. Повторяя этот тест для различ- ных случайных значений a , можно убедиться в правильности полученного ответа. Если n действительно является простым числом, оно всегда будет проходить тест как простое число. Если не является — это смогут выявить по крайней мере 75% возможных значений a , и вероятность того, что состав- ное число n успешно пройдет несколько тестов как простое, можно снизить до любого уровня. Мы ограничим вероятность получения неверного результата до 2 − 128 , чтобы достичь запланированного уровня безопасности. Приведем тест Рабина–Миллера. функция Rabin-Miller вход: n Нечетное число ≥ 3 . выход: b Булево значение, указывающее, является ли n простым чис- лом. assert n ≥ 3 ∧ n mod 2 = 1 Вначале найдем такую пару ( s, t ) , что s — нечетное и 2 t s = n − 1 . ( s, t ) ← ( n − 1 , 0) while s mod 2 = 0 do ( s, t ) ← ( s/ 2 , t + 1) od Вероятность получения неверного результата будет отслеживать- ся с помощью переменной k . Эта вероятность не превышает 2 − k . Будем прокручивать цикл до тех пор, пока вероятность получения неверного результата не станет достаточно низкой. k ← 0 while k < 128 do Выберем случайное a , такое, что 2 ≤ a ≤ n − 1 . a ∈ r 2 , . . . , n − 1 Ресурсоемкая операция: возведение в степень по модулю. v ← a s mod n Если v = 1 , n успешно проходит тест для базиса a . if v 6 = 1 then Если n — простое число, тогда последовательность v, v 2 , . . . , v 2 t должна завершиться числом 1, а последним числом, не рав- ным единице, должно быть n − 1 . i ← 0 while v 6 = n − 1 do if i = t − 1 then return false else 11.4. Большие простые числа 225 ( v, i ) ← ( v 2 mod n, i + 1) fi od fi Если мы добрались до этого этапа, значит, число n успешно прошло проверку на простоту для базиса a . Таким образом, мы сокра- тили вероятность получения неверного результата в 2 2 раза, поэтому значение k можно увеличить на 2. k ← k + 2 od return true Данный алгоритм работает только для нечетных n , больших или рав- ных 3, поэтому вначале мы проверяем соответствующее условие. Функция isPrime должна вызывать функцию Rabin-Miller только с корректным ар- гументом, однако каждая функция сама отвечает за проверку собственных входных и выходных значений. Никто не знает, как программное обеспечение может измениться в будущем. В основе теста Рабина–Миллера лежит идея, известная как малая теорема Ферма 4 . Для любого простого числа n и для всех 1 ≤ a < n справедливо от- ношение a n − 1 mod n = 1 . Чтобы понять доказательство этого утверждения, требуется более глубокое знание математики, чем то, на которое ориентиро- вана эта книга. Небольшой тест (называемый также алгоритмом проверки на простоту Ферма) позволяет доказать это утверждение для ряда случайно выбранных значений a . К сожалению, существует несколько “неприятных” чисел, называемых числами Кармайкла (Carmichael). Эти числа являются составными, но проходят тест Ферма для всех (почти) базисов a . Тест Рабина–Миллера является разновидностью теста Ферма. Вначале мы записываем n − 1 как 2 t s , где s — нечетное число. Если требуется вы- числить a n − 1 , можно вначале подсчитать a s и затем возвести полученный результат в квадрат t раз, чтобы получить a s · 2 t = a n − 1 . Если a s = 1(mod n ) , тогда многократное возведение в квадрат не изменит результата, поэтому получаем, что a n − 1 = 1(mod n ) . Если же a s 6 = 1(mod n ) , тогда мы анализи- руем числа a s , a s · 2 , a s · 2 2 , a s · 2 3 , . . . , a s · 2 t (разумеется, взятые по модулю n ). Ес- ли n является простым числом, тогда, согласно теореме Ферма, последним элементом приведенной выше последовательности должна быть 1. Отметим также, что если n — простое, тогда единственными числами, удовлетворяю- щими уравнению x 2 = 1(mod n ) , являются 1 и n − 1 . (Легко проверить, что 4 Существует несколько теорем, названных именем Ферма (Fermat). Наибольшую из- вестность приобрела последняя теорема Ферма, касающаяся уравнения a n + b n = c n . Ее доказательство слишком велико, чтобы приводить его здесь. |