Exact Analyses of Computational Time for Factoring in Quantum Computers(Public Key Cryptography)(<Special Section>Cryptography and Information Security)
スポンサーリンク
概要
- 論文の詳細を見る
We evaluate the exact number of gates for circuits of Shor's factoring algorithm. We estimate the running time for factoring a large composite such as 576 and 1024 bit numbers by appropriately setting gate operation time. For example, we show that on the condition that each elementary gate is operated within 50μsec, the running time for factoring 576 bit number is 1 month even if the most effective circuit is adopted. Consequently, we find that if we adopt the long gate operation-time devices or qubit-saving circuits, factorization will not be completed within feasible time on the condition that a new efficient modular exponentiation algorithm will not be proposed. Furthermore, we point out that long gate operation time may become a new problem preventing a realization of quantum computers.
- 社団法人電子情報通信学会の論文
- 2005-01-01
著者
-
KUNIHIRO Noboru
University of Electro-Communica-tions
-
Kunihiro Noboru
University Of Electro-communications
関連論文
- Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
- Extension of Secret Handshake Protocols with Multiple Groups in Monotone Condition
- Cryptanalysis of Two MD5-Based Authentication Protocols : APOP and NMAC
- Extended Password Recovery Attacks against APOP, SIP, and Digest Authentication
- New Message Differences for Collision Attacks on MD4 and MD5
- Improved Collision Attacks on MD4 and MD5(Hash Functions,Cryptography and Information Security)
- Deterministic Polynomial Time Equivalence between Factoring and Key-Recovery Attack on Takagi's RSA
- Improved Collision Search for Hash Functions : New Advanced Message Modification
- Small Secret CRT-Exponent Attacks on Takagi's RSA
- Near-Collision Attacks on MD4 : Applied to MD4-Based Protocols
- Exact Analyses of Computational Time for Factoring in Quantum Computers(Public Key Cryptography)(Cryptography and Information Security)
- Solving Generalized Small Inverse Problems