<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Mar 27, 2015 at 3:59 AM, Mattias Aabmets <span dir="ltr"><<a href="mailto:mattias.aabmets@gmail.com" target="_blank">mattias.aabmets@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>I just stumbled on <a href="http://phys.org/news/2014-11-largest-factored-quantum-device.html" target="_blank">an article from phys.org</a> and it got me thinking.</div><div><br></div><div>If they managed to factor 56 153 with adiabatic quantum computations, i.e. optimisation, using only 4 qbits,  </div><div>then it follows that D-Wave, which is designed to solve optimization problems and has 512 bits, is capable of  <br></div><div>factoring 512 bit long composite numbers.  </div><div><br></div></div></blockquote><div><br>You should read the Dattani & Bryans paper: <a href="http://arxiv.org/pdf/1411.6758v3.pdf">http://arxiv.org/pdf/1411.6758v3.pdf</a></div><div><br></div><div>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".<br></div><div><br>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.<br><br>The probability of an RSA moduli having this property is exponentially small. I see no practical consequence to RSA, DLP, or ECC security.<br><br>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.<br></div></div></div></div>