{"id":132,"date":"2025-04-09T22:49:00","date_gmt":"2025-04-09T14:49:00","guid":{"rendered":"http:\/\/www.triode.cc\/?p=132"},"modified":"2025-10-22T09:05:49","modified_gmt":"2025-10-22T01:05:49","slug":"ntru","status":"publish","type":"post","link":"https:\/\/www.triode.cc\/index.php\/2025\/04\/09\/ntru\/","title":{"rendered":"NTRU"},"content":{"rendered":"\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>\u53c2\u8003\u8d44\u6599\uff1a<a href=\"https:\/\/link.springer.com\/book\/10.1007\/978-1-4939-1711-2\">An Introduction to Mathematical Cryptography | SpringerLink<\/a><\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">\u524d\u7f6e\u77e5\u8bc6<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u683c<\/h3>\n\n\n\n<p>\u4e0e\u683c\u76f8\u5173\u7684\u524d\u7f6e\u77e5\u8bc6\u5728<a href=\"http:\/\/www.triode.cc\/index.php\/2025\/03\/31\/lattice-based-cryptography\/\">\u8fd9\u7bc7\u535a\u5ba2<\/a>\u91cc\u9762\u90fd\u6709\u63d0\u53ca<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u5377\u79ef\u591a\u9879\u5f0f\u73af<\/h3>\n\n\n\n<p>\u5bf9\u4e8e\u4e00\u4e2a\u6574\u6570\\(N\\)\uff0c\u79e9\u4e3a\\(N\\)\u7684\u5377\u79ef\u591a\u9879\u5f0f\u73af\u5373\u4e3a\u5982\u4e0b\u5546\u73af\uff1a<\/p>\n\n\n\n<p>$$<br>R=\\frac{\\mathbb{Z}[x]}{(x^{N}-1)}<br>$$<\/p>\n\n\n\n<p>\u7c7b\u4f3c\u7684\u6211\u4eec\u4e5f\u53ef\u4ee5\u5b9a\u4e49\u51fa\u6a21\\(q\\)\u7684\u5377\u79ef\u591a\u9879\u5f0f\u73af\u4e3a\u5982\u4e0b\u5546\u73af\uff1a<\/p>\n\n\n\n<p>$$<br>R_q=\\frac{(\\mathbb{Z}\/q\\mathbb{Z})[x]}{(x^{N}-1)}<br>$$<\/p>\n\n\n\n<p>\u53ef\u4ee5\u77e5\u9053\u5377\u79ef\u591a\u9879\u5f0f\u73af\u4e2d\u6bcf\u4e00\u4e2a\u591a\u9879\u5f0f\\(a(x)\\)\u90fd\u6709\u552f\u4e00\u7684\u8868\u793a\uff08\u5728\u8fd9\u4e4b\u540e\uff0c\u6211\u4eec\u9ed8\u8ba4\u5377\u79ef\u591a\u9879\u5f0f\u73af\u5185\u7684\u591a\u9879\u5f0f\u90fd\u662f\u5982\u4e0b\u8868\u793a\uff09\uff1a<\/p>\n\n\n\n<p>$$<br>a(x)=a_0+a_1x+a_2x^2+\\cdots+a_{N-1}x^{N-1}<br>$$<\/p>\n\n\n\n<p>\u5176\u4e2d\\(a_0,a_1,\\cdots,a_{N-1}\\in \\mathbb{Z}\\)\uff08\u6216\u8005\\(\\mathbb{Z}\/q\\mathbb{Z}\\)\uff0c\u8fd9\u53d6\u51b3\u4e8e\u8fd9\u4e2a\u5377\u79ef\u591a\u9879\u5f0f\u73af\u662f\u4e00\u822c\u7684\u5377\u79ef\u591a\u9879\u5f0f\u73af\u8fd8\u662f\u6a21\\(q\\)\u7684\u5377\u79ef\u591a\u9879\u5f0f\u73af\uff09 \u5377\u79ef\u591a\u9879\u5f0f\u73af\u662fNTRU\u5bc6\u7801\u4f53\u7cfb\u7684\u57fa\u7840\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">center-lift<\/h3>\n\n\n\n<p>\u5bf9\u4e8e\\(R_q\\)\u4e0a\u4e00\u4e2a\u591a\u9879\u5f0f\\(a(x)\\)\uff0c\\(a(x)\\)\u5230\\(R\\)\u4e0a\u7684center-lift\u5373\u4e3a\u4e00\u4e2a\u591a\u9879\u5f0f\\(a'(x)\\)\u6ee1\u8db3\uff1a<\/p>\n\n\n\n<p>$$<br>a'(x)\\equiv a(x)\\pmod{q}<br>$$<\/p>\n\n\n\n<p>\u5176\u4e2d\\(a'(x)\\)\u7684\u7cfb\u6570\\(a_i&#8217;\\in(-\\frac{q}{2},\\frac{q}{2}]\\). \u5bf9\u4e8e\u4e00\u4e2a\u591a\u9879\u5f0f\uff0c\u8981\u83b7\u5f97\u5176center-lift\u6709\u5982\u4e0b\u7b97\u6cd5\uff1a<\/p>\n\n\n\n<p>$$<br>a_i&#8217;= \\begin{cases} a_i&amp;,0\\le a_i\\le\\frac{q}{2}\\\\ a_i-q&amp;,\\frac{q}{2}&lt; a_i&lt; q \\end{cases}<br>$$<\/p>\n\n\n\n<p>center-lift\u53ef\u4ee5\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u5b9e\u73b0\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>def center_lift(Rm, R, f):\n    modulo = ZZ(Rm(list(f)).base_ring()(-1)) + 1\n    l = &#91;ZZ(x) if x &lt;= modulo \/\/ 2 else ZZ(x) - modulo for x in list(f)&#93;\n    return R(l)<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    modulo <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">base_ring<\/span><span style=\"color: #ECEFF4\">()(<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    l <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">&lt;=<\/span><span style=\"color: #D8DEE9FF\"> modulo <\/span><span style=\"color: #81A1C1\">\/\/<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">else<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> modulo <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)&#93;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">l<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e09\u5143\u591a\u9879\u5f0f\uff08ternary polynomial\uff09<\/h3>\n\n\n\n<p>\u5bf9\u4e8e\u5377\u79ef\u591a\u9879\u5f0f\u73af\\(R=\\frac{\\mathbb{Z}[x]}{(x^{N}-1)}\\)\uff0c\u5bf9\u4e8e\u4efb\u610f\u6b63\u6570\\(d_1,d_2\\)\uff0c\u82e5\u591a\u9879\u5f0f\\(a(x)\\in R\\)\u6ee1\u8db3\u4ee5\u4e0b\u6761\u4ef6\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\\(a(x)\\)\u4e2d\u6709\\(d_1\\)\u4e2a\u7cfb\u6570\u4e3a\\(1\\)\uff1b<\/li>\n\n\n\n<li>\\(a(x)\\)\u4e2d\u6709\\(d_2\\)\u4e2a\u7cfb\u6570\u4e3a\\(-1\\)\uff1b<\/li>\n\n\n\n<li>\\(a(x)\\)\u4e2d\u5176\u4f59\u7cfb\u6570\u5747\u4e3a\\(0\\).<\/li>\n<\/ol>\n\n\n\n<p>\u5219\u79f0\u8fd9\u4e2a\u591a\u9879\u5f0f\u4e3a\u4e00\u4e2a\u4e09\u5143\u591a\u9879\u5f0f\uff08ternary polynomial\uff0c\u6216\u79f0trinary polynomial\uff09\uff0c\u5bf9\u4e8e\u4e00\u4e2a\u5377\u79ef\u591a\u9879\u5f0f\u73afR\uff0c\u5176\u4e0a\u7684\u6240\u6709\u4e09\u5143\u591a\u9879\u5f0f\u7684\u96c6\u5408\u8bb0\u4e3a\uff1a<\/p>\n\n\n\n<p>$$<br>\\mathcal{T}(d_1,d_2)=\\left\\{a(x)\\in R| a(x)\\text{ is a ternary polynomial}\\right\\}<br>$$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">NTRU\u7b97\u6cd5\u7ec6\u8282<\/h2>\n\n\n\n<p>\u53d6\u6574\u6570\\(N\\ge1\\)\u4ee5\u53ca\u4e24\u4e2a\u6a21\u6570\\(p,q\\)\uff08\u5176\u4e2d\\(N\\)\u4e3a\u8d28\u6570\uff0c\u4e14\\(N\\)\u4e0e\\(q\\)\u4e92\u8d28\uff0c\\(p\\)\u4e0e\\(q\\)\u4e92\u8d28\uff09\uff0c\u5f97\u5230\u5982\u4e0b\u4e09\u4e2a\u5377\u79ef\u591a\u9879\u5f0f\u73af\uff1a<\/p>\n\n\n\n<p>$$<br>R=\\frac{\\mathbb{Z}[x]}{(x^{N}-1)},\\quad R_p=\\frac{(\\mathbb{Z}\/p\\mathbb{Z})[x]}{(x^{N}-1)},\\quad R_q=\\frac{(\\mathbb{Z}\/q\\mathbb{Z})[x]}{(x^{N}-1)}<br>$$<\/p>\n\n\n\n<p>\u5728\u6b64\u6211\u4eec\u5c06\u6d88\u606f\u4f20\u9012\u7684\u53cc\u65b9\u5206\u522b\u79f0\u4e3aAlice\u548cBob\uff0cAlice\u9009\u53d6\u516c\u5171\u53c2\u6570\\((N,p,q,d)\\)\uff08\\(d\\)\u4e5f\u662f\u4e2a\u6574\u6570\uff0c\u516c\u5171\u53c2\u6570\u7684\u9009\u62e9\u5e94\u6ee1\u8db3\\(q&gt;(6d+1)p\\)\uff09\uff0c\u5e76\u5728\\(R\\)\u4e0a\u968f\u673a\u9009\u53d6\u4e09\u5143\u591a\u9879\u5f0f\\(f(x)\\in\\mathcal{T}(d+1,d)\\)\u4ee5\u53ca\\(g(x)\\in\\mathcal{T}(d,d)\\)\uff0c\u8ba1\u7b97\uff1a<\/p>\n\n\n\n<p>$$<br>\\begin{aligned} F_p\\equiv f^{-1}\\pmod{p}\\\\ F_q\\equiv f^{-1}\\pmod{q} \\end{aligned}<br>$$<\/p>\n\n\n\n<p>\u8fd9\u6837\u5c31\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\\(R_p\\)\u4e0a\u7684\u591a\u9879\u5f0f\\(F_p\\)\u4ee5\u53ca\u4e00\u4e2a\\(R_q\\)\u4e0a\u7684\u591a\u9879\u5f0f\\(F_q\\)\uff0c\u5728\u6b64\u4e4b\u540eAlice\u5728\\(R_q\\)\u4e0a\u8ba1\u7b97\uff1a<\/p>\n\n\n\n<p>$$<br>h(x)=F_q(x)\\star g(x)<br>$$<\/p>\n\n\n\n<p>\u5728\u8fd9\u91cc\u201c\\(\\star\\)\u201d\u8868\u793a\u5377\u79ef\u591a\u9879\u5f0f\u73af\u4e0a\u591a\u9879\u5f0f\u7684\u4e58\u6cd5\uff0c\u5bf9\u4e8e\u4e24\u4e2a\u5377\u79ef\u591a\u9879\u5f0f\u73af\\(R\\)\u4e0a\u7684\u591a\u9879\u5f0f\\(a(x),b(x)\\)\uff0c\u5176\u4e58\u79ef\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n\n\n\n<p>$$<br>a(x)\\star b(x)=c(x),\\quad c_k=\\sum_{i+j\\equiv k\\pmod{N}}{a_{i}b_{j}}<br>$$<\/p>\n\n\n\n<p>\u7531\u6b64\u8ba1\u7b97\u51fa\u7684\u591a\u9879\u5f0f\\(h(x)\\)\u5373\u4e3a<strong>\u516c\u94a5<\/strong>\uff0c\u524d\u9762\u751f\u6210\u7684\\((f,F_p)\\)\u5c31\u662f<strong>\u79c1\u94a5<\/strong>\uff08\u5b9e\u9645\u4e0a\u79c1\u94a5\u53ea\u9700\u8981\\(f\\)\uff0cAlice\u53ef\u4ee5\u901a\u8fc7\\(f\\)\u6765\u8ba1\u7b97\u51fa\\(F_p\\)\uff09\u3002 \u5728\u6b64\u4e4b\u540eBob\u9700\u8981\u901a\u8fc7\u516c\u94a5\\(h(x)\\)\u6765\u52a0\u5bc6\u660e\u6587\\(m(x)\\)\uff08\u5176\u4e2d\u660e\u6587\\(m(x)\\in R\\)\uff0c\u800c\u4e14\u5176\u4e2d\u7cfb\u6570\\(m_i\\)\u6ee1\u8db3\\(-\\frac{p}{2}&lt;m_i\\le \\frac{p}{2}\\)\uff0c\u5b9e\u9645\u4e0a\\(m(x)\\)\u5c31\u662f\\(R_p\\)\u4e0a\u67d0\u4e2a\u591a\u9879\u5f0f\u7684center-lift\uff09\uff0cBob\u5148\u9009\u53d6\u4e00\u4e2a\u968f\u673a\u4e09\u5143\u591a\u9879\u5f0f\\(r(x)\\in\\mathcal{T}(d,d)\\)\uff0c\u8ba1\u7b97\uff1a<\/p>\n\n\n\n<p>$$<br>e(x)\\equiv ph(x)\\star r(x)+m(x)\\pmod{q}<br>$$<\/p>\n\n\n\n<p>\u5f97\u5230\u7684\u591a\u9879\u5f0f\\(e(x)\\)\u5c31\u662fBob\u7684\u5bc6\u6587\uff0cAlice\u5f97\u5230Bob\u53d1\u9001\u7684\u5bc6\u6587\u4e4b\u540e\u8981\u8fdb\u884c\u89e3\u5bc6\uff0c\u5219\u9700\u5148\u5728\\(R_q\\)\u4e0a\u8ba1\u7b97\uff1a<\/p>\n\n\n\n<p>$$<br>a(x)\\equiv f(x)\\star e(x)\\pmod{q}<br>$$<\/p>\n\n\n\n<p>\u7136\u540e\u5f97\u5230\\(a(x)\\)\u7684center-lift\uff0c\u7136\u540e\u518d\u5728\\(R_p\\)\u4e2d\u8ba1\u7b97\uff1a<\/p>\n\n\n\n<p>$$<br>b(x)\\equiv F_p(x)\\star a(x)\\pmod{p}<br>$$<\/p>\n\n\n\n<p>\u8fd9\u6837\u5f97\u5230\u7684\\(R_p\\)\u4e0a\u7684\u591a\u9879\u5f0f\\(b(x)\\)\u5c31\u662f\u660e\u6587\\(m(x)\\). NTRU\u5927\u81f4\u6d41\u7a0b\u5982\u4e0b\u56fe\u6240\u793a\uff08\u5728\u53c2\u8003\u8d44\u6599\u91cc\u622a\u7684\uff09\uff1a <\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full is-resized\"><a href=\"http:\/\/www.triode.cc\/wp-content\/uploads\/2025\/04\/image.png\"><div class='fancybox-wrapper lazyload-container-unload' data-fancybox='post-images' href='http:\/\/www.triode.cc\/wp-content\/uploads\/2025\/04\/image.png'><img class=\"lazyload lazyload-style-1\" src=\"data:image\/svg+xml;base64,PCEtLUFyZ29uTG9hZGluZy0tPgo8c3ZnIHdpZHRoPSIxIiBoZWlnaHQ9IjEiIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgc3Ryb2tlPSIjZmZmZmZmMDAiPjxnPjwvZz4KPC9zdmc+\"  loading=\"lazy\" decoding=\"async\" width=\"642\" height=\"590\" data-original=\"http:\/\/www.triode.cc\/wp-content\/uploads\/2025\/04\/image.png\" src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsQAAA7EAZUrDhsAAAANSURBVBhXYzh8+PB\/AAffA0nNPuCLAAAAAElFTkSuQmCC\" alt=\"\" class=\"wp-image-135\" style=\"aspect-ratio:1;width:840px;height:auto\"  sizes=\"auto, (max-width: 642px) 100vw, 642px\" \/><\/div><\/a><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\">NTRU\u7684\u5b9e\u73b0<\/h3>\n\n\n\n<p>\u5728\u8fd9\u91cc\u901a\u8fc7sage\u5b9e\u73b0\u53c2\u8003\u8d44\u6599\u4e2d\u7684\u4e00\u4e2a\u4f8b\u5b50\uff08Example 7.53\uff09\uff1a \u53d6\\((N, p, q, d) = (7, 3, 41, 2)\\)\uff0c\u663e\u7136\u6709\\((6d+1)p=39&lt;q\\)\uff0c\u800c\u4e14\\((p,q)=1,(N,q)=1\\)\uff0c\u7b26\u5408\u53c2\u6570\u9009\u62e9\u7684\u6761\u4ef6\uff0c\u90a3\u4e48\u53ef\u4ee5\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u6784\u9020\u51fa\u4e09\u4e2a\u5377\u79ef\u591a\u9879\u5f0f\u73af\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>_R = PolynomialRing(ZZ, 'x')\nR = _R.quotient(x^N - 1, 'x')\n\n_Rp = PolynomialRing(Zmod(p), 'x')\nRp = _Rp.quotient(x^N - 1, 'x')\n\n_Rq = PolynomialRing(Zmod(q), 'x')\nRq = _Rq.quotient(x^N - 1, 'x')<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">_R <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ZZ<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">R <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _R<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_Rp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">p<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Rp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _Rp<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_Rq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Rq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _Rq<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u5bf9\u56fa\u5b9a\u7684\u5377\u79ef\u591a\u9879\u5f0f\u73af\\(R\\)\uff0c\u53ef\u4ee5\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u6765\u83b7\u5f97\u968f\u673a\u4e09\u5143\u591a\u9879\u5f0f\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>def T(R, N, d1, d2):\n    from random import shuffle\n    coef = &#91;1&#93; * d1 + &#91;-1&#93; * d2 + &#91;0&#93; * (N - d1 - d2)\n    shuffle(coef)\n    return R(coef)<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">T<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">N<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">d1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">d2<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">from<\/span><span style=\"color: #D8DEE9FF\"> random <\/span><span style=\"color: #81A1C1\">import<\/span><span style=\"color: #D8DEE9FF\"> shuffle<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    coef <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> d1 <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> d2 <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #B48EAD\">0<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> d1 <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> d2<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">shuffle<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">coef<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">coef<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u968f\u673a\u9009\u53d6\u4e24\u4e2a\\(R\\)\u4e0a\u7684\u4e09\u5143\u591a\u9879\u5f0f\\(f(x)\\in\\mathcal{T}(3,2)\\)\u4ee5\u53ca\\(g(x)\\in\\mathcal{T}(2,2)\\)\uff08\u5e76\u4fdd\u8bc1\\(f(x)\\)\u5728\\(R_p\\)\u4ee5\u53ca\\(R_q\\)\u4e0a\u5747\u53ef\u9006\uff09\uff0c\u6839\u636e\u7ed9\u51fa\u7684\u4f8b\u5b50\uff0c\u9009\u53d6\u7684\u4e24\u4e2a\u591a\u9879\u5f0f\u5982\u4e0b\uff1a<\/p>\n\n\n\n<p>$$<br>\\begin{aligned} &amp;f(x)=x^6\u2212x^4+x^3+x^2\u22121\\\\ &amp;g(x)=x^6+x^4\u2212x^2\u2212x \\end{aligned}<br>$$<\/p>\n\n\n\n<p>\u7136\u540e\u5206\u522b\u5728\\(R_p,R_q\\)\u4e0a\u8ba1\u7b97\\(f(x)\\)\u7684\u9006\uff0c\u6309\u9053\u7406\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u6765\u6c42\u591a\u9879\u5f0f\\(f(x)\\)\u5728\u4efb\u610f\u6a21\u5377\u79ef\u591a\u9879\u5f0f\u73af\\(R_m\\)\u7684\u9006\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>def inv(Rm, f):\n    return Rm(list(f)).inverse()<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">inverse<\/span><span style=\"color: #ECEFF4\">()<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u4f46\u662f\u5982\u679c\u73af\\(R_m\\)\u7684\u6a21\u6570\u4e3a\u5408\u6570\u7684\u65f6\u5019\u5c31\u8dd1\u4e0d\u52a8\u4e86\uff0c\u627e\u4e86\u4e00\u5708\u5728<a href=\"https:\/\/latticehacks.cr.yp.to\/ntru.html\">\u8fd9\u91cc<\/a>\u627e\u5230\u4e86\u4e00\u79cd\u540d\u4e3a<code>invertmodpowerof2<\/code>\u7684\u7b97\u6cd5\uff0c\u7ecf\u8fc7\u4fee\u6539\u5f97\u5230\u4e86\u4e0b\u9762\u7684\u7248\u672c\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>def invertmodpowerof2(Rm, R, f):\n    modulo = ZZ(Rm(list(f)).base_ring()(-1)) + 1\n    assert modulo.is_power_of(2)\n    _R2 = PolynomialRing(Zmod(2), 'x')\n    R2 = _R2.quotient(x^N - 1, 'x')\n\n    g = R2(list(f)).inverse()\n    while True:\n        r = center_lift(Rm, R, Rm(list(f * g)))\n        if r == 1:\n            return g\n        g = center_lift(Rm, R, Rm(list(g * (2 - r))))<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">invertmodpowerof2<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    modulo <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">base_ring<\/span><span style=\"color: #ECEFF4\">()(<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">assert<\/span><span style=\"color: #D8DEE9FF\"> modulo<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">is_power_of<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    _R2 <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    R2 <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _R2<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R2<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">inverse<\/span><span style=\"color: #ECEFF4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">while<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">True<\/span><span style=\"color: #ECEFF4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        r <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> g<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> r <\/span><span style=\"color: #81A1C1\">==<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> g<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> r<\/span><span style=\"color: #ECEFF4\">))))<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u4e0d\u8fc7\u8fd9\u4e2a\u7b97\u6cd5\u53ea\u80fd\u7528\u4e8e\u6a21\u6570\u4e3a\\(2^k\\)\u7684\u60c5\u51b5\uff0c\u5bf9\u4e00\u822c\u5408\u6570\u6682\u65f6\u8fd8\u6ca1\u627e\u5230\u5408\u9002\u7684\u65b9\u6848. \u56de\u5230\u4f8b\u5b50\uff0c\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u53ef\u4ee5\u8ba1\u7b97\u51fa\\(F_p\\)\u4ee5\u53ca\\(F_q\\)\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>Fp = inv(Rp, f)\nFq = inv(Rq, f)<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">Fp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> f<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Fq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> f<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n\n\n\n<p>$$<br>\\begin{aligned} &amp;F_p=x^{6} + 2 x^{5} + x^{3} + x^{2} + x + 1\\in R_p\\\\ &amp;F_q=8 x^{6} + 26 x^{5} + 31 x^{4} + 21 x^{3} + 40 x^{2} + 2 x + 37\\in R_q \\end{aligned}<br>$$<\/p>\n\n\n\n<p>\u53ef\u4ee5\u5f97\u5230\\((f,F_p)\\)\u4f5c\u4e3a\u79c1\u94a5\uff0c\u5e76\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u8ba1\u7b97\u516c\u94a5\\(h(x)=F_q(x)\\star g(x)\\)\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>h = Fq * Rq(list(g))<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">h <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> Fq <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g<\/span><span style=\"color: #ECEFF4\">))<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u5f97\u5230\uff1a<\/p>\n\n\n\n<p>$$<br>h(x)=F_q(x)\\star g(x)=20 x^{6} + 40 x^{5} + 2 x^{4} + 38 x^{3} + 8 x^{2} + 26 x + 30\\in R_q<br>$$<\/p>\n\n\n\n<p>\u6b32\u52a0\u5bc6\u6d88\u606f\\(m(x)=\u2212x^5+x^3+x^2\u2212x+1\\)\uff0c\u53d6\\(R\\)\u4e0a\u968f\u673a\u4e09\u5143\u591a\u9879\u5f0f\\(r(x)=x^6 \u2212x^5 +x\u22121\\in\\mathcal{T}(2,2)\\)\uff0c\u901a\u8fc7<code>e = Rq(list(p*r*h + m))<\/code>\u5728\\(R_q\\)\u4e0a\u8ba1\u7b97\\(e(x)\\equiv pr(x)\\star h(x)+m(x)\\pmod{q}\\)\uff0c\u5f97\u5230\u5bc6\u6587\uff1a<\/p>\n\n\n\n<p>$$<br>e(x)=31 x^{6} + 19 x^{5} + 4 x^{4} + 2 x^{3} + 40 x^{2} + 3 x + 25<br>$$<\/p>\n\n\n\n<p>\u53c2\u6570\u9009\u53d6\u4ee5\u53ca\u52a0\u5bc6\u5168\u6d41\u7a0b\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>(N, p, q, d) = (7, 3, 41, 2)\n\n_R = PolynomialRing(ZZ, 'x')\nR = _R.quotient(x^N - 1, 'x')\n\n_Rp = PolynomialRing(Zmod(p), 'x')\nRp = _Rp.quotient(x^N - 1, 'x')\n\n_Rq = PolynomialRing(Zmod(q), 'x')\nRq = _Rq.quotient(x^N - 1, 'x')\n\ndef T(R, N, d1, d2):\n    from random import shuffle\n    coef = &#91;1&#93; * d1 + &#91;-1&#93; * d2 + &#91;0&#93; * (N - d1 - d2)\n    shuffle(coef)\n    return R(coef)\n\ndef center_lift(Rm, R, f):\n    modulo = ZZ(Rm(list(f)).base_ring()(-1)) + 1\n    l = &#91;ZZ(x) if x &lt;= modulo \/\/ 2 else ZZ(x) - modulo for x in list(f)&#93;\n    return R(l)\n\ndef inv(Rm, f):\n    return Rm(f).inverse()\n\ndef invertmodpowerof2(Rm, R, f):\n    modulo = ZZ(Rm(list(f)).base_ring()(-1)) + 1\n    assert modulo.is_power_of(2)\n    _R2 = PolynomialRing(Zmod(2), 'x')\n    R2 = _R2.quotient(x^N - 1, 'x')\n\n    g = R2(list(f)).inverse()\n    while True:\n        r = center_lift(Rm, R, Rm(list(f * g)))\n        if r == 1:\n            return g\n        g = center_lift(Rm, R, Rm(list(g * (2 - r))))\n\n# f = T(R, N, d + 1, d)\nf = R(\"x^6 - x^4 + x^3 + x^2 - 1\") # private key\n# g = T(R, N, d, d)\ng = R(\"x^6 + x^4 - x^2 - x\")\n\nFp = inv(Rp, f)\nFq = inv(Rq, f)\n\nh = Fq * Rq(list(g)) # public key\n\nm = R(\"-x^5+x^3+x^2-x+1\")\n# r = T(R, N, d, d)\nr = R(\"x^6-x^5+x-1\")\n\ne = Rq(list(p*r*h + m))<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> p<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> d<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">7<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">3<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">41<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_R <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ZZ<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">R <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _R<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_Rp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">p<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Rp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _Rp<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_Rq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Rq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _Rq<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">T<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">N<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">d1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">d2<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">from<\/span><span style=\"color: #D8DEE9FF\"> random <\/span><span style=\"color: #81A1C1\">import<\/span><span style=\"color: #D8DEE9FF\"> shuffle<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    coef <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> d1 <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> d2 <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #B48EAD\">0<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> d1 <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> d2<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">shuffle<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">coef<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">coef<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    modulo <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">base_ring<\/span><span style=\"color: #ECEFF4\">()(<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    l <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">&lt;=<\/span><span style=\"color: #D8DEE9FF\"> modulo <\/span><span style=\"color: #81A1C1\">\/\/<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">else<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> modulo <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)&#93;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">l<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">).<\/span><span style=\"color: #88C0D0\">inverse<\/span><span style=\"color: #ECEFF4\">()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">invertmodpowerof2<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    modulo <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">base_ring<\/span><span style=\"color: #ECEFF4\">()(<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">assert<\/span><span style=\"color: #D8DEE9FF\"> modulo<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">is_power_of<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    _R2 <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    R2 <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _R2<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R2<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">inverse<\/span><span style=\"color: #ECEFF4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">while<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">True<\/span><span style=\"color: #ECEFF4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        r <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> g<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> r <\/span><span style=\"color: #81A1C1\">==<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> g<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> r<\/span><span style=\"color: #ECEFF4\">))))<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #616E88\"># f = T(R, N, d + 1, d)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #A3BE8C\">x^6 - x^4 + x^3 + x^2 - 1<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #616E88\"># private key<\/span><\/span>\n<span class=\"line\"><span style=\"color: #616E88\"># g = T(R, N, d, d)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #A3BE8C\">x^6 + x^4 - x^2 - x<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Fp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> f<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Fq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> f<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">h <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> Fq <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #616E88\"># public key<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">m <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #A3BE8C\">-x^5+x^3+x^2-x+1<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #616E88\"># r = T(R, N, d, d)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">r <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #A3BE8C\">x^6-x^5+x-1<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">e <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">p<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">r<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">h <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> m<\/span><span style=\"color: #ECEFF4\">))<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u5728\u83b7\u53d6\u5bc6\u6587\u4e4b\u540e\uff0c\u9700\u8981\u9996\u5148\u5728\\(R_q\\)\u4e0a\u8ba1\u7b97\\(f(x)\\star e(x)\\)\u5e76\u83b7\u53d6\u5176center-lift\u5f97\u5230\\(a(x)\\)\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>a = center_lift(Rq, R, Rq(list(f * e)))<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">a <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> e<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u5f97\u5230\uff1a<\/p>\n\n\n\n<p>$$<br>a(x)=x^{6} + 10x^{5} &#8211; 8x^{4} &#8211; x^{3} &#8211; x^{2} + x &#8211; 1<br>$$<\/p>\n\n\n\n<p>\u7136\u540e\u5728\\(R_p\\)\u4e0a\u8ba1\u7b97\\(F_p\\star a(x)\\)\u5e76\u83b7\u53d6\u5176center-lift\u5f97\u5230\\(b(x)\\)\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>b = center_lift(Rp, R, Rp(list(Fp * a)))<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">b <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rp<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Fp <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> a<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u6b64\u65f6\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n\n\n\n<p>$$<br>b(x)=-x^{5} + x^{3} + x^{2} &#8211; x + 1<br>$$<\/p>\n\n\n\n<p>\u53ef\u4ee5\u770b\u5230\\(b(x)=m(x)\\)\uff0c\u8bf4\u660e\u6b64\u65f6\u8ba1\u7b97\u51fa\u6765\u7684\u5c31\u662f\u660e\u6587\uff0c\u5982\u6b64\u53ef\u4ee5\u5f97\u5230\u89e3\u5bc6\u6d41\u7a0b\u5982\u4e0b\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>a = center_lift(Rq, R, Rq(list(f * e)))\nb = center_lift(Rp, R, Rp(list(Fp * a)))<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">a <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> e<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">b <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rp<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Fp <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> a<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">NTRU\u7684\u683c\u653b\u51fb<\/h2>\n\n\n\n<p>\u56de\u5230\u516c\u94a5\u8ba1\u7b97\u8fd9\u4e00\u6b65\uff0c\u6211\u4eec\u9700\u8981\u5728\\(R_q\\)\u4e0a\u8ba1\u7b97\\(h(x)=F_q(x)\\star g(x)\\)\uff0c\u4e24\u8fb9\u4e58\u4e0a\\(f(x)\\)\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n\n\n\n<p>$$<br>f(x)\\star h(x)\\equiv g(x)\\pmod{q}<br>$$<\/p>\n\n\n\n<p>\u4e0e\u5bf9\u6570\u7684\u5904\u7406\u65b9\u6cd5\u7c7b\u4f3c\u7684\uff0c\u53ef\u4ee5\u5c06\u4e0a\u5f0f\u53d8\u4e3a\uff1a<\/p>\n\n\n\n<p>$$<br>f(x)\\star h(x)=g(x)+q\\cdot u(x)<br>$$<\/p>\n\n\n\n<p>\u5176\u4e2d\\(u(x)\\in R\\)\uff0c\u6211\u4eec\u60f3\u8981\u7684\u662f\u79c1\u94a5\\(f(x)\\)\uff0c\u90a3\u4e48\u53ef\u4ee5\u6784\u9020\u51fa\u5982\u4e0b\u65b9\u7a0b\uff1a<\/p>\n\n\n\n<p>$$<br>(f(x),-u(x)) \\left(\\begin{matrix} 1&amp;h(x)\\\\ 0&amp;q \\end{matrix}\\right)= (f(x),g(x))\\tag{1}<br>$$<\/p>\n\n\n\n<p>\u4f46\u662f\u76f4\u63a5\u5bf9\u591a\u9879\u5f0f\u77e9\u9635\u8fdb\u884c\u89c4\u7ea6\u5e94\u8be5\u662f\u4e0d\u592a\u53ef\u80fd\u7684\uff0c\u90a3\u4e48\u9700\u8981\u627e\u5230\u4e00\u79cd\u65b9\u6cd5\u6765\u5c06\u591a\u9879\u5f0f\u77e9\u9635\u8f6c\u6362\u4e3a\u4e00\u822c\u7684\u77e9\u9635\uff0c\u5148\u524d\u63d0\u5230\u5bf9\u4e8e\u4e24\u4e2a\u5377\u79ef\u591a\u9879\u5f0f\u73afR\u4e0a\u7684\u591a\u9879\u5f0f\\(a(x),b(x)\\)\uff0c\u5176\u4e58\u79ef\u5b9a\u4e49\u4e3a\uff1a<\/p>\n\n\n\n<p>$$<br>a(x)\\star b(x)=c(x),\\quad c_k=\\sum_{i+j\\equiv k\\pmod{N}}{a_{i}b_{j}}<br>$$<\/p>\n\n\n\n<p>\u663e\u7136\u6709\uff1a<\/p>\n\n\n\n<p>$$<br>c_k=(a_0,a_1,\\cdots,a_{N-1})\\cdot(b_{k\\mod{N}},b_{k-1\\mod{N}},\\cdots,b_{k-N+1\\mod{N}})^T<br>$$<\/p>\n\n\n\n<p>\u90a3\u4e48\u53ef\u4ee5\u5f97\u5230\uff1a<\/p>\n\n\n\n<p>$$<br>(c_0,c_1,\\cdots, c_{N-1})=(a_0,a_1,\\cdots,a_{N-1}) \\left(\\begin{matrix} b_0&amp;b_1&amp;\\cdots&amp;b_{N-1}\\\\ b_{N-1}&amp;b_0&amp;\\cdots&amp;b_{N-2}\\\\ \\vdots&amp;\\vdots&amp;&amp;\\vdots\\\\ b_{1}&amp;b_{2}&amp;\\cdots&amp;b_{0} \\end{matrix}\\right)<br>$$<\/p>\n\n\n\n<p>\u5b9e\u9645\u4e0a\u7b49\u5f0f\u53f3\u8fb9\u7684\u77e9\u9635\u662f\\(b(x)\\)\u7684\u7cfb\u6570\u7684\u5faa\u73af\u6392\u5217\uff0c\u8fd9\u6837\u6211\u4eec\u5c31\u53ef\u4ee5\u5c06\u77e9\u9635\u5185\u7684\\(h(x)\\)\u8f6c\u6362\u4e3a\u4e00\u4e2a\\(n\\times n\\)\u7684\u77e9\u9635\uff1a<\/p>\n\n\n\n<p>$$<br>H=\\left(\\begin{matrix} h_0&amp;h_1&amp;\\cdots&amp;h_{N-1}\\\\ h_{N-1}&amp;h_0&amp;\\cdots&amp;h_{N-2}\\\\ \\vdots&amp;\\vdots&amp;&amp;\\vdots\\\\ h_{1}&amp;h_{2}&amp;\\cdots&amp;h_{0} \\end{matrix}\\right)<br>$$<\/p>\n\n\n\n<p>\u540c\u7406\uff0c\u7531\u4e8e\\(1\\)\u4ee5\u53ca\\(q\\)\u4e5f\u53ef\u4ee5\u770b\u4f5c\u662f\u4ec5\u6709\u5e38\u6570\u9879\u4e0d\u4e3a\\(0\\)\u7684\u591a\u9879\u5f0f\uff0c\u6240\u4ee5\u53ef\u4ee5\u5c06\u5b83\u4eec\u5206\u522b\u8f6c\u6362\u4e3a\u5355\u4f4d\u77e9\u9635\\(I\\)\u4ee5\u53ca\\(q\\)\u500d\u7684\u5355\u4f4d\u77e9\u9635\\(qI\\)\uff0c\u800c\u884c\u5411\u91cf\u5185\u7684\u591a\u9879\u5f0f\\(f(x)\\)\u53ef\u4ee5\u8f6c\u6362\u4e3a\u5176\u5bf9\u5e94\u7684\u7cfb\u6570\u5411\u91cf\\(\\pmb{f}=(f_0,f_1,\\cdots,f_{N-1})\\)\uff0c\u540c\u7406\\(u(x),g(x)\\)\u4e5f\u53ef\u4ee5\u8f6c\u6362\u4e3a\u5bf9\u5e94\u7684\u7cfb\u6570\u5411\u91cf\\(\\pmb{u}\\)\u4ee5\u53ca\\(\\pmb{g}\\)\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u53ef\u4ee5\u5f97\u5230\u65b9\u7a0b(1)\u7684\u7b49\u4ef7\u8868\u793a\uff1a<\/p>\n\n\n\n<p>$$<br>(\\pmb{f},-\\pmb{u}) \\left(\\begin{matrix} I&amp;H\\\\ 0&amp;qI \\end{matrix}\\right)=(\\pmb{f},\\pmb{g})<br>$$<\/p>\n\n\n\n<p>\u5176\u4e2d\\(2N\\times2N\\)\u77e9\u9635\\(\\left(\\begin{matrix}I&amp;H\\\\0&amp;qI\\end{matrix}\\right)\\)\u6240\u786e\u5b9a\u7684\u683c\u88ab\u79f0\u4e3aNTRU\u683c\uff08NTRU Lattice\uff09\u4e00\u822c\u8bb0\u4e3a\\(\\mathcal{L}_h^{\\text{NTRU}}\\)\uff0c\u65b9\u4fbf\u8d77\u89c1\uff0c\u540e\u7eed\u5c06\u5176\u8bb0\u4f5c\\(\\mathcal{L}_h\\)\uff0c\u663e\u7136\u5411\u91cf\\((\\pmb{f},\\pmb{g})\\in\\mathcal{L}_h\\)\uff0c\u63a5\u4e0b\u6765\u5206\u6790\u901a\u8fc7\u5bf9\\(\\mathcal{L}_h\\)\u8fdb\u884c\u683c\u57fa\u89c4\u7ea6\u5f97\u5230\u5411\u91cf\\((\\pmb{f},\\pmb{g})\\)\u7684\u53ef\u80fd\u6027\uff1a \u56e0\u4e3a\\(\\det(\\mathcal{L}_h)=q^N\\)\uff0c\u6240\u4ee5\u6709\uff1a<\/p>\n\n\n\n<p>$$<br>\\left(\\frac{2}{\\sqrt{4\\delta-1}}\\right)^{2N-1}\\sqrt{2N}\\cdot|\\det(\\mathcal{L}_h)|^{1\/2N}=\\left(\\frac{2}{\\sqrt{4\\delta-1}}\\right)^{2N-1}\\sqrt{2Nq}<br>$$<\/p>\n\n\n\n<p>\u53d6\\(\\delta=\\frac{3}{4}\\)\uff0c\u6709\uff1a<\/p>\n\n\n\n<p>$$<br>\\left(\\frac{2}{\\sqrt{4\\delta-1}}\\right)^{2N-1}\\sqrt{2Nq}=(\\sqrt{2})^{2N-1}\\cdot\\sqrt{2Nq}=2^N\\sqrt{Nq}<br>$$<\/p>\n\n\n\n<p>\u800c\u56e0\u4e3a\\(f(x),g(x)\\)\u90fd\u662f\u4e09\u5143\u591a\u9879\u5f0f\uff0c\u6240\u4ee5\uff1a<\/p>\n\n\n\n<p>$$<br>||(\\pmb{f},\\pmb{g})||=\\sqrt{4d+1}\\le2^N\\sqrt{Nq}=\\left(\\frac{2}{\\sqrt{4\\delta-1}}\\right)^{2N-1}\\sqrt{2N}\\cdot|\\det(\\mathcal{L}_h)|^{1\/2N}<br>$$<\/p>\n\n\n\n<p>\u5f88\u663e\u7136\uff0c\\((\\pmb{f},\\pmb{g})\\)\u53ef\u4ee5\u901a\u8fc7BKZ\u7b97\u6cd5\u5bf9\u683c\\(\\mathcal{L}_h\\)\u8fdb\u884c\u683c\u57fa\u89c4\u7ea6\u5f97\u5230\uff08LLL\u6709\u65f6\u5019\u4e0d\u884c\uff09\uff0c\u901a\u8fc7\u5982\u4e0b\u4ee3\u7801\u5c31\u53ef\u4ee5\u6784\u9020\u51fa\u683c\u5e76\u8fdb\u884c\u89c4\u7ea6\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>L = matrix(ZZ, 2*N, 2*N)\n\nh_coeff = &#91;ZZ(x) for x in list(h)&#93; # \u6709\u65f6\u5019\u53ef\u80fdh\u8981\u4e58\u4e0a\u4e00\u4e2apow(q, -1, p)\nfor i in range(N):\n    L&#91;i, i&#93; = 1\n    L&#91;N + i, N + i&#93; = q\n    for j in range(N):\n        L&#91;i, N + j&#93; = h_coeff&#91;(j - i) % N&#93;\n\nres = L.BKZ()<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">L <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">matrix<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ZZ<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">h_coeff <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">h<\/span><span style=\"color: #ECEFF4\">)&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #616E88\"># \u6709\u65f6\u5019\u53ef\u80fdh\u8981\u4e58\u4e0a\u4e00\u4e2apow(q, -1, p)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> i <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> j <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> j<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> h_coeff<\/span><span style=\"color: #ECEFF4\">&#91;(<\/span><span style=\"color: #D8DEE9FF\">j <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">%<\/span><span style=\"color: #D8DEE9FF\"> N<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">res <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> L<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">BKZ<\/span><span style=\"color: #ECEFF4\">()<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u4f46\u662f\u76ee\u6807\u5411\u91cf\u5e76\u4e0d\u4e00\u5b9a\u5728\u7b2c\u4e00\u6761\uff0c\u6240\u4ee5\u9700\u8981\u904d\u5386\u6bcf\u4e00\u884c\uff0c\u5224\u65ad\u524d\\(N\\)\u4e2a\u5206\u91cf\u8868\u793a\u7684\u591a\u9879\u5f0f\u662f\u5426\u5c5e\u4e8e\\(\\mathcal{T}(d+1, d)\\)\u518d\u5c1d\u8bd5\u6c42\u89e3\uff0c\u7ecf\u8fc7\u6d4b\u8bd5\u53d1\u73b0\uff0c\u4e00\u4e2a\u516c\u94a5\u53ef\u4ee5\u901a\u8fc7\u683c\u653b\u51fb\u83b7\u53d6\u591a\u4e2a\u79c1\u94a5\uff0c\u5e76\u4e14\u8fd9\u4e9b\u79c1\u94a5\u90fd\u53ef\u4ee5\u6210\u529f\u8fdb\u884c\u89e3\u5bc6\uff0c\u4f8b\u5982\u5bf9\u4e8e\u524d\u9762\u7684\u4f8b\u5b50\uff0c\u5047\u8bbe\u6211\u4eec\u53ea\u77e5\u9053\u516c\u94a5\uff1a<\/p>\n\n\n\n<p>$$<br>h(x)=20 x^{6} + 40 x^{5} + 2 x^{4} + 38 x^{3} + 8 x^{2} + 26 x + 30<br>$$<\/p>\n\n\n\n<p>\u4ee5\u53ca\u5bc6\u6587\uff1a<\/p>\n\n\n\n<p>$$<br>e(x)=31 x^{6} + 19 x^{5} + 4 x^{4} + 2 x^{3} + 40 x^{2} + 3 x + 25<br>$$<\/p>\n\n\n\n<p>\u53ef\u4ee5\u901a\u8fc7\u6784\u9020\u683c\u8fdb\u884c\u79c1\u94a5\u7684\u6062\u590d\uff1a<\/p>\n\n\n\n<p>$$<br>\\mathcal{L}_h=\\left(\\begin{array}{rrrrrrrrrrrrrr} 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 30 &amp; 26 &amp; 8 &amp; 38 &amp; 2 &amp; 40 &amp; 20 \\\\ 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 20 &amp; 30 &amp; 26 &amp; 8 &amp; 38 &amp; 2 &amp; 40 \\\\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 40 &amp; 20 &amp; 30 &amp; 26 &amp; 8 &amp; 38 &amp; 2 \\\\ 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 40 &amp; 20 &amp; 30 &amp; 26 &amp; 8 &amp; 38 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 38 &amp; 2 &amp; 40 &amp; 20 &amp; 30 &amp; 26 &amp; 8 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 8 &amp; 38 &amp; 2 &amp; 40 &amp; 20 &amp; 30 &amp; 26 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 26 &amp; 8 &amp; 38 &amp; 2 &amp; 40 &amp; 20 &amp; 30 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 &amp; 0 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 &amp; 0 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 &amp; 0 \\\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 41 \\end{array}\\right)<br>$$<\/p>\n\n\n\n<p>\u6062\u590d\u79c1\u94a5\u5e76\u89e3\u5bc6\u7684\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>L = matrix(ZZ, 2*N, 2*N)\n\nh_coeff = &#91;ZZ(x) for x in list(h)&#93;\nfor i in range(N):\n    L&#91;i, i&#93; = 1\n    L&#91;N + i, N + i&#93; = q\n    for j in range(N):\n        L&#91;i, N + j&#93; = h_coeff&#91;(j - i) % N&#93;\n\nres = L.BKZ()&#91;1&#93;\nff = R([ZZ(x) for x in res&#91;:N&#93;])\nprint(ff)\n\nfp = inv(Rp, ff)\na = center_lift(Rq, R, Rq(list(ff * e)))\nb = center_lift(Rp, R, Rp(list(fp * a)))\nprint(b)<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D8DEE9FF\">L <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">matrix<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ZZ<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">h_coeff <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">h<\/span><span style=\"color: #ECEFF4\">)&#93;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> i <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> j <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> j<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> h_coeff<\/span><span style=\"color: #ECEFF4\">&#91;(<\/span><span style=\"color: #D8DEE9FF\">j <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">%<\/span><span style=\"color: #D8DEE9FF\"> N<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">res <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> L<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">BKZ<\/span><span style=\"color: #ECEFF4\">()&#91;<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">ff <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">([<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> res<\/span><span style=\"color: #ECEFF4\">&#91;:<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">&#93;])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ff<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">fp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> ff<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">a <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ff <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> e<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">b <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rp<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">fp <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> a<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">b<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u5f97\u5230\u591a\u9879\u5f0f\\(f&#8217;=-x^{6} &#8211; x^{5} + x^{3} &#8211; x^{2} + 1\\)\uff0c\u663e\u7136\u5176\u4e0d\u7b49\u4e8e\u524d\u9762\u7684\u79c1\u94a5\\(f=x^6\u2212x^4+x^3+x^2\u22121\\)\uff0c\u4f46\u662f\u8ba1\u7b97\u51fa\u6765\u7684\\(b=-x^{5} + x^{3} + x^{2} &#8211; x + 1\\)\u5374\u7b49\u4e8e\u524d\u9762\u9009\u62e9\u7684\u660e\u6587.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u4f8b\u9898\uff1a[SCTF 2020]Lattice<\/h3>\n\n\n\n<p>\u9898\u76ee\u5730\u5740\uff1a<a href=\"https:\/\/www.nssctf.cn\/problem\/1399\">SCTF 2020\uff1aLattice<\/a><\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>from base64 import b16encode  \n  \nZx.&lt;x> = ZZ[]  \nn = 109   \nq = 2048  \np = 3  \nDf = 9  \nDg = 10  \nDr = 11  \n  \ndef mul(f,g):  \n    return (f * g) % (x^n-1)  \n  \ndef bal_mod(f,q):  \n    g = list(((f&#91;i&#93; + q\/\/2) % q) - q\/\/2 for i in range(n))  \n    return Zx(g)  \n  \ndef random_poly(d):  \n    assert d &lt;= n  \n    result = n*&#91;0&#93;  \n    for j in range(d):  \n        while True:  \n            r = randrange(n)  \n            if not result&#91;r&#93;: break  \n        result&#91;r&#93; = 1-2*randrange(2)  \n    return Zx(result)  \n  \ndef inv_mod_prime(f,p):  \n    T = Zx.change_ring(Integers(p)).quotient(x^n-1)  \n    return Zx(lift(1 \/ T(f)))  \n  \ndef inv_mod_powerof2(f,q):  \n    assert q.is_power_of(2)  \n    g = inv_mod_prime(f,2)  \n    while True:  \n        r = bal_mod(mul(g,f),q)  \n        if r == 1: return g  \n        g = bal_mod(mul(g,2 - r),q)  \n  \ndef keygen():  \n    f = random_poly(Df)  \n    while True:  \n        try:  \n            fp = inv_mod_prime(f,p)  \n            fq = inv_mod_powerof2(f,q)  \n            break  \n        except:  \n            f = random_poly(Df)  \n    g = random_poly(Dg)  \n    h = bal_mod(p * mul(fq,g),q)  \n    pub_key = h  \n    pri_key = &#91;f,fp&#93;  \n    return pub_key,pri_key  \n  \ndef encrypt(m,h):  \n    r = random_poly(Dr)  \n    e = bal_mod(mul(h,r) + m,q)  \n    return e  \n  \nif __name__ == '__main__':  \n    pub_key,pri_key = keygen()  \n    flag=b'SCTF{***********}'&#91;5:-1&#93;  \n    m = Zx(list(bin(int(b16encode(flag), 16))&#91;2:&#93;))  \n    print(m)  \n    e = encrypt(m,pub_key)  \n    print('pub_key=')  \n    print(pub_key)  \n    print('e=')  \n    print(e)<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #81A1C1\">from<\/span><span style=\"color: #D8DEE9FF\"> base64 <\/span><span style=\"color: #81A1C1\">import<\/span><span style=\"color: #D8DEE9FF\"> b16encode  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Zx<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #81A1C1\">&lt;<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">&gt;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> ZZ<\/span><span style=\"color: #ECEFF4\">[]<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">n <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">109<\/span><span style=\"color: #D8DEE9FF\">   <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">q <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2048<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">p <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">3<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Df <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">9<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Dg <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">10<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Dr <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">11<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">mul<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9\">g<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> g<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">%<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">n<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">bal_mod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9\">q<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(((<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><span style=\"color: #81A1C1\">\/\/<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">%<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><span style=\"color: #81A1C1\">\/\/<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> i <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">n<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Zx<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">random_poly<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">d<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">assert<\/span><span style=\"color: #D8DEE9FF\"> d <\/span><span style=\"color: #81A1C1\">&lt;=<\/span><span style=\"color: #D8DEE9FF\"> n  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    result <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> n<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #B48EAD\">0<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> j <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">d<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">while<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">True<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            r <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">randrange<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">n<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">not<\/span><span style=\"color: #D8DEE9FF\"> result<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">r<\/span><span style=\"color: #ECEFF4\">&#93;:<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">break<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        result<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">r<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #88C0D0\">randrange<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Zx<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">result<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv_mod_prime<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9\">p<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    T <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> Zx<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">change_ring<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Integers<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">p<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">n<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Zx<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">\/<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">T<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)))<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv_mod_powerof2<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9\">q<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">assert<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">is_power_of<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv_mod_prime<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">while<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">True<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        r <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">bal_mod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">mul<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> r <\/span><span style=\"color: #81A1C1\">==<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> g  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">bal_mod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">mul<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">g<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> r<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">keygen<\/span><span style=\"color: #ECEFF4\">():<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    f <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">random_poly<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Df<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">while<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">True<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">try<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            fp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv_mod_prime<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">p<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            fq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv_mod_powerof2<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            <\/span><span style=\"color: #81A1C1\">break<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">except<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            f <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">random_poly<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Df<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    g <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">random_poly<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Dg<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    h <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">bal_mod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">p <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">mul<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">fq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">g<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    pub_key <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> h  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    pri_key <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">fp<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> pub_key<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">pri_key  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">encrypt<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">m<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9\">h<\/span><span style=\"color: #ECEFF4\">):<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    r <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">random_poly<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Dr<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    e <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">bal_mod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">mul<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">h<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">r<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> m<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> e  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> __name__ <\/span><span style=\"color: #81A1C1\">==<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">__main__<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    pub_key<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">pri_key <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">keygen<\/span><span style=\"color: #ECEFF4\">()<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    flag<\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #81A1C1\">b<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">SCTF{***********}<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #B48EAD\">5<\/span><span style=\"color: #ECEFF4\">:<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    m <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Zx<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">bin<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">int<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">b16encode<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">flag<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">16<\/span><span style=\"color: #ECEFF4\">))&#91;<\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">:&#93;))<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">m<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    e <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">encrypt<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">m<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\">pub_key<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">pub_key=<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">pub_key<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">e=<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\">  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">e<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u663e\u7136\u8fd9\u662fNTRU\u52a0\u5bc6\uff0c\u9898\u76ee\u4ee3\u7801\u5c06flag\u8f6c\u6362\u4e3a\u4e8c\u8fdb\u5236\u7136\u540e\u8f6c\u5316\u4e3a\u4e00\u4e2a\u591a\u9879\u5f0f\\(m(x)\\)\uff0c\u7ed9\u51fa\u4e86\u516c\u94a5\\(h(x)\\)\u4ee5\u53ca\u5bc6\u6587\\(e(x)\\)\uff0c\u8981\u6062\u590d\u51fa\u660e\u6587\\(m(x)\\)\uff0c\u5219\u9700\u8981\u5148\u6062\u590d\u51fa\u79c1\u94a5\uff0c\u901a\u8fc7\u4e0b\u9762\u7684\u4ee3\u7801\u5c31\u53ef\u4ee5\u901a\u8fc7\u683c\u653b\u51fb\u6062\u590d\u51fa\u660e\u6587\\(m(x)\\)\uff0c\u5e76\u6062\u590d\u51faflag\uff1a<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#2e3440ff\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" style=\"color:#d8dee9ff;display:none\" aria-label=\"\u590d\u5236\" class=\"code-block-pro-copy-button\"><pre class=\"code-block-pro-copy-button-pre\" aria-hidden=\"true\"><textarea class=\"code-block-pro-copy-button-textarea\" tabindex=\"-1\" aria-hidden=\"true\" readonly>from Crypto.Util.number import *\n\nN = 109\nq = 2048\np = 3\n\n_R = PolynomialRing(ZZ, 'x')\nR = _R.quotient(x^N - 1, 'x')\n\n_Rp = PolynomialRing(Zmod(p), 'x')\nRp = _Rp.quotient(x^N - 1, 'x')\n\n_Rq = PolynomialRing(Zmod(q), 'x')\nRq = _Rq.quotient(x^N - 1, 'x')\n\ndef center_lift(Rm, R, f):\n    modulo = ZZ(Rm(list(f)).base_ring()(-1)) + 1\n    l = &#91;ZZ(x) if x &lt;= modulo \/\/ 2 else ZZ(x) - modulo for x in list(f)&#93;\n    return R(l)\n\ndef inv(Rm, f):\n    return Rm(f).inverse()\n\nh = R(\"...\")\ne = R(\"...\")\n\nL = matrix(ZZ, 2*N, 2*N)\n\nh_coeff = &#91;ZZ(x) for x in list(h)&#93;\nfor i in range(N):\n    L&#91;i, i&#93; = 1\n    L&#91;N + i, N + i&#93; = q\n    for j in range(N):\n        L&#91;i, N + j&#93; = h_coeff&#91;(j - i) % N&#93;\n\nres = L.BKZ(blocksize=24)\nfor v in res:\n    fc = list(v&#91;:N&#93;)\n    c0, c1, c_1 = fc.count(0), fc.count(1), fc.count(-1)\n    if c0 == 100 and c1 + c_1 == 9:\n        f = R(fc)\n        Fp = inv(Rp, f)\n        a = center_lift(Rq, R, Rq(list(f * e)))\n        b = center_lift(Rp, R, Rp(list(Fp * a)))\n        s = \"\".join(&#91;str(x) for x in ct&#93;)\n        pad = 8 - len(s) % 8\n        for i in range(pad + 1):\n            print(long_to_bytes(int('0' * i + s + '0' * (pad - i), 2)))\n        break<\/textarea><\/pre><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki nord\" style=\"background-color: #2e3440ff\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #81A1C1\">from<\/span><span style=\"color: #D8DEE9FF\"> Crypto<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #D8DEE9FF\">Util<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #D8DEE9FF\">number <\/span><span style=\"color: #81A1C1\">import<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">109<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">q <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2048<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">p <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">3<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_R <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ZZ<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">R <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _R<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_Rp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">p<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Rp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _Rp<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">_Rq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">PolynomialRing<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Zmod<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">q<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">Rq <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> _Rq<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">quotient<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #81A1C1\">^<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">x<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    modulo <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)).<\/span><span style=\"color: #88C0D0\">base_ring<\/span><span style=\"color: #ECEFF4\">()(<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">))<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    l <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">&lt;=<\/span><span style=\"color: #D8DEE9FF\"> modulo <\/span><span style=\"color: #81A1C1\">\/\/<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">else<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> modulo <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">)&#93;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">l<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">def<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">Rm<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #D8DEE9\">f<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">return<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rm<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f<\/span><span style=\"color: #ECEFF4\">).<\/span><span style=\"color: #88C0D0\">inverse<\/span><span style=\"color: #ECEFF4\">()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">h <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #A3BE8C\">...<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">e <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #A3BE8C\">...<\/span><span style=\"color: #ECEFF4\">&quot;<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">L <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">matrix<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">ZZ<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">h_coeff <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #88C0D0\">ZZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">h<\/span><span style=\"color: #ECEFF4\">)&#93;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> i <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> q<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> j <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        L<\/span><span style=\"color: #ECEFF4\">&#91;<\/span><span style=\"color: #D8DEE9FF\">i<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> N <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> j<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> h_coeff<\/span><span style=\"color: #ECEFF4\">&#91;(<\/span><span style=\"color: #D8DEE9FF\">j <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">%<\/span><span style=\"color: #D8DEE9FF\"> N<\/span><span style=\"color: #ECEFF4\">&#93;<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">res <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> L<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">BKZ<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9\">blocksize<\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #B48EAD\">24<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> v <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> res<\/span><span style=\"color: #ECEFF4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    fc <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">v<\/span><span style=\"color: #ECEFF4\">&#91;:<\/span><span style=\"color: #D8DEE9FF\">N<\/span><span style=\"color: #ECEFF4\">&#93;)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    c0<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> c1<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> c_1 <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> fc<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">count<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">0<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> fc<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">count<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> fc<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">count<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">    <\/span><span style=\"color: #81A1C1\">if<\/span><span style=\"color: #D8DEE9FF\"> c0 <\/span><span style=\"color: #81A1C1\">==<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">100<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">and<\/span><span style=\"color: #D8DEE9FF\"> c1 <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> c_1 <\/span><span style=\"color: #81A1C1\">==<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">9<\/span><span style=\"color: #ECEFF4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        f <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">R<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">fc<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        Fp <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">inv<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> f<\/span><span style=\"color: #ECEFF4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        a <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rq<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rq<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">f <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> e<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        b <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">center_lift<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Rp<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> R<\/span><span style=\"color: #ECEFF4\">,<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">Rp<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">list<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">Fp <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> a<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        s <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&quot;&quot;<\/span><span style=\"color: #ECEFF4\">.<\/span><span style=\"color: #88C0D0\">join<\/span><span style=\"color: #ECEFF4\">(&#91;<\/span><span style=\"color: #88C0D0\">str<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">x<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> x <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> ct<\/span><span style=\"color: #ECEFF4\">&#93;)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        pad <\/span><span style=\"color: #81A1C1\">=<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">8<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">len<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">s<\/span><span style=\"color: #ECEFF4\">)<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">%<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">8<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">for<\/span><span style=\"color: #D8DEE9FF\"> i <\/span><span style=\"color: #81A1C1\">in<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #88C0D0\">range<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">pad <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">1<\/span><span style=\"color: #ECEFF4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">            <\/span><span style=\"color: #88C0D0\">print<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">long_to_bytes<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #88C0D0\">int<\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">0<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> i <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> s <\/span><span style=\"color: #81A1C1\">+<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #A3BE8C\">0<\/span><span style=\"color: #ECEFF4\">&#39;<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #81A1C1\">*<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #ECEFF4\">(<\/span><span style=\"color: #D8DEE9FF\">pad <\/span><span style=\"color: #81A1C1\">-<\/span><span style=\"color: #D8DEE9FF\"> i<\/span><span style=\"color: #ECEFF4\">),<\/span><span style=\"color: #D8DEE9FF\"> <\/span><span style=\"color: #B48EAD\">2<\/span><span style=\"color: #ECEFF4\">)))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D8DEE9FF\">        <\/span><span style=\"color: #81A1C1\">break<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>\u53ef\u4ee5\u5f97\u5230flag\uff1a<code>SCTF{@#26f35b89d3#@}<\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5173\u4e8eNTRU\u516c\u94a5\u5bc6\u7801\u4f53\u7cfb<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[7,6,10],"class_list":["post-132","post","type-post","status-publish","format-standard","hentry","category-3","tag-crypto","tag-6","tag-10"],"_links":{"self":[{"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/posts\/132","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/comments?post=132"}],"version-history":[{"count":5,"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/posts\/132\/revisions"}],"predecessor-version":[{"id":320,"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/posts\/132\/revisions\/320"}],"wp:attachment":[{"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/media?parent=132"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/categories?post=132"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.triode.cc\/index.php\/wp-json\/wp\/v2\/tags?post=132"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}