Scott Fluhrer \(sfluhrer\) writes: > > That we do not know until we know what those quantum computers can > > really do... I have not seen anybody saying how many qbits you need to > > break MODP-2048. > > It's about twice as many as you need to factor a 2048 bit composite; > so about 4k (logical) qubits. > > > Most of the things I have seen talks about factoring RSA, > > and even then they do not provide numbers. > > How about https://arxiv.org/abs/quant-ph/0205095 - to factor an n > bit number, you can do it with circa 2n qubits. > > If you want other references, we have > https://arxiv.org/abs/1611.07995 and > https://arxiv.org/pdf/1706.07884.pdf both with similar results. We > also have https://arxiv.org/abs/quant-ph/0601097 which suggests a > way with 1.5n qubits; however that paper makes some assumptions > about errors that might not be true.
It would be good idea to get draft-hoffman-c2pq updated with these references. > Of course, these papers are focusing in on minimizing the number of > qubits; it's quite possible a trade-off that increases the number of > qubits, while decreasing the number of (say) T gates, would be > advantageous; we don't know enough about the relative costs to know. Yep, and how many bits we need more because of error correcting stuff etc. > > draft-hoffman-c2pq also says that we might have machines breaking > > AES-128 before than we have machines that can break Diffie-Hellman, i.e., it > > is most likely easier to make machine running Grover's algorithm than > > machine running Shor's algorithm. > > That work totally ignores the amount of time we're talking about > with O(2**64) computations (and parallelization is less helpful than > usual; Grover's becomes less efficient the more we parallelize it). Any idea how many computations needs to be done for the shor's algorithm, i.e., breaking 2048 bit Diffie-Hellman. I have just seen text saying it is polynominal time, but I have not really seen any guesses what the actual numbers are going to be. And I understand that there is also quite big classical computation pre- and post-processing steps too. > Also, the interesting algorithms in Quantum Chemical modelling are > significantly different from Grover's. It's possible that there are > some proposed protein folding problems that would use Grover's... -- [email protected] _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec
