[Cryptography] D-Wave, RSA, and DLP

[Steve Weis]

On Fri, Mar 27, 2015 at 3:59 AM, Mattias Aabmets <mattias.aabmets at gmail.com>
wrote:

> I just stumbled on an article from phys.org
> <http://phys.org/news/2014-11-largest-factored-quantum-device.html> and
> it got me thinking.
>
> If they managed to factor 56 153 with adiabatic quantum computations, i.e.
> optimisation, using only 4 qbits,
> then it follows that D-Wave, which is designed to solve optimization
> problems and has 512 bits, is capable of
> factoring 512 bit long composite numbers.
>
>
You should read the Dattani & Bryans paper:
http://arxiv.org/pdf/1411.6758v3.pdf

They can only factor numbers that have a special form where the factors
differ in a limited number of bits. As the paper says "unless we know in
advance that the factors will differ at two bits, this reduction will not
allow us to crack big RSA codes".

That's how they are able to succinctly represent a 16-bit number if
4-qubits. I think they're encoding the two indices of the bit differences.

The probability of an RSA moduli having this property is exponentially
small. I see no practical consequence to RSA, DLP, or ECC security.

When it comes to D-Wave, it's still debatable whether it's benefiting from
any quantum effects or is even a good at solving the problems it is
designed for. I don't know the area well enough to comment and we will not
come to any conclusion on this mailing list.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150327/37d32c4e/attachment.html>