All Questions
Tagged with quantum-computing discrete-logarithm
4
questions
3
votes
2
answers
577
views
Why is discrete logarithm not quantum proof?
I don't understand why discrete logarithm is not quantum proof. I understand that quantum computer can quickly compute the exponent, but there is a modulo in the equation. Doesn't it mean, that there ...
- 31
4
votes
0
answers
77
views
Comparing quantum computing resources to break the DLP on elliptic curve group vs Schnorr group
Take an elliptic curve group of 256-bit prime order $n$ over a 256-bit prime field in which the Discrete Logarithm Problem is believed hard, e.g. secp256r1. Build an isomorphic Schnorr group by taking ...
- 143k
4
votes
1
answer
139
views
Difficulty of Shor's algorithm in a Schnorr group as a function of the modulus
Consider a Schnorr group with order a prime $q$ sized for security against current computers (like $q$ of 256 bit); modulus a prime $p=q\,r+1$ large enough (e.g. 3072 to 32768-bit) that the algorithms ...
- 143k
17
votes
0
answers
426
views
Fewest qubits required for the discrete logarithm problem and integer factorization
According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
- 15.4k