“这破坏了RSA密码系统”

SVP算法的快速分解整数Claus Peter Schnorr摘要：为了分解整数$ N $，我们为第n个$ n的素数构造了$ n $个三元组$ p_n $个光滑整数$ u，v，| u-vN | $ $ p_n $。表示这样的三元关系。我们从晶格的几乎最短向量获得亲缘关系 $ \ mathcal {L}（\ mathbf {R} _ {n，f}）$和基本矩阵$ \ mathbf {R} _ {n，f} \ in \ mathbb {R} ^ {（n + 1）\次（n + 1）} $，其中 $ f：[1，n] \ rightarrow [1，n] $是$ [1,2，...，n] $和$（N f（1），...，N f（n ））$是$ \ mathbf {R} _ {n，f} $的对角线。我们从一个独立的排列$ f＆＃$获得一个独立的fac关系。我们通过对$ \ mathbf {R} _ {n，f} $进行强的原始对偶归约来找到足够短的晶格向量。我们以n = 47分解$ N \大约2 ^ {400} $，以n = 95分解$ N \大约2 ^ {800} $。[Gama，Nguyen 2008]的加速的强原始对偶分解是整数$ N \ approx 2 ^ {400} $和$ N \ approx 2 ^ {800} $通过$ 4.2 \ cdot 10 ^ 9 $和$ 8.4 \ cdot 10 ^ {10} $算术运算，比二次筛{\ bf QS快得多}和数字字段筛选{\ bf NFS}，并使用更小的素数$ p_n $。这破坏了RSA密码系统。类别/关键字：密钥加密/原始对偶还原，SVP，事实相关日期：2021年3月1日收到联系作者：schnorr at cs uni-frankfurt de可用格式：PDF | BibTeX引用版本：20210302：203341（此报告的所有版本）短URL：ia.cr/2021/232 [Cryptology ePrint存档]