The end of public key cryptography as we know it?

An article posted on sci.crypt stated that quantum factoring
is real and that an article was posted in this month's Science
magazine. The author of the post says this would make factoring
a 10 bit number the same time as factoring a 100000000 bit number.

A wonder how long it is before every major government in the world
has one of these. Makes RSA's future kind of moot doesn't it??

I definitely have to read this article, but I thought I'd post it
here for those that weren't aware or that hadn't heard.

I wonder how long it will take before they can figure out how to
do this for other computationally intensinve problems like N-th roots.
(To make Diffie Hellman moot as well).

It's beginning to seem that mathematically challenging algorithms
aren't going to be that challenging for long.  I have no details other
than what is posted here.

Perhaps somebody could post a better synopsis than what was in
sci.crypt? (I plan on reading it for myself anyway, which I imagine
most other people here will be doing as soon as they can)

 Doug Hughes				Engineering Network Services
 doug@eng.auburn.edu			Auburn University

From: Doug Hughes <Doug.Hughes@eng.auburn.edu>
   Date: Thu, 13 Jul 1995 13:46:10 -0500

   An article posted on sci.crypt stated that quantum factoring
   is real and that an article was posted in this month's Science
   magazine. The author of the post says this would make factoring
   a 10 bit number the same time as factoring a 100000000 bit number.

You can bet your ass and your mother's and grandmother's donatable
organs that if this were possible, then the legislative initiatives
currently underway would not be: they'd just let us use RSA and get
a false sense of security.

   A wonder how long it is before every major government in the world
   has one of these. Makes RSA's future kind of moot doesn't it??

Well, it would probably "prove" many-worlds right: in which case
we're probably going to be invaded from the one where the Nazis
won WWII, or the libertarians won Shay's Rebellion.

Phil,

>    An article posted on sci.crypt stated that quantum factoring
>    is real and that an article was posted in this month's Science
>    magazine. The author of the post says this would make factoring
>    a 10 bit number the same time as factoring a 100000000 bit number.
> 
> You can bet your ass and your mother's and grandmother's donatable
> organs that if this were possible, then the legislative initiatives
> currently underway would not be: they'd just let us use RSA and get
> a false sense of security.
> 
>    A wonder how long it is before every major government in the world
>    has one of these. Makes RSA's future kind of moot doesn't it??
> 
> Well, it would probably "prove" many-worlds right: in which case
> we're probably going to be invaded from the one where the Nazis
> won WWII, or the libertarians won Shay's Rebellion.

Yuk yuk. :>

A minor adjustment to your comment: I haven't read the work yet, but
if it's based on Shor and Simon, it only "proves" the existence of
state superpositions (and perhaps some other mathematical things
relating to the construction of unitary transforms) - a fact equally
congenial to Many Worlds, Copenhagen, von Neumann, and most other
interpretations of quantum mechanics.  The only people who would
likely be upset by this are the neo-materialists and other
hidden-variable fetishists.

I'm six hundred messages behind and not likely to catch up soon, so
apologies if this has already been covered.

   - Mark -

--
Mark Chen 
chen@intuit.com
415/329-6913
finger for PGP public key
D4 99 54 2A 98 B1 48 0C  CF 95 A5 B0 6E E0 1E 1D