[Cryptography] D-Wave, RSA, and DLP

[Viktor Dukhovni]

On Fri, Mar 27, 2015 at 12:59:25PM +0200, Mattias Aabmets wrote:
> Greetings!
> 
> 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.

No such thing follows.  Look at page 3 of:

    http://arxiv.org/pdf/1411.6758v3

    The equations obtained from adding the columns in the multiplication
    table are then:

	p1 +q1 = 0+2z1,2
	p2 +p1q1 +q2 +z1,2 = 0+2z2,3 +4z2,4 p3 +p2q1 +p1q2 +q3 +z2,3 = 1+2z3,4 +4z3,5
	...
	q6 + p6 + z12,13 + z11,13 + z10,13 = 0 + 2z13,14 + 4z13,15 1 + z13,14 + z12,14 + z11,14 = 1 + 2z14,15
	z14,15 + z13,15 = 1

    and when the simplification rules are applied automatically by
    a computer program, most pi and qi are already determined, and
    the result is this set of equations:

	    p3+q3 = 1 (16)
	    p4+q4 = 1 (17)
	    p4q3 + p3q4 = 1. (18)

and guess how what fraction of large semiprimes admit the radical
algebraic simplifications (performed by a classical computer) to
equations such as equations 16/17/18.  What is the run-time of the
portion of the algorithm that simplifies the equtions?

Notice the comment that for the system shown the simplifications
are due to the fact that:

    "In fact, it turns out that the product of any two numbers
    differing at only 2 bits will lead to the equations: ..."

So this is a highly-specialized result.  No need to panic (yet).

-- 
	Viktor.