Алгоритм, доказывающий непростоту числа

3.1. Алгоритм, доказывающий непростоту числа

Выберем случайным образом число , , и проверим для
этого числа указанные выше свойства 1) и 2) п.2.

Если хотя бы одно из них нарушается, то число составное.

Если выполнены оба условия 1) и 2) п.2, возвращаемся к шагу 1.

Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей . А вероятность не определить его после повторений не превосходит . т. е. убывает очень быстро.

Миллер предложил детерминированный алгоритм определения состав­ных чисел, имеющий сложность , однако справедливость его ре­зультата зависит от недоказанной в настоящее время так называемой расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия 1) и 2) п.2 для всех целых чисел , . Если при каком-нибудь из указанного промежутка нарушается одно из условий а) или б), число составное. В противном случае оно будет простым или степенью простого числа. Последняя возможность, конечно, легко проверяется.

Напомним некоторые понятия, необходимые для формулиров­ки расширенной гипотезы Римана. Они понадобятся нам и в дальнейшем. Пусть - целое число. Функция называется характе­ром Дирихле по модулю , или просто характером, если эта функция периодична с периодом , отлична от нуля только на числах, взаимно простых с , и мультипликативна, т. е. для любых целых выполня­ется равенство . Для каждого существует ровно характеров Дирихле. Они образуют группу по умножению. Единичным элементом этой группы является так называемый главный характер , равный 1 на всех числах, взаимно простых с , и 0 на остальных це­лых числах. Порядком характера называется его порядок как элемента мультипликативной группы характеров.

С каждым характером может быть связана так называемая - функция Дирихле - функция комплексного переменного , определённая рядом. Сумма этого ряда аналитична в области и может быть аналитически продолжена на всю комплексную плос­кость. Следующее соотношение связывает L - функцию, отвечающую главному характеру, с дзета-функцией Римана . Расширенная гипотеза Римана утверждает, что комплексные нули всех L -функций Дирихле, расположенные в полосе , лежат на прямой . В настоящее время не доказана даже простей­шая форма этой гипотезы - классическая гипотеза Римана, утвержда­ющая такой же факт о нулях дзета-функции.

В 1952 г. Анкени с помощью расширенной гипотезы Римана доказал, что для каждого простого числа существует квадратичный невычет , удовлетворяющий неравенствам . Константа 70 была со­считана позднее. Именно это утверждение и лежит в основе алгоритма Миллера. В 1957 г. Берджесс доказал существование такого невычета без использования расширенной гипотезы Римана, но с худшей оценкой , справедливой при любом положительном и , большем некоторой границы, зависящей от.

Алгоритм Миллера принципиально отличается от алгоритма 2.1., так как полученное с его помощью утверждение о том, что число - со­ставное, опирается на недоказанную расширенную гипотезу Римана и по­тому может быть неверным. В то время как вероятностный алгоритм 2.1. даёт совершенно правильный ответ для составных чисел. Несмотря на отсутствие оценок сложности, на практике он работает вполне удовле­творительно.

Похожие работы

Шифросистемы с открытым ключом. Их возможности и применение.

Скачать

31031

1

0

... в тайне. Исходный текст шифруется открытым ключом адресата и передается ему. Зашифрованный текст в принципе не может быть расшифрован тем же открытым ключом. Дешифрование сообщение возможно только с использованием закрытого ключа, который известен только самому адресату. Криптографические системы с открытым ключом используют так называемые необратимые или ...

Защита персональных данных с помощью алгоритмов шифрования

Скачать

50231

14

1

... . Так как система с открытыми ключами позволяет распределять ключи и в симметричных системах, можно объединить в системе передачи защищенной информации асимметричный и симметричный алгоритмы шифрования. С помощью первого рассылать ключи, вторым же - собственно шифровать передаваемую информацию Обмен информацией можно осуществлять следующим образом: ·          получатель вычисляет открытый и ...

Устройство аппаратного шифрования данных с интерфейсом USB

Скачать

86939

6

20

... схема устройства для аппаратного шифрования информации, которая соответствует приведенным выше требованиям, изображена на рисунке 1.9. Рис. 1.9 – Структурная схема устройства аппаратного шифрования 2.  РАЗРАБОТКА СХЕМОТЕХНИЧЕСКОЙ РЕАЛИЗАЦИИ АППАРАТНОГО ШИФРАТОРА 2.1  Выбор элементной базы для шифратора   Согласно техническому заданию, элементная база для аппаратного шифратора должна ...

Криптографические системы защиты данных

Скачать

61238

6

2

... не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию; 2.7 Выводы по разделу 2. Подводя итоги вышесказанного, можно уверенно заявить, что криптографическими системами защиты называються совокупность различных методов и средств, благодаря которым исходная информация кодируеться, передаеться и расшифровываеться. Существуют различные криптографические системы защиты, ...