RSA is obsolete

A preprint by White, James, Williams et al (names chosen randomly), some of whom hail from the Centre for Quantum Computing Technology at the Univeristy of Queensland have made groundbreaking progress in the effort to build a quantum computer capable of implementing Shor’s algorithm, and thus defeating the security of the most popular forms of data encryption.

The most common form of public key encryption used today is RSA (Rivest, Shamir, and A…something), which relies on the difficulty of factorising large numbers into their prime factors. More precisely, it is widely believed that the prime factorisation is not possible in polynomial time. RSA is the algorithm behind PGP (Pretty Good Privacy). Modern data security depends on the difficulty of this problem.

Now, Shor’s algorithm is a quantum algorithm for factorisation. It is accepted that, if a quantum computer existed, Shor’s algorithm could factorise numbers into their prime factors in polynomial time.

Willams et al haven’t done this, yet. But they have made significant progress in demonstrating that it is possible. This has major implications for data security. Why else would their work be partially funded by the US Disruptive Technologies office? New Scientist are right when they say that this will have profound implications.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: