Life In 19x19 :: The Next Computer

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.

Quote:

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.

Author:	Elom0 [ Mon Dec 12, 2022 9:09 pm ]
Post subject:	The Next Computer
AlphaGo would love this

Author:	phillip1882 [ Tue Dec 13, 2022 6:22 pm ]
Post subject:	Re: The Next Computer
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.

Author:	Elom0 [ Wed Dec 14, 2022 8:52 am ]
Post subject:	Re: The Next Computer
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 . . ?

Author:	vier [ Wed Dec 14, 2022 10:08 am ]
Post subject:	Re: The Next Computer
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.

Author:	pwaldron [ Wed Dec 14, 2022 11:33 am ]
Post subject:	Re: The Next Computer
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.

Life In 19x19 http://www.lifein19x19.com/

The Next Computer http://www.lifein19x19.com/viewtopic.php?f=8&t=19003	Page 1 of 1

Author:	phillip1882 [ Wed Dec 14, 2022 4:35 pm ]
Post subject:	Re: The Next Computer
Quote: 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.

Author:	vier [ Thu Dec 15, 2022 7:49 pm ]
Post subject:	Re: The Next Computer
phillip1882 wrote: Quote: 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.

Author:	phillip1882 [ Fri Dec 16, 2022 1:26 pm ]
Post subject:	Re: The Next Computer
(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.

Page 1 of 1	All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/