Is quantum computing a issue for bitcoin?

[organofcorti]

Back in 2009 Shor's algorithm had been used by a quantum computer to factorise the number 15. Anyone know what the most recent record is?

[Etlase2]

https://bitcointalk.org/index.php?topic=3008.0 an enlightening thread on this topic

Besides unbalanced oil & vinegar, NTRU exists today and has an open source implementation: http://en.wikipedia.org/wiki/NTRU
There are also one-time Lamport signatures + merkle trees that allow for more than one sig use: http://en.wikipedia.org/wiki/Lamport_signature

Both of these have serious downsides compared to ECDSA though, namely a lot more data is required for public keys and signatures. But they are quantum computer resistant.

[kjj]

Back in 2009 Shor's algorithm had been used by a quantum computer to factorise the number 15. Anyone know what the most recent record is?

15!  But this time with electrons, and this time it was really truly Quantum^TM, for sure.

Also, according to Wikipedia, the first factoring was done in 2001.  It may not have actually been a quantum event since entanglement wasn't observed, but I'd think that teaching an NMR machine to factor integers would be a bigger accomplishment!  After all, everyone "knows" that quantum computing is coming, but getting Shor's to work in a non-quantum computer would change the world.