Life In 19x19

i'm not worried about this breaking encryption. just double the size of the number that needs factoring. even if polynomial time to factor, it would take near to the end of time to do so.

phillip1882 wrote:i'm not worried about this breaking encryption. just double the size of the number that needs factoring. even if polynomial time to factor, it would take near to the end of time to do so.

Hmm then why are they saying that it would take 10 years to update their encryption based security . . ?

Elom0 wrote:AlphaGo would love this

Why precisely? It is not the case that quantum computers are faster general purpose computers. Today only a few problems are known that could be solved more quickly by a quantum computer in case a quantum computer could be built that can handle real world noise.

phillip1882 wrote:i'm not worried about this breaking encryption. just double the size of the number that needs factoring. even if polynomial time to factor, it would take near to the end of time to do so.

If factoring a number of M digits takes slightly over M^2 steps, then factoring a number of 2M digits takes slightly over 4M^2 steps, roughly 4 times as long, not to the end of time.

phillip1882 wrote:i'm not worried about this breaking encryption. just double the size of the number that needs factoring. even if polynomial time to factor, it would take near to the end of time to do so.

Factoring on a quantum computer is log(N) complexity. Doubling the size of the number only leads to a small increase in work.

There's a lot of work right now in quantum resistant encryption algorithms. AlphaGo may not be worried, but the banks are.

Factoring on a quantum computer is log(N) complexity. Doubling the size of the number only leads to a small increase in work.

no its polynomial rather than exponential.
i dont just mean doubling the number i mean doubling the number of bits it takes to represent.
for the sake of argument, lets say a 32 bit integer take 10 seconds to factor
a 64 bit integer would take 100 seconds.
a 128 bit integer would take 10000 seconds.
a 256 bit integer would take 100,000,000 seconds.
a 512 bit integer would take 100,000,000*100,000,000 seconds. and this is assuming a very generous N^2 complexity.

determining whether a number is prime is N^2 complexity by the number of bits, but factoring a number is a lot harder.

phillip1882 wrote:

Factoring on a quantum computer is log(N) complexity. Doubling the size of the number only leads to a small increase in work.

no its polynomial rather than exponential.
i dont just mean doubling the number i mean doubling the number of bits it takes to represent.
for the sake of argument, lets say a 32 bit integer take 10 seconds to factor
a 64 bit integer would take 100 seconds.
a 128 bit integer would take 10000 seconds.
a 256 bit integer would take 100,000,000 seconds.
a 512 bit integer would take 100,000,000*100,000,000 seconds. and this is assuming a very generous N^2 complexity.

determining whether a number is prime is N^2 complexity by the number of bits, but factoring a number is a lot harder.

Hmm. Are you confusing polynomial and exponential? I gave the approximately correct values. pwaldron's reply was essentially correct. A number N has M bits, where M is about log N. Shor's algorithm takes expected time O(M^2 log M loglog M), that is, roughly time O(M^2). Doubling the length of N would take roughly four times as long.

(M +1)^2 = M^2 +2*M aprox. going from 32 to 33 would be a difference of 64.
technically you're right. doubling the size of the number increases the complexity by a factor of 4.
but if you multiply by 4 enough times, it becomes too big.