Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Это определение тесно связано с понятием разрешимости (tractability): можно ли решить задачу с помощью детерминированного или рандомизированного
156
Часть II. Математические основы
полиномиального алгоритма при разумных ограничениях времени и памяти, даже если размер исходных данных очень велик? Если ответ отрицателен, задача считается трудноразрешимой (intractable).
Однако, поскольку полиномы, характеризующие время выполнения алгоритмов, принадлежащих классам V или W, могут иметь совершенно разные степени, временная сложность задач также сильно варьируется. Таким образом, эффективный алгоритм решения разрешимой задачи на практике может оказаться непригодным. В последующих главах мы рассмотрим несколько протоколов, имеющих полиномиальную временную сложность. Следовательно, по определению 4.6 такие протоколы являются эффективными. Однако для практических приложений они не представляют никакой ценности, поскольку степень полиномов, ограничивающих их временную сложность, слишком велика. И наоборот, существуют практичные алгоритмы, не являющиеся полиномиальными (см. раздел 4.6), которые вполне пригодны для эффективного решения теоретически трудноразрешимых задач с небольшим объемом входных данных (например, метод кенгуру ' Полларда для индексных вычислений, рассмотренный в разделе 3.6.1).
Мы будем называть практически эффективными (practically efficient) полиномиальные алгоритмы с невысокой степенью полиномов, ограничивающих временную сложность. Например, машина Тьюринга Div3, алгоритмы gcd, mod_exp и Prime_Test, а также протокол QKD являются практически эффективными. Рассмотрим еще один пример практически эффективного алгоритма, широко применяемого в современной криптографии.
4.4.6.1 Пример эффективного алгоритма
Идею вероятностной проверки простоты числа можно непосредственно воплотить в виде алгоритма, генерирующего случайное вероятностно простое (probabilistic prime) число заданного размера. Число п называется вероятностно простым, если алгоритм Prime_Test(n) возвращает ответ "ДА".
Алгоритм 4.7. Генерация случайного fc-битового вероятностно простого числа
ВВОД: к: положительное целое число;
(* размер числа к должен быть равен к битов *).
ВЫВОД: fc-битовое случайное вероятностно простое число
PrimeGen(fc).
1- Р G i/(2fc_1,2fc_1 — 1], где р — нечетное.
2. if Prime_Test(p) = НЕТ return(Prime_Gen(fc)).
3. return(p).
Глава 4. Вычислительная сложность
157
Предположим, что алгоритм Prime Gen(fc) завершил свою работу. Это означает, что алгоритм нашел число р, удовлетворяющее условию PrimeTest(p) = ДА (п. 2). Из оценки вероятности ошибки алгоритма PrimeTest следует, что вероятность события "число р-не простое" не превосходит 2~к, где к = log2 р.
Возникает естественный вопрос: завершится ли алгоритм PrimeGen(fc) вообще?
В теории чисел хорошо известна теорема [ 170], утверждающая, что количество простых чисел, не превышающих числа X, ограничено снизу числом ^ак'
количество простых чисел, состоящих из к бит, приблизительно равно
2& 2'г—^ 2к ~к~ к-1 ~2Р
Следовательно, можно ожидать, что алгоритм Prime_Gen(fc) на этапе 2 рекурсивно вызовет себя 2к раз, найдет вероятностно простое число и завершит работу.
Временная сложность алгоритма PrimeTest(p) имеет порядок Ojg((logp)4) = = Ов(к4). Следовательно, при 2к вызовах алгоритма PrimeTest временная сложность алгоритма Prime_Gen(fc) имеет порядок Ojg(fc5).
Второй вопрос, на который необходимо ответить: означает ли оценка Ов(к5) существование полинома, зависящего от аргумента к, т.е. может ли эта величина полиномиально зависеть от размера исходных данных алгоритма PrimeGen(fc)?
Если число п записано в позиционной системе счисления с основанием Ъ > 1, его размер равен log6Ti и всегда меньше п. Для того чтобы время выполнения алгоритма Prime_Gen(fc) полиномиально зависело от размера исходных данных, необходимо явно указать, что число к должно состоять из к битов.
Определение 4.7 (Унарное представление числа). Унарное представление положительного целого числа п имеет вид
п
С этого момента для того, чтобы подчеркнуть размер входного числа, мы будем использовать его унарное представление.
158
Часть II. Математические основы
4.5 Недетерминированное полиномиальное время
Рассмотрим следующую задачу принятия решений. Задача SQUARE-FREENESS
ВВОД: N: положительное и нечетное составное целое число. ВОПРОС: Является ли число N свободным от квадратов?
Задача SQUARE-FREENESS очень сложна. До сих пор не существует алгоритма (детерминированного или вероятностного), временная сложность которого полиномиально зависела бы от размера числа ./V. Разумеется, существуют алгоритмы, позволяющие ответить на поставленный вопрос. Вот один из них: вводим число N, выполняем деление на квадраты всех нечетных простых чисел, не превышающих [Nj, и, если число N не делится ни на один из квадратов, выводим ответ "ДА". Однако, если число N произвольно, этот метод выполняется за
ально зависит от половины размера числа N.
Несмотря на это, задача SQUARE-FREENESS не является трудноразрешимой. Если нам известна некая дополнительная информация о задаче — свидетельство (witness) (или сертификат (sertificate), или вспомогательные исходные данные (auxiliary input)) — ее можно решить за время, полиномиально зависящее от размера исходного числа. Например, если на ввод поступает число N, в качестве свидетельства, гарантирующего эффективность алгоритма верификации целых чисел, свободных от квадратов, можно использовать число 4>{N) — количество всех положительных чисел, не превосходящих N и взаимно простых с числом N (определение 5.11 в разделе 5.2.3), вычисленное с помощью функции Эйлера ф (Euler function phi).
