Quantum Computers and stuff
-----BEGIN PGP SIGNED MESSAGE----- I found this in the May 6 issue of Science: >At the same press conference where Lenstra and company announced >the defeat of RSA-129,he promised a "surprise" for the next >factoring feat. He hinted at a new, faster algorithm- and >perhaps a test involving a number with quite a few more digits >than 129. Then I found this in the May 7 issue of Science News: >In a startling theoretical result that could call into question >any cryptosystem based on factoring, Peter W Shore of AT&T Bell >Laboratories in Murray Hill, N.J., has just proved that >factoring is "easy" when done on a special type of computer >operating according to quantum mechanical principles . Although >such a quantum computer does not yet exist, this finding has >shaken the cryptographic community. By "easy" I presume they mean solvable in Polynomical time. I'm not saying the writing is on the wall or anything but it might be prudent to start thinking about Diffe-Hellman, perhaps using elliptic curves. John K Clark johnkc@well.sf.ca.us -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCzAgUBLdbskn03wfSpid95AQFZuwTvVug954sJilmhlyR3Sye+LpCB9ktG+erw mfDHBbAUpYC34P/lL81dzekGj7hmMhOIgZklZn7h/XfgCydQihm0e+DHGC9h64nT AI6g2xHI5k/hH9QZRUPjFLwreaFeKX4ARy3rfWEgpGC7g1qqyPnKQi7TBuffyYCV 51NJ9lGzGjuSVIcDdHcGBIoTkMg1T8pH+Yr44jo/MehE86KB+/0= =pxVR -----END PGP SIGNATURE-----
Bob Silverman claims that Shore's result is largely bullshit. I haven't gotten any details yet, so I don't know for sure, but I'd say at this point panic is not yet in order. Perry John K Clark says:
>In a startling theoretical result that could call into question >any cryptosystem based on factoring, Peter W Shore of AT&T Bell >Laboratories in Murray Hill, N.J., has just proved that >factoring is "easy" when done on a special type of computer >operating according to quantum mechanical principles . Although >such a quantum computer does not yet exist, this finding has >shaken the cryptographic community.
By "easy" I presume they mean solvable in Polynomical time. I'm not saying the writing is on the wall or anything but it might be prudent to start thinking about Diffe-Hellman, perhaps using elliptic curves.
participants (2)
-
John K Clark -
Perry E. Metzger