{"id":121,"date":"2025-03-31T13:13:00","date_gmt":"2025-03-31T05:13:00","guid":{"rendered":"http:\/\/www.triode.cc\/?p=121"},"modified":"2025-09-29T00:23:55","modified_gmt":"2025-09-28T16:23:55","slug":"lattice-based-cryptography","status":"publish","type":"post","link":"https:\/\/www.triode.cc\/index.php\/2025\/03\/31\/lattice-based-cryptography\/","title":{"rendered":"\u683c\u5bc6\u7801"},"content":{"rendered":"\n
\n

\u53c2\u8003\u8d44\u6599\uff1a<\/p>\n\n\n\n

(1) A Gentle Tutorial for Lattice-Based Cryptanalysis<\/a><\/p>\n\n\n\n

(2) Improved low-density subset sum algorithms<\/a><\/p>\n\n\n\n

(3) Solving low-density multiple subset sum problems with SVP oracle<\/a><\/p>\n\n\n\n

(4) Extended Hidden Number Problem and Its Cryptanalytic Applications<\/a><\/p>\n\n\n\n

(5) Extending Wiener\u2019s Attack in the Presence of Many Decrypting Exponents<\/a><\/p>\n<\/blockquote>\n\n\n\n

\u683c\uff08Lattice\uff09<\/h2>\n\n\n\n

\u683c\u7684\u6982\u5ff5<\/h3>\n\n\n\n

\u5b9a\u4e49<\/strong>\uff1a\u4e00\u4e2a\\(n\\)\u7ef4\u7684\u683c\\(\\mathcal{L}\\)\u662f\\(\\mathbb{R}^{n}\\)\u7684\u4e00\u4e2a\u79bb\u6563\u53ef\u52a0\u7684\u5b50\u7fa4. \u5bf9\u4e8e\u683c\\(\\mathcal{L}\\)\uff0c\u5176\u53ef\u4ee5\u88ab\u8868\u793a\u4e3a\u7531\\(\\mathbb{R}^{n}\\)\u4e0a\\(m\\)\u4e2a\u7ebf\u6027\u65e0\u5173\u7684\u57fa\u5411\u91cf\\(\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_m\\}\\)\u7ec4\u6210\u7684\u57fa\\(\\pmb{B}\\)\uff0c\u5411\u91cf\u7684\u4e2a\u6570\\(m\\)\u88ab\u79f0\u4e3a\u683c\\(\\mathcal{L}\\)\u7684\u79e9\uff0c\u6240\u4ee5\u683c\\(\\mathcal{L}\\)\u4e5f\u80fd\u8868\u793a\u4e3a\uff1a<\/p>\n\n\n\n

$$
\\mathcal{L}=\\mathcal{L}(\\pmb{B})=\\left\\{\\sum_{i=1}^{m}a_i\\pmb{b}_i|a_i\\in\\mathbb{Z},i=1,2,\\cdots,m\\right\\}
$$<\/p>\n\n\n\n

\u683c\u7684\u5f88\u591a\u6027\u8d28\u4e0e\u8bb0\u53f7\u4e0e\u7ebf\u6027\u7a7a\u95f4\uff08\u5411\u91cf\u7a7a\u95f4\uff09\u7c7b\u4f3c\u3002 <\/p>\n\n\n\n

\u9010\u6b21\u6700\u5c0f\u957f\u5ea6<\/strong>\uff1a\u5bf9\u4e8e\u4e00\u4e2a\u79e9\u7ef4\\(n\\)\u7684\u683c\\(\\mathcal{L}\\)\uff0c\u5bf9\u4e8e\\(i\\in\\{1,2,\\cdots n\\}\\)\uff0c\u82e5\\(r\\)\u662f\u4f7f\u5f97\u683c\\(\\mathcal{L}\\)\u62e5\u6709\\(i\\)\u4e2a\u957f\u5ea6\u6700\u5927\u4e3a\\(r\\)\u4e14\u7ebf\u6027\u65e0\u5173\u7684\u5411\u91cf\u7684\u6700\u5c0f\u503c\uff0c\u5219\u79f0\\(r\\)\u4e3a\u683c\\(\\mathcal{L}\\)\u7684\u7b2c\\(i\\)\u9010\u6b21\u6700\u5c0f\u957f\u5ea6\uff0c\u8bb0\u4e3a\\(\\lambda_i(\\mathcal{L})=r\\) <\/p>\n\n\n\n

\u5173\u4e8e\u9010\u6b21\u6700\u5c0f\u957f\u5ea6\uff0c\u6211\u4eec\u6709\u95f5\u53ef\u592b\u65af\u57fa\uff08Minkowski\uff09\u7b2c\u4e00\u5b9a\u7406\uff1a<\/p>\n\n\n\n

\u95f5\u53ef\u592b\u65af\u57fa\uff08Minkowski\uff09\u7b2c\u4e00\u5b9a\u7406<\/strong>\uff1a\u8bbe\\(\\mathcal{L}\\)\u662f\u4e00\u4e2a\\(n\\)\u7ef4\u6ee1\u79e9\u683c\uff0c\u5219\uff1a<\/p>\n\n\n\n

$$
\\lambda_1(\\mathcal{L})\\le\\sqrt{n}|\\det(\\mathcal{L})|^{1\/n}
$$<\/p>\n\n\n\n

\u95f5\u53ef\u592b\u65af\u57fa\u7b2c\u4e00\u5b9a\u7406\u8868\u660e\u6211\u4eec\u53ef\u4ee5\u4ee5\\(\\lambda_1(\\mathcal{L})\\)\u4e3a\u6807\u51c6\u6765\u8bc4\u5224\u683c\u4e2d\u5411\u91cf\u7684\u957f\u5ea6.<\/p>\n\n\n\n

\u5173\u4e8e\u683c\u7684\u95ee\u9898<\/h3>\n\n\n\n

\u6700\u77ed\u5411\u91cf\u95ee\u9898<\/strong>\uff08Shortest Vector Problem, \\(\\text{SVP}\\)\uff09\uff1a\u7ed9\u5b9a\u683c\\(\\mathcal{L}\\)\u7684\u57fa\\(\\pmb{B}\\)\uff0c\u627e\u5230\u683c\\(\\mathcal{L}\\)\u4e0a\u7684\u4e00\u4e2a\u975e\u96f6\u5411\u91cf\\(\\pmb{v}\\)\u6ee1\u8db3\\(||\\pmb{v}||=\\lambda_1(\\mathcal{L})\\). <\/p>\n\n\n\n

\u6700\u8fd1\u5411\u91cf\u95ee\u9898<\/strong>\uff08Closest Vector Problem, \\(\\text{CVP}\\)\uff09\uff1a\u7ed9\u5b9a\u683c\\(\\mathcal{L}\\)\u7684\u57fa\\(\\pmb{B}\\)\u4ee5\u53ca\u4e00\u4e2a\u76ee\u6807\u5411\u91cf\\(\\pmb{t}\\)\uff08\u4e0d\u4e00\u5b9a\u5728\u683c\\(\\mathcal{L}\\)\u4e0a\uff09\uff0c\u627e\u5230\u683c\\(\\mathcal{L}\\)\u4e0a\u7684\u4e00\u4e2a\u975e\u96f6\u5411\u91cf\\(\\pmb{v}\\)\u6ee1\u8db3<\/p>\n\n\n\n

$$
||\\pmb{v}-\\pmb{t}||=\\min_{\\pmb{w}\\in\\mathcal{L}}||\\pmb{w}-\\pmb{t}||
$$<\/p>\n\n\n\n

\u4e0a\u8ff0\u95ee\u9898\u5747\u4e3aNP-Hard\u95ee\u9898\uff0c\u8fd9\u4e9b\u95ee\u9898\u7684\u5bbd\u677e\u7248\u672c\u5982\u4e0b\uff1a <\/p>\n\n\n\n

\u8fd1\u4f3c\u6700\u77ed\u5411\u91cf\u95ee\u9898<\/strong>\uff08Approximate Shortest Vector Problem, \\(\\text{SVP}_{\\gamma}\\)\uff09\uff1a\u7ed9\u5b9a\u683c\\(\\mathcal{L}\\)\u7684\u57fa\\(\\pmb{B}\\)\u4e0e\u8fd1\u4f3c\u56e0\u5b50\\(\\gamma\\)\uff0c\u627e\u5230\u683c\\(\\mathcal{L}\\)\u4e0a\u7684\u4e00\u4e2a\u975e\u96f6\u5411\u91cf\\(\\pmb{v}\\)\u6ee1\u8db3\\(||\\pmb{v}||\\le\\gamma\\cdot\\lambda_1(\\mathcal{L}\\)). <\/p>\n\n\n\n

\u8fd1\u4f3c\u6700\u8fd1\u5411\u91cf\u95ee\u9898<\/strong>\uff08Approximate Closest Vector Problem, \\(\\text{CVP}_{\\gamma}\\)\uff09\uff1a\u7ed9\u5b9a\u683c\\(\\mathcal{L}\\)\u7684\u57fa\\(\\pmb{B}\\)\u3001\u4e00\u4e2a\u76ee\u6807\u5411\u91cf\\(\\pmb{t}\\)\uff08\u4e0d\u4e00\u5b9a\u5728\u683c\\(\\mathcal{L}\\)\u4e0a\uff09\u4ee5\u53ca\u4e00\u4e2a\u8fd1\u4f3c\u56e0\u5b50\\(\\gamma\\)\uff0c\u627e\u5230\u683c\\(\\mathcal{L}\\)\u4e0a\u7684\u4e00\u4e2a\u975e\u96f6\u5411\u91cf\\(\\pmb{v}\\)\u6ee1\u8db3<\/p>\n\n\n\n

$$
||\\pmb{v}-\\pmb{t}||=\\gamma\\cdot\\min_{\\pmb{w}\\in\\mathcal{L}}||\\pmb{w}-\\pmb{t}||
$$<\/p>\n\n\n\n

\u800c\\(\\text{SVP}_{\\gamma}\\)\u4e0e\\(\\text{CVP}_{\\gamma}\\)\u5bf9\u4e8e\u786e\u5b9a\u7684\u53c2\u6570\u5747\u5b58\u5728\u6709\u6548\u7684\u89e3\u51b3\u65b9\u6848\uff0c\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u89e3\u51b3\\(\\text{SVP}_{\\gamma}\\)\u4e0e\\(\\text{CVP}_{\\gamma}\\)\u6765\u8fd1\u4f3c\u5730\u89e3\u51b3\\(\\text{SVP}\\)\u4e0e\\(\\text{CVP}\\). \u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u683c\u57fa\u89c4\u7ea6\u6765\u89e3\u51b3\u4e0a\u8ff0\u4e24\u4e2a\u53ef\u8ba1\u7b97\u95ee\u9898.<\/p>\n\n\n\n

\u683c\u57fa\u89c4\u7ea6<\/h3>\n\n\n\n

\u683c\u57fa\u89c4\u7ea6\u7684\u76ee\u6807\u662f\u5c06\u4e00\u4e2a\u4efb\u610f\u4e00\u4e2a\u683c\u8f6c\u5316\u4e3a\u53e6\u5916\u4e00\u4e2a\u57fa\u76f8\u540c\u4f46\u662f\u5177\u6709\u66f4\u77ed\u3001\u66f4\u591a\u7684\u6b63\u4ea4\u5411\u91cf\u3002\u7531\u4e8e\u6211\u4eec\u8981\u627e\u7684\u662f\u201c\u77ed\u5411\u91cf\u201d\uff0c\u6240\u4ee5\u683c\u57fa\u89c4\u7ea6\u53ef\u80fd\u4f1a\u63d0\u4f9b\u89e3\u51b3\u8fd1\u4f3c\u6700\u77ed\u5411\u91cf\u95ee\u9898\u7684\u65b9\u6cd5.<\/p>\n\n\n\n

LLL\u7b97\u6cd5<\/h4>\n\n\n\n

LLL\u7b97\u6cd5\u662f\u4e00\u4e2a\u8fed\u4ee3\u7b97\u6cd5\uff0c\u7531Lenstra\u3001Lenstra\u4e0eLov\u00e1sz\u63d0\u51fa. \u8fd9\u4e2a\u8fed\u4ee3\u7b97\u6cd5\u7684\u7b2c\u4e00\u6b65\u662f\u901a\u8fc7\u65bd\u5bc6\u7279\u6b63\u4ea4\u5316\u83b7\u5f97\u57fa\\(\\pmb{B}=\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_n\\}\\)\u7684\u4e00\u7ec4\u6b63\u4ea4\u57fa\uff0c\u901a\u8fc7\u65bd\u5bc6\u7279\u6b63\u4ea4\u5316\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u683c\u57fa\u8fdb\u884c\u7ea6\u51cf\uff0c\u5bf9\u4e8e\u4e0a\u9762\u7684\u57fa\\(\\pmb{B}\\)\uff0c\u65bd\u5bc6\u7279\u6b63\u4ea4\u5316\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n\n\n\n

$$
\\begin{cases} \\pmb{b}_i^{*}=\\pmb{b}_i,&i=1\\\\ \\pmb{b}_i^{*}=\\pmb{b}_i-\\sum_{j=1}^{i-1}\\mu_{i,j}\\pmb{b}_j^{*},&1<i\\le n \\end{cases}\\kern{25pt}\\mu_{i,j}=\\frac{\\langle\\pmb{b}_i,\\pmb{b}_{j}^{*}\\rangle}{\\langle\\pmb{b}^{*}_{j},\\pmb{b}^{*}_{j}\\rangle}
$$<\/p>\n\n\n\n

\u800c\u5bf9\u4e8e\\(\\delta\\in(\\frac{1}{4},1)\\)\uff0c\u5982\u679c\u57fa\\(\\pmb{B}=\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_n\\}\\)\u6ee1\u8db3\uff1a<\/p>\n\n\n\n

    \n
  1. \uff08\u5c3a\u5bf8\u7ea6\u51cf\uff0csize-reduction\uff09\u5bf9\u4e8e\u4efb\u610f\\(i>j\\)\uff0c\u6709\\(|\\mu_{i,j}|\\le\\frac{1}{2}\\)\uff1b<\/li>\n\n\n\n
  2. \uff08Lov\u00e1sz\u6761\u4ef6\uff0cLov\u00e1sz condition\uff09\u5bf9\u4e8e\u4efb\u610f\\(i\\in\\{1,2,\\cdots,n-1\\}\\)\uff0c\u6709\\((\\delta-\\mu_{i+1,i}^{2})||\\pmb{b}_{i}^{*}||^{2}\\le||\\pmb{b}_{i+1}^{*}||^2\\)<\/li>\n<\/ol>\n\n\n\n

    \u5219\u79f0\u57fa\\(\\pmb{B}\\)\u4e3a\\(\\delta\\)-LLL\u7ea6\u51cf\u57fa\uff0c\u901a\u8fc7\u7ed3\u5408\u8fd9\u4e24\u4e2a\u6761\u4ef6\uff0cLenstra\u3001Lenstra\u4e0eLov\u00e1sz\u7ed9\u51fa\u4e86LLL\u7b97\u6cd5\uff1a<\/p>\n\n\n

    \n
    \"\"<\/div><\/a><\/figure>\n<\/div>\n\n\n

    \u800c\u5bf9\u4e8e\u683c\u4e2d\u6700\u77ed\u5411\u91cf\u7684\u4e0b\u754c\uff0c\u6211\u4eec\u6709\u5982\u4e0b\u5b9a\u7406\uff1a \u8bbe\u683c\u57fa\\(\\pmb{B}=\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_n\\}\\)\u5bf9\u5e94\u7684\u65bd\u5bc6\u7279\u6b63\u4ea4\u57fa\u4e3a\u57fa\\(\\pmb{B}^*=\\{\\pmb{b}_1^*,\\pmb{b}_2^*,\\cdots,\\pmb{b}_n^*\\}\\)\uff0c\u5219\u6709\uff1a<\/p>\n\n\n\n

    $$
    \\lambda_1(\\mathcal{L}(\\pmb{B}))\\ge\\min_{i\\in\\{1,\\cdots,n\\}}||\\pmb{b}^{*}_{i}||
    $$<\/p>\n\n\n\n

    \u901a\u8fc7\u8fd9\u4e2a\u5b9a\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u5bfc\u51fa\u5982\u4e0b\u547d\u9898\uff1a \u5047\u82e5\\(\\pmb{B}=\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_n\\}\\)\u662f\u4e00\u4e2a\\(\\delta\\)-LLL\u7ea6\u51cf\u57fa\uff0c\u5219\u5fc5\u7136\u6709\uff1a<\/p>\n\n\n\n

    $$
    ||\\pmb{b}_1||\\le\\left(\\frac{2}{\\sqrt{4\\delta-1}}\\right)^{n-1}\\sqrt{n}\\cdot|\\det(\\mathcal{L})|^{1\/n}
    $$<\/p>\n\n\n\n

    \u8fd9\u6761\u5f0f\u5b50\u5f80\u5f80\u53ef\u4ee5\u5e2e\u52a9\u6211\u4eec\u5224\u65ad\u4e00\u4e2a\u683c\u57fa\u662f\u5426\u80fd\u901a\u8fc7LLL\u6765\u7ea6\u51cf\u51fa\u6700\u77ed\u5411\u91cf. \u5728sage\u4e2d\u5185\u7f6e\u4e86\u73b0\u6210\u7684LLL\u7b97\u6cd5\uff0c\u4f8b\u5982\u6211\u4eec\u8981\u89e3\u51b3A Gentle Tutorial for Lattice-Based Cryptanalysis<\/a>\u4e2d\u7684\u4f8b3.12\uff08\u5982\u4e0b\u56fe\uff09\uff1a<\/p>\n\n\n

    \n
    \"\"<\/div><\/a><\/figure>\n<\/div>\n\n\n

    \u5219\u53ef\u4ee5\u901a\u8fc7\u4e0b\u9762\u7684\u6b65\u9aa4\u6765\u83b7\u5f97\u7ed3\u679c\uff1a<\/p>\n\n\n

    \n
    \"\"<\/div><\/a><\/figure>\n<\/div>\n\n\n

    \u663e\u7136\u53ef\u4ee5\u5f97\u5230\u7ed3\u679c\u4e3a\\(\\pmb{b}_1^*=(0,-1),\\pmb{b}_2^*=(-2,0)\\).<\/p>\n\n\n\n

    \u89e3\u51b3CVP<\/h3>\n\n\n\n

    LLL\u7b97\u6cd5\u540c\u6837\u53ef\u4ee5\u7528\u6765\u89e3\u51b3\u8fd1\u4f3c\u6700\u8fd1\u5411\u91cf\u95ee\u9898\uff0c\u4f46\u662f\u9700\u8981\u7ed3\u5408Babai\u6700\u8fd1\u5e73\u9762\u7b97\u6cd5\u6216\u8005Kannan\u5d4c\u5165\u6cd5<\/p>\n\n\n\n

    Babai\u6700\u8fd1\u5e73\u9762\u7b97\u6cd5\uff08Babai\u2019s Nearest Plane Algorithm\uff09<\/h4>\n\n\n\n

    Babai\u6700\u8fd1\u5e73\u9762\u7b97\u6cd5\u9996\u5148\u8981\u83b7\u5f97\u8f93\u5165\u683c\u7684\u7ea6\u51cf\u57fa\\(\\pmb{B}=\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_n\\}\\)\uff0c\u7136\u540e\u5bf9\u4e8e\u76ee\u6807\u5411\u91cf\\(\\pmb{t}\\)\uff0c\u6211\u4eec\u4ee4\\(\\pmb{t}’=\\pmb{t}-c_n\\pmb{b}_n\\)\uff0c\u5176\u4e2d\uff1a\\(c_n=\\lceil\\langle\\pmb{t},\\pmb{b}^*_{n}\\rangle\/\\langle\\pmb{b}^*_{n},\\pmb{b}^*_{n}\\rangle\\rfloor\\)\uff08\u5176\u4e2d\\(\\lceil\\cdot\\rfloor\\)\u8868\u793a\u56db\u820d\u4e94\u5165\uff09\uff0c\u7136\u540e\u5bf9\u524d\\(n-1\\)\u4e2a\u5411\u91cf\u4e0e\\(\\pmb{t}’\\)\u8fdb\u884c\u64cd\u4f5c\uff0c\u5f97\u5230\\(\\pmb{t}”=\\pmb{t}’-c_{n-1}\\pmb{b}_{n-1}\\)\uff0c\u5176\u4e2d\\(c_n=\\lceil\\langle\\pmb{t}’,\\pmb{b}^*_{n-1}\\rangle\/\\langle\\pmb{b}^*_{n-1},\\pmb{b}^*_{n-1}\\rangle\\rfloor\\)\uff0c\u4ee5\u6b64\u7c7b\u63a8\uff0c\u5c31\u53ef\u4ee5\u5f97\u5230\u5b8c\u6574\u7684Babai\u6700\u8fd1\u5e73\u9762\u7b97\u6cd5\uff1a<\/p>\n\n\n

    \n
    \"\"<\/div><\/a><\/figure>\n<\/div>\n\n\n

    Kannan\u5d4c\u5165\u6cd5<\/h4>\n\n\n\n

    Kannan\u5d4c\u5165\u6cd5\u662f\u901a\u8fc7\u5c06\u76ee\u6807\u5411\u91cf\u5d4c\u5165\u683c\u57fa\uff0c\u4ece\u800c\u5c06CVP\u8f6c\u5316\u4e3aSVP\u8fdb\u884c\u6c42\u89e3\uff0c\u8bbe\u8f93\u5165\u7684\u683c\u57fa\u4e3a\\(\\pmb{B}=\\{\\pmb{b}_1,\\pmb{b}_2,\\cdots,\\pmb{b}_n\\}\\)\uff0c\u800c\u76ee\u6807\u5411\u91cf\u4e3a\\(\\pmb{t}=(t_1,t_2,\\cdots,t_n)\\)\uff0c\u6211\u4eec\u8bbeCVP\u7684\u89e3\u4e3a\\(c_1\\pmb{b}_1+c_2\\pmb{b}_2+\\cdots+c_n\\pmb{b}_n\\)\uff0c\u5373\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{t}\\approx\\sum_{i=1}^{n}c_i\\pmb{b}_i
    $$<\/p>\n\n\n\n

    \u4e5f\u5c31\u6709\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{t}=\\sum_{i=1}^{n}c_i\\pmb{b}_i+\\pmb{e}
    $$<\/p>\n\n\n\n

    \u5176\u4e2d\\(||\\pmb{e}||\\)\u5f88\u5c0f\uff0c\u6240\u4ee5\u6211\u4eec\u5c31\u53ef\u4ee5\u6784\u9020\u51fa\u4e00\u4e2a\\(n+1\\)\u7ef4\u7684\u683c\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{B}’= \\left(\\begin{matrix} \\pmb{B}&0\\\\ \\pmb{t}&q \\end{matrix}\\right)
    $$<\/p>\n\n\n\n

    \u56e0\u4e3a\u6709\uff1a<\/p>\n\n\n\n

    $$
    (-c_1,-c_2,\\cdots,-c_n,1)\\pmb{B}’=(\\pmb{e},q)
    $$<\/p>\n\n\n\n

    \u6240\u4ee5\u8fd9\u4e2a\u683c\u663e\u7136\u5305\u542b\u77ed\u5411\u91cf\\((\\pmb{e},q)\\)\uff0c\u7531\u6b64\u6211\u4eec\u5c31\u53ef\u4ee5\u5f97\u5230CVP\u7684\u89e3\u4e3a\\(\\pmb{t}-\\pmb{e}\\). \u5728\u8fd9\u91cc\uff0c\u6574\u6570\\(q\\)\u79f0\u4e3a\u5d4c\u5165\u56e0\u5b50\uff0c\u5b83\u4f1a\u5f71\u54cd\u5230\u901a\u8fc7LLL\u7b97\u6cd5\u5bfb\u627e\u6b63\u786e\u5411\u91cf\u7684\u6210\u529f\u7387\uff0c\u5e94\u6839\u636e\u5b9e\u9645\u60c5\u51b5\u9009\u53d6.<\/p>\n\n\n\n

    \u683c\u5728\u5bc6\u7801\u5b66\u4e2d\u7684\u5e94\u7528<\/h2>\n\n\n\n

    \u80cc\u5305\u95ee\u9898\uff08Knapsack Problem\uff09<\/h3>\n\n\n\n

    \u80cc\u5305\u95ee\u9898\u662fNP\u5b8c\u5168\u95ee\u9898\uff0c\u5176\u7ecf\u5e38\u88ab\u7528\u4e8e\u4f5c\u4e3a\u516c\u94a5\u5bc6\u7801\u4f53\u7cfb\u7684\u9677\u9631\u95e8\u3002\u5728\u5bc6\u7801\u5b66\u4e2d\uff0c\u80cc\u5305\u95ee\u9898\u7684\u5e38\u89c1\u7248\u672c\u4e3a\u5b50\u96c6\u548c\u95ee\u9898\uff0c\u5373\uff1a\u7ed9\u5b9a\\(n\\)\u4e2a\u6b63\u6570\\(a_1,a_2,\\cdots,a_n\\)\u4e0e\u4e00\u4e2a\u6574\u6570\\(s\\)\uff0c\u5bfb\u627e\u96c6\u5408\\(\\{a_1,a_2,\\cdots,a_n\\}\\)\u7684\u5b50\u96c6\u4f7f\u5f97\u5176\u548c\u4e3a\\(s\\)\u3002\u4e5f\u5c31\u662f\u627e\u5230\\(e_1,e_2,\\cdots,e_n\\in\\{0,1\\}\\)\u4f7f\u5f97\uff1a<\/p>\n\n\n\n

    $$
    s=\\sum_{i=1}^{n}e_ia_i
    $$<\/p>\n\n\n\n

    \u4f4e\u5bc6\u5ea6\u5b50\u96c6\u548c\u95ee\u9898<\/h4>\n\n\n\n

    \u96c6\u5408\\(\\{a_1,a_2,\\cdots,a_n\\}\\)\u7684\u5bc6\u5ea6\\(d\\)\u53ef\u4ee5\u901a\u8fc7\u4e0b\u5f0f\u8ba1\u7b97\uff1a<\/p>\n\n\n\n

    $$
    d=\\frac{n}{\\log_2{\\max_{i\\in\\{1,2,\\cdots,n\\}}(a_i)}}
    $$<\/p>\n\n\n\n

    \u7814\u7a76\u8868\u660e\uff0c\u5f53\\(d<0.9408\\)\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u5b50\u96c6\u548c\u95ee\u9898\u8f6c\u6362\u4e3a\u6c42\u89e3SVP. \u4e00\u822c\u7b56\u7565\u4e3a\u6784\u9020\u4e00\u4e2a\u683c\uff0c\u5176\u4e2d\u6709\u4e00\u4e2a\u77ed\u5411\u91cf\u5305\u542b\\(\\{e_1,e_2,\\cdots,e_n\\}\\)\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u53ef\u4ee5\u6784\u9020\u51fa\u4e0b\u9762\u7684\u683c\u57fa\u77e9\u9635\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{B}=\\left(\\begin{matrix} 1&&&&a_1\\\\ &1&&&a_2\\\\ &&\\ddots&&\\vdots\\\\ &&&1&a_n\\\\ &&&&s \\end{matrix}\\right)
    $$<\/p>\n\n\n\n

    \u663e\u7136\u7ebf\u6027\u7ec4\u5408\\((e_1,e_2,\\cdots,e_n,-1)\\)\u4f1a\u751f\u6210\u4e00\u4e2a\u77ed\u5411\u91cf\\((e_1,e_2,\\cdots,e_n,-1)\\pmb{B}=(e_1,e_2,\\cdots,e_n,0)\\)\uff0c\u6240\u4ee5\u6211\u4eec\u7684\u9884\u671f\u662f\u901a\u8fc7LLL\u7b97\u6cd5\u5bf9\u4e0a\u8ff0\u683c\u8fdb\u884c\u89c4\u7ea6\u5f97\u5230\u8fd9\u4e2a\u77ed\u5411\u91cf\uff0c\u4f46\u662f\u8fd9\u4e2a\u65b9\u6cd5\u5728\u5bc6\u5ea6\u6bd4\u8f83\u9ad8\u7684\u65f6\u5019\u4f1a\u5931\u6548\uff0c\u6240\u4ee5Coster\u7b49\u4eba\u63d0\u51fa\u4e86CJLOSS\u7b97\u6cd5\uff0c\u4f7f\u5f97\u6211\u4eec\u53ef\u4ee5\u5728\\(d<0.9408\\)\u7684\u65f6\u5019\u901a\u8fc7\u5c06\u5b50\u96c6\u548c\u95ee\u9898\u8f6c\u6362\u4e3aSVP\u4ece\u800c\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u6c42\u89e3\u8fd9\u4e2a\u95ee\u9898\uff0cCJLOSS\u7b97\u6cd5\u4e2d\u6784\u9020\u7684\u683c\u4e3a\uff1a<\/p>\n\n\n\n

    $$
    \\pmb{B}’=\\left(\\begin{matrix} 1&&&&Na_1\\\\ &1&&&Na_2\\\\ &&\\ddots&&\\vdots\\\\ &&&1&Na_n\\\\ \\frac{1}{2}&\\frac{1}{2}&\\cdots&\\frac{1}{2}&Ns \\end{matrix}\\right)
    $$<\/p>\n\n\n\n

    \u5176\u4e2d\u6574\u6570\\(N>\\sqrt{n}\\)\uff0c\u5728\u8fd9\u4e2a\u683c\u5185\uff0c\u7ebf\u6027\u7ec4\u5408\\((e_1,e_2,\\cdots,e_n,-1)\\)\u4f1a\u751f\u6210\u53e6\u5916\u4e00\u4e2a\u77ed\u5411\u91cf\uff1a<\/p>\n\n\n\n

    $$
    (e_1,e_2,\\cdots,e_n,-1)\\pmb{B}’=(e_1-\\frac{1}{2},e_2-\\frac{1}{2},\\cdots,e_n-\\frac{1}{2},0)
    $$<\/p>\n\n\n\n

    \u663e\u7136\u8fd9\u6761\u77ed\u5411\u91cf\u7684\u6a21\u4e3a\\(\\frac{\\sqrt{n}}{2}\\)\uff0c\u6211\u4eec\u5f88\u5bb9\u6613\u53ef\u4ee5\u901a\u8fc7LLL\u7b97\u6cd5\u6c42\u89e3\u51fa\u8fd9\u6761\u77ed\u5411\u91cf\uff08\u8fd9\u4e2a\u77ed\u5411\u91cf\u4e00\u822c\u662f\u89c4\u7ea6\u540e\u7684\u683c\u7684\u7b2c\u4e00\u4e2a\u5411\u91cf\uff0c\u4e14\u524d\\(n\\)\u4e2a\u5143\u7d20\u5f80\u5f80\u4e3a\\(\\frac{1}{2}-e_i\\)\uff09\u3002 \u4f7f\u7528sage\u901a\u8fc7CJLOSS\u7b97\u6cd5\u6c42\u89e3\u4f4e\u5bc6\u5ea6\u5b50\u96c6\u548c\u7684\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n

    <\/circle><\/circle><\/circle><\/g><\/svg><\/span>