Квадратные корни по модулю п

Если п - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю п вы­числительно эквивалентна возможности разложить число п на множители [1283, 35, 36, 193]. Другими словами, тот, кто знает простые множители числа п, может легко вычислить квадратные корни любого числа по модулю и, но для любого другого вычисление окажется таким же трудным, как и разложение на простые множители числа п.

11.5 Генерация простого числа

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

Если каждому понадобится свое простое число, не иссякнет ли у нас запас? Нет. В действительности сущее т-вует приблизительно 10151 простых чисел длино1 до 512 бит включительно. Для чисел, близких и, вероятность того, что случайно выбранное число окажется простым, равна 1/1п п. Поэтому полное число простых чисел, меньших п, равно я/(1п п). Во вселенной всего 10⁷⁷ атомов. Если бы для каждого атома во вселенной с начала времен каждую микросекунду требовался бы миллиард простых чисел, понадобилось бы только 10 ¹⁰⁹ простых чисел, осталось бы еще примерно 10 ^ш простых чисел.

Что если два человека случайно выберут одно и то же простое число? Этого не случится. При выборе из 10151 простых чисел вероятность совпадения выбора значительно меньше, чем вероятность, что ваш компь ю-тер случайно вспыхнет в тот самый момент, когда вы выиграете в лотерею.

Если кто-то создаст базу данных всех простых чисел, не сможет ли он использовать эту базу данных для вскрытия алгоритмов с открытыми ключами? Нет. Если бы вы хранили один гигабайт информации на устро й-стве, весящем один грамм, то перечень простых чисел размером до 512 бит включительно весил бы столько, что масса хранилища превысила бы предел Чандрасекара, и оно сколлапсировало бы в черную дыру... в любом случае вы не сможете извлечь данные.

Но если так трудоемко разложение на множители, как может быть простой генерация простых чисел? Фокус в том, что ответить "да" или "нет" на вопрос "Является ли число п простым?" гораздо проще, чем ответить на более сложный вопрос "Каковы множители и?"

Генерация случайных чисел с последующей попыткой разложения их на множители - это неправильный сп о-соб поиска простых чисел. Существуют различные вероятностные проверки на простоту чисел, определяющие, является ли число простым, с заданной степенью достоверности. При условии, что эта "степень достоверности" достаточна велика, такие способы проверки достаточно хороши. Я слышал, что простые числа, генерированные таким образом называются "промышленно простыми числами": эти числа вероятно являются простыми с ко н-тролируемой возможностью ошибки.

Предположим, что одна проверка из 2⁵⁰ - ошибочна. Это означает, что с вероятностью 1/10 ¹⁵ проверка объя­вит простым составное число. (Простое число никогда не будет объявлено составным при проверке.) Если по

какой-то причине понадобится большая достоверность простоты числа, уровень ошибки можно понизить. С другой стороны, если вы установите вероятность того, что число является составным, в 300 миллионов раз меньшей, чем вероятность выиграть главный приз в государственной лотерее, вы можете больше об этом не волноваться.

Обзоры недавних исследований в этой области можно найти в [1256, 206]. Другими важными работами я в-ляются [1490, 384, И, 19, 626, 651, 911].