量子计算机为什么会卡在格上

Shor 算法一步就吃掉 RSA。同一台机器面对一张加了点噪声的点阵,却几乎无从下手。一个滑块就能看出差别。

阶段 Shor
  1. 0
  2. 1
  3. 2
  4. 3
  5. 4

点按图中的某一段,即可打开该阶段。

真正改变的是什么

RSA 把秘密藏在一个问题里,而量子计算机偏偏会问这个问题。格把秘密藏在一个对两种机器都保持指数难度的问题里——而握有短基的人,干脆绕过了这个问题。

内容一览

  1. 1 分解质因数不再是难题 — 数学并没有出问题,只是「难」被放错了地方。
  2. 2 用点代替数 — 格本身是公开的,点谁都看得见。
  3. 3 消息是一个点,然后被推了一下 — 噪声小到可以被消掉,又大到足以藏起你从哪个点出发。
  4. 4 找最近的格点,就是全部难题 — 已知的量子算法能削掉这道题的指数一部分,却削不掉指数本身。
  5. 5 换成对的基,只要一次取整 — 秘密不是格,而是对格的一份好描述。

可交互的讲解

阶段 Shor
  1. 0
  2. 1
  3. 2
  4. 3
  5. 4
1 / 5