It is currently Sat Feb 24, 2024 4:44 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 8 posts ] 
Author Message
Offline
 Post subject: The Next Computer
Post #1 Posted: Mon Dec 12, 2022 9:09 pm 
Lives in sente

Posts: 720
Liked others: 1011
Was liked: 30
Rank: BGA 3 kyu
KGS: Elom, Windnwater
OGS: Elom, Elom0
Online playing schedule: The OGS data looks pretty so I'll pause for now before I change it.
AlphaGo would love this

Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #2 Posted: Tue Dec 13, 2022 6:22 pm 
Lives in gote

Posts: 319
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
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.


This post by phillip1882 was liked by: Elom0
Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #3 Posted: Wed Dec 14, 2022 8:52 am 
Lives in sente

Posts: 720
Liked others: 1011
Was liked: 30
Rank: BGA 3 kyu
KGS: Elom, Windnwater
OGS: Elom, Elom0
Online playing schedule: The OGS data looks pretty so I'll pause for now before I change it.
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 . . ?

Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #4 Posted: Wed Dec 14, 2022 10:08 am 
Dies with sente

Posts: 89
Liked others: 8
Was liked: 27
Elom0 wrote:

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.

Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #5 Posted: Wed Dec 14, 2022 11:33 am 
Lives in gote

Posts: 392
Liked others: 29
Was liked: 176
GD Posts: 1072
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.

Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #6 Posted: Wed Dec 14, 2022 4:35 pm 
Lives in gote

Posts: 319
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
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.

Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #7 Posted: Thu Dec 15, 2022 7:49 pm 
Dies with sente

Posts: 89
Liked others: 8
Was liked: 27
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.

Top
 Profile  
 
Offline
 Post subject: Re: The Next Computer
Post #8 Posted: Fri Dec 16, 2022 1:26 pm 
Lives in gote

Posts: 319
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
(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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group