Быстрая факторизация и постквантовые алгоритмы

Кстати, если вдруг придумают алгоритм быстрой факторизации больших полупростых чисел, сломав тем самым RSA, то, конечно, “популярной мотивации” для создания универсального квантового компьютера станет сильно меньше: на этом направлении всегда пишут про алгоритм Шора. А вот с необходимостью перехода на постквантовые криптосистемы, в этом случае, есть интересные особенности.

Так, обнаружение алгоритма быстрой факторизации, естественно, легко может грозить тем, что попутно обнаружится и способ быстро сломать задачи типа привычного эллиптического варианта Диффи-Хеллмана (читай – ECDSA). Однако только из этого не следует автоматически вывод, что переходить требуется именно на постквантовые криптосистемы. Вот тут и начинаются особенности. Во-первых, постквантовые криптосистемы уже разработаны, уже имеют какую-то практическую “классическую” стойкость, уже реализованы, – так что их быстрее внедрить; во-вторых, задачи, на которых базируются те или иные постквантовые криптосистемы, имеют гораздо больше шансов сохранить известную сложность после обнаружения каких-то принципиально новых методов быстрой факторизации – это, конечно, тоже не гарантируется, однако для ускорения факторизации/логарифмирования до сих пор использовались математические конструкции, которые, в общем-то, стоят и за многими постквантовыми алгоритмами.

Адрес записки: https://dxdt.ru/2023/11/07/11463/

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Написать комментарий

Ваш комментарий:

Введите ключевое слово "5ZW11" латиницей СПРАВА НАЛЕВО (<--) без кавычек: (это необходимо для защиты от спама).

Если видите "капчу", то решите её. Это необходимо для отправки комментария ("капча" не применяется для зарегистрированных пользователей). Обычно, комментарии поступают на премодерацию, которая нередко занимает продолжительное время.