[Cryptography] NSA looking for quantum-computing resistant encryption. How will encryption be affected by quantum computing

[Steve Weis]

On Wed, Sep 2, 2015 at 8:47 AM, ianG <iang at iang.org> wrote:
> On 31/08/2015 17:36 pm, Jerry Leichter wrote:
>> Just for comparison:
>>   The current record for factoring an integer using a quantum computer
>> is 56153, which you could factor by hand.
>
> Seems to be some discordance on that one - any chance of a cite?

This is the paper "Quantum factorization of 56153 with only 4 qubits":
http://arxiv.org/pdf/1411.6758v3.pdf

The authors rely on the factors of 56153 only differing in two
different bit positions (233 = 0b11101001, 241 = 0b11110001). They can
only factor composites with that special form (e.g. 143, 3599, 11663).
As the authors say in the paper: "[U]nless we know in advance that the
factors will differ at two bits, this reduction will not allow us to
crack big RSA codes." They also acknowledge that this "can easily be
solved by a classical computer, since there are only 4 variables".

As far as I know, the record of factoring with Shor's algorithm is 21
and described in this paper:
http://www.nature.com/nphoton/journal/v6/n11/abs/nphoton.2012.259.html

Here's a poster of their results:
http://new.qcmc2012.org/wp-content/uploads/2012/08/Poster_Martin-Lopez.pdf