ショアのアルゴリズム
 |
ショアのアルゴリズム（英: Shor's algorithm）は、1994年にアメリカの数学者ピーター・ショアによって考案された[1][2]、整数における素因数を探索する量子アルゴリズムである。これは、注目を集めている潜在的な使用法があり、量子コンピューターが従来の古典コンピューターより遥かに高速に超多項式が解けるという強力な根拠となっている量子アルゴリズムのうちの一つである[3]。一方で、実用的に使用されるような素因数分解が解けるようになるには、将来的にさらなる量子ビットが必要である[4]。
実現可能性とその影響
[編集]現在の量子コンピューターには、量子ノイズや、量子力学的干渉の破壊といった課題が存在する。しかし、それらの課題を克服し、ある程度の量子ビット数の量子コンピューターを、操作することができるようになったとすると、RSA暗号、ディフィー・ヘルマン鍵共有、楕円曲線ディフィー・ヘルマン鍵共有などの公開鍵暗号の解読ができてしまうと考えられている[5]。なぜなら、例えばRSA暗号は、大きな素数同士の合成数を機械で素因数分解するのは、膨大な時間がかかり困難であるという推定のもとで基づいているからである。
出典
[編集]- ^ 竹内薫『量子コンピューターが本当にすごい: Google、NASAで実用が始まった“夢の計算機”』PHP研究所、2015年6月、241頁。ISBN 978-4-569-82498-7。
- ^ Shor, P.W. (1994). “Algorithms for quantum computation: Discrete logarithms and factoring”. Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 124–134. doi:10.1109/sfcs.1994.365700. ISBN 978-0-8186-6580-6
- ^ 長橋賢吾『図解入門よくわかる最新量子ｺﾝﾋﾟｭｰﾀの基本と仕組み』秀和システム、2018年9月、82頁。ISBN 978-4-7980-5455-1。
- ^ Gidney, Craig; Ekerå, Martin (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. Quantum 5: 433. arXiv:1905.09749. Bibcode: 2021Quant...5..433G. doi:10.22331/q-2021-04-15-433.
- ^ Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin E. (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". In Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Advances in Cryptology – ASIACRYPT 2017 – 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part II. Lecture Notes in Computer Science. Vol. 10625. Springer. pp. 241–270. arXiv:1706.06752. doi:10.1007/978-3-319-70697-9_9. ISBN 978-3-319-70696-2。
 | この項目は、数理論理学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 |