Применение алгоритма RSA для шифрования потоков данных — страница 13

  • Просмотров 7969
  • Скачиваний 308
  • Размер файла 89
    Кб

быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределёнными. Это вносит ряд дополнитель­ных осложнений в работу алгоритмов. Наконец, отметим, что существуют методы построения больших про­стых чисел, использующие не только простые делители 3.3. Проверка большого числа на простоту Есть некоторое отличие в постановках задач предыдущего и настоя­щего пунктов. Когда мы строим простое число В этом пункте

мы предполагаем лишь, что нам задано некоторое чи­сло выдержало испытания алгоритмом 5 для 100 различных значений параметра является простым, а нам требуется лишь доказать это. В настоящее время известны детерминированные алгоритмы различ­ной сложности для доказательства простоты чисел. Мы остановимся по­дробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана. Померанца и Рамели. Для доказательства простоты

или непростоты числа этот алгоритм требует арифметиче­ских операций. Здесь - некоторая положительная абсолютная посто­янная. Функция хоть и медленно, но всё же возрастает с ростом X. Ленстры и А. Коена. Мы будем называть описываемый ниже алгоритм алго­ритмом Адлемана - Ленстры. В основе алгоритма лежит использование сравнений типа малой те­оремы Ферма, но в кольцах целых чисел круговых полей, т. е. полей. порождённых над полем

числами - корнями из 1. Пусть - простое нечётное число и — первообразный корень по модулю дискретным логарифмом, с помощью сравнения с условием, что делится на Следующая функция, определённая на множестве целых чисел. является характером по модулю и порядок этого характера равен Сумма называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана -

Ленстры. Теорема 3. Пусть - нечетное простое число, выполняется сравнение . Если при каких-либо числах сравнение из теоремы 3 нарушается. можно утверждать, что составное число. В противном случае, если сравнение выполняется, оно даёт некоторую информацию о возможных простых делителях числа имеет лишь один простой делитель и является простым. В случае легко проверить, что сравнение из теоремы 3 равно­сильно хорошо известному в

элементарной теории чисел сравнению (13) где - так называемый символ Якоби. Хорошо известно также, что последнее сравнение выполняется не только для простых Пример (X. Ленстра). Пусть — натуральное число, (14) а кроме того с некоторым целым числом имеем (15) Как уже указывалось, при простом сравнения (14) выполняются для любого есть первообразный корень по модулю с усло­вием (15) при простом может быть найдено достаточно быстро с помощью