Cтраница 3
Наша задача в предлагаемой статье отчасти методическая; по нашим наблюдениям, даже специалисты плохо понимают связи между различными существующими подходами. В статье дается эффективное описание гамильтоновой структуры лаксовых уравнений и связанных с ней пуассоновых подпространств и орбит. Полезное методическое замечание состоит в том, что орбиты совершенно не зависят от эллиптической кривой. Мы также приводим сравнение различных постановок задачи факторизации, связанной с решением лаксовых уравнений - задачи Римана и пока менее популярной задачи Кузена. [31]
Эта задача считается сложной настолько, что на предположении о трудности ее решения основываются практические алгоритмы криптографии. С теоретической точки зрения положение несколько хуже: неизвестно ни сведение к задаче факторизации задач из класса NP, ни другие прямые свидетельства в пользу ее сложности. Слово прямые взято в кавычки из-за того, что в настоящее время неизвестен ответ на вопрос Р NP. Таким образом, предположение о сложности задачи факторизации пополняет и без того обильную коллекцию недоказанных гипотез в вычислительной теории сложности. Количество таких гипотез хочется по возможности уменьшать. В этом и состоит основная ценность результата Шора - если совершить один акт веры и уверовать в сложность задачи факторизации, то необходимость в еще одном акте веры ( относительно больших вычислительных возможностей квантового компьютера) отпадает. [32]
Следует, однако, отметить, что использование соотношений (3.64) не всегда приводит к операторному представлению функции с наименьшим числом операторов. Задача представления функции в форме с минимальным числом операторов аналогична задаче факторизации булевых функций, которая состоит в получении абсолютно минимальных форм представления функций. Известные к настоящему времени способы факторизации не намного эффективнее перебора всех возможных суперпозиций, состоящих из двух, трех и более операторов, до тех пор, пока не будут получены представления функций с абсолютно минимальным числом операторов. Вполне естественно, что такие способы из-за своей громоздкости не имеют практического значения. Поэтому задача факторизации решается приближенно путем вынесения за скобки некоторых переменных в МДНФ функции, хотя доказано, что таким способом не всегда удается получить абсолютно минимальное представление функций. [33]
Важной проблемой в теории протоколов распределения ключей типа Диффи-Хеллмана ( см. [4]) является проблема доказательства сходимости какой-либо предположительно трудной вычислительной задачи ( например, задачи дискретного логарифмирования или факторизации целых чисел) к задаче Диффи-Хеллмана, т.е. к задаче вычисления общего секретного ключа по данной открытой информации в некотором протоколе типа Диффи Хеллмана. Если такая сводимость имеет место, то из сложности исходной задачи вытекает стойкость соответствующего протокола. В работах ден Бура [3] и Маурера [5] доказана сводимость задачи дискретного логарифмирования к задаче Диффи-Хеллмана при некоторых дополнительных предположениях. Однако при полиномиальной сложности последней задачи эта оценка дает лишь субэкспоненциальную, а не полиномиальную верхнюю границу сложности задачи дискретного логарифмирования. В работах Шмуели [7] и МакКарли [6] изучается сводимость задачи факторизации п к задаче Диффи-Хеллмана по модулю п, где п является произведением двух различных простых чисел. К сожалению, автору недоступна работа [7]; в [6] приведен с наброском доказательства без ссылки на источник некоторый результат Шмуели, относящийся к вышеуказанной проблеме. При этом, однако, результат Шмуели ( в том виде, как он приведен в [6]) не позволяет утверждать, что если алгоритм А полиномиален и имеет не пренебрежимо малую вероятность успеха, то и алгоритм В полиномиален. [34]
Эта задача считается сложной настолько, что на предположении о трудности ее решения основываются практические алгоритмы криптографии. С теоретической точки зрения положение несколько хуже: неизвестно ни сведение к задаче факторизации задач из класса NP, ни другие прямые свидетельства в пользу ее сложности. Слово прямые взято в кавычки из-за того, что в настоящее время неизвестен ответ на вопрос Р NP. Таким образом, предположение о сложности задачи факторизации пополняет и без того обильную коллекцию недоказанных гипотез в вычислительной теории сложности. Количество таких гипотез хочется по возможности уменьшать. В этом и состоит основная ценность результата Шора - если совершить один акт веры и уверовать в сложность задачи факторизации, то необходимость в еще одном акте веры ( относительно больших вычислительных возможностей квантового компьютера) отпадает. [35]