1294
правки
Квантовый алгоритм факторизации: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм факторизации (посмотреть исходный код)
Версия от 04:53, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 13: | Строка 13: | ||
== Применение == | == Применение == | ||
[[Труднорешаемая задача|Труднорешаемые задачи]] теории чисел нашли применение в криптографических системах с открытым ключом. Криптосистема RSA с открытым ключом, также как и другие, основывается на том, что факторизация не имеет эффективного алгоритма. Наиболее известные классические алгоритмы факторизации | [[Труднорешаемая задача|Труднорешаемые задачи]] теории чисел нашли применение в криптографических системах с открытым ключом. Криптосистема RSA с открытым ключом, также как и другие, основывается на том, что факторизация не имеет эффективного алгоритма. Наиболее известные классические алгоритмы факторизации способны помочь определить, насколько безопасна криптосистема и какой размер ключа следует выбрать. Квантовый алгоритм Шора для факторизации может взломать эти системы за полиномиальное время с помощью квантового компьютера. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Вопрос о том, существует ли классический алгоритм факторизации с полиномиальным временем выполнения, остается открытым. Существуют задачи сложнее факторизации, такие как нахождение единичной группы числового поля произвольной степени, для которых пока не | Вопрос о том, существует ли классический алгоритм факторизации с полиномиальным временем выполнения, остается открытым. Существуют задачи сложнее факторизации, такие как нахождение единичной группы числового поля произвольной степени, для которых пока не обнаружено эффективных квантовых алгоритмов. | ||
== См. также == | == См. также == | ||
| Строка 36: | Строка 36: | ||
6. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26,1484-1509 (1997) | 6. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26,1484-1509 (1997) | ||
[[Категория: Совместное определение связанных терминов]] | |||