Comments 12
Алгоритм Шора решает и задачу разложения числа на множители (RSA) и задачу дискретного логарифмирования (DLP), причем как в поле вычетов, так и на эллиптических кривых (ECC, ECDLP):
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/l03.pdf LECTURE 3: Quantum attacks on elliptic curve cryptography, 2008
Shor’s algorithm, which can calculate discrete logarithms over any cyclic group. In particular, this algorithm can be used to break the Diffie-Hellman key exchange protocol, which assumes that the discrete log problem in Z^x_p (p prime) is hard. However, Shor’s algorithm also breaks elliptic curve cryptography, the main competitor to RSA.… Ironically, Shor’s algorithm takes a comparable number of steps for both factoring and discrete log (regardless of the group involved)
http://arxiv.org/pdf/quant-ph/0301141v2.pdf Shor’s discrete logarithm quantum algorithm for
elliptic curves 2008
It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits.
http://logic.pdmi.ras.ru/~sergey/teaching/crypto10/12-quantum.pdf Алгоритм Шора, АФТУ РАН 2010
В результате получается квантовое решение задачи дискретного логарифма. Эллиптические кривые не спасают — для любой коммутативной группы работает, нужно только умножать уметь.
Мы взломали всю коммутативную криптографию. Что делать? Один ответ — строить квантовую криптографию. Другой ответ — строить некоммутативную криптографию.
См https://en.wikipedia.org/wiki/Post-quantum_cryptography "… cryptographic algorithms (usually public-key algorithms) that are thought to be secure against an attack by a quantum computer."
http://arxiv.org/pdf/quant-ph/0301141v2.pdf
А квантовый компьютер Google недавно проапргейдили до 1000+ кубит
http://www.wired.com/2015/09/googles-quantum-computer-just-got-a-big-upgrade-1000-qubits/
Спите спокойно, граждане Багдада.
Кажется, для квантового компьютера их всего один, от гугла, на javascript.
Сложная тема.
Ссылки:
http://www.cs.utep.edu/interval-comp/yakovlev.pdf
http://www2.math.uni-wuppertal.de/~xsc/xsc/pxsc_download.html
«Также завтра мы опубликуем этот материал на нашем портале, где, возможно, между нашими экспертами, молодыми исследователями и автором развернется самая настоящая научная дискуссия. Вероятно, кто-то из уважаемых читателей захочет присоединиться к дискуссии на нашем портале.»
Не могли бы дать ответ здесь или на вашем портале?
Добрый день! Ответ от А.М. Загоскина:
Здравствуйте! Этот вопрос в первую очередь касается цифровых компьютеров и напрямую связан с вопросом о квантовой коррекции ошибок и о пределах применимости математической модели. Для аналоговых устройств все в каком-то смысле проще — их точность ограничена, но пока уравнения для моделируемой системы и для аналогового «решателя» одни и те же, ответ будет приблизительно верным.
Экспертное мнение: Квантовые компьютеры, квантовая инженерия и квантовость