{"id":478559,"date":"2026-05-04T18:13:08","date_gmt":"2026-05-04T18:13:08","guid":{"rendered":"https:\/\/savepearlharbor.com\/?p=478559"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=478559","title":{"rendered":"Q-LLL: \u043a\u0430\u043a \u043c\u044b \u0441\u0434\u0435\u043b\u0430\u043b\u0438 LLL-\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044e \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u043c\u043e\u0439, \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u043e\u0439 \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c\u043e\u0439"},"content":{"rendered":"<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h3>\u041d\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430 LLL \u0441 \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 Gram\/Lov\u00e1sz-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0435\u0439 \u0438 exact-\u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u0430\u043c\u0438<\/h3>\n<h4>\u0410\u043d\u043d\u043e\u0442\u0430\u0446\u0438\u044f<\/h4>\n<p>LLL-\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044f \u0434\u0430\u0432\u043d\u043e \u0441\u0442\u0430\u043b\u0430 \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438, \u0442\u0435\u043e\u0440\u0438\u0438 \u0447\u0438\u0441\u0435\u043b, \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0440\u0435\u0448\u0451\u0442\u043e\u043a. \u041e\u0431\u044b\u0447\u043d\u043e LLL \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u201c\u0447\u0451\u0440\u043d\u044b\u0439 \u044f\u0449\u0438\u043a\u201d: \u043d\u0430 \u0432\u0445\u043e\u0434 \u043f\u043e\u0434\u0430\u0451\u0442\u0441\u044f \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0431\u0430\u0437\u0438\u0441, \u0432\u043d\u0443\u0442\u0440\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044f, \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u0431\u0430\u0437\u0438\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c LLL.<\/p>\n<p>\u041d\u043e \u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0432\u0441\u0451 \u0447\u0430\u0449\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0434\u0440\u0443\u0433\u0430\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430. \u041d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0434\u0438\u043d \u0437\u0430\u043f\u0443\u0441\u043a LLL, \u0430 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0439 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0446\u0435\u043b\u043e\u0433\u043e \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430 \u0440\u0435\u0448\u0451\u0442\u043e\u043a: \u0441 \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0430\u043c\u0438, embedding-\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438, \u0432\u0435\u0441\u0430\u043c\u0438, \u043f\u043e\u0434\u0432\u044b\u0431\u043e\u0440\u043a\u0430\u043c\u0438 \u0441\u0442\u0440\u043e\u043a \u0438 \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0430\u043c\u0438 \u043e \u0441\u043a\u0440\u044b\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u0412 \u0442\u0430\u043a\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0432\u0430\u0436\u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0434\u0443\u0446\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0431\u0430\u0437\u0438\u0441, \u043d\u043e \u0438 \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u0433\u0434\u0435 \u0432 \u0431\u0430\u0437\u0438\u0441\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0434\u0435\u0444\u0435\u043a\u0442\u044b;<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u043a\u0438\u0435 Lov\u00e1sz-\u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u0432\u043d\u044b;<\/p>\n<\/li>\n<li>\n<p>\u043a\u0430\u043a\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0440\u0435\u0448\u0451\u0442\u043a\u0438 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u043c\u0438;<\/p>\n<\/li>\n<li>\n<p>\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442;<\/p>\n<\/li>\n<li>\n<p>\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043e\u0442\u0434\u0435\u043b\u0438\u0442\u044c \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0443 \u043e\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0438\u0441\u0442\u0438\u043d\u044b.<\/p>\n<\/li>\n<\/ul>\n<p>\u0422\u0430\u043a \u043f\u043e\u044f\u0432\u0438\u043b\u0430\u0441\u044c \u0441\u0438\u0441\u0442\u0435\u043c\u0430 <strong>Q-LLL \u2014 Quantized-Certified Lattice Reduction<\/strong>.<\/p>\n<p>\u0413\u043b\u0430\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f Q-LLL:<\/p>\n<pre><code>\u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044f \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u0442,exact-\u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u044f,\u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:87px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Q-LLL \u043d\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 LLL-reduced \u0431\u0430\u0437\u0438\u0441\u0430. \u041d\u0430\u043f\u0440\u043e\u0442\u0438\u0432, \u043e\u043d \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0443\u044e exact-\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u044c. \u041d\u043e\u0432\u0438\u0437\u043d\u0430 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c: \u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c <strong>\u043d\u043e\u0432\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f LLL-\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0435\u0439<\/strong>, \u0433\u0434\u0435 \u0432\u044b\u0431\u043e\u0440 \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 Gram\/Lov\u00e1sz-\u043a\u0430\u0440\u0442\u043e\u0439, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u0438\u0441\u0430 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442\u0441\u044f exact-\u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439.<\/p>\n<hr\/>\n<h2>1. \u041f\u043e\u0447\u0435\u043c\u0443 \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u043e\u0441\u044c \u043f\u0435\u0440\u0435\u043e\u0441\u043c\u044b\u0441\u043b\u0438\u0442\u044c LLL<\/h2>\n<p>\u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL \u2014 \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u0430\u043c\u044b\u0445 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0438 \u0440\u0435\u0448\u0451\u0442\u043e\u043a. \u041e\u043d \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0431\u0430\u0437\u0438\u0441 \u0440\u0435\u0448\u0451\u0442\u043a\u0438 \u0438 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0430\u0435\u0442 \u0435\u0433\u043e \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044f size reduction \u0438 swap-\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043f\u043e\u043a\u0430 \u0431\u0430\u0437\u0438\u0441 \u043d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u0438\u0442 Lov\u00e1sz-\u0443\u0441\u043b\u043e\u0432\u0438\u044e.<\/p>\n<p>\u0412 \u0443\u0447\u0435\u0431\u043d\u043e\u0439 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0440\u043e\u0441\u0442\u043e:<\/p>\n<pre><code>\u0434\u0430\u043d \u043e\u0434\u0438\u043d \u0431\u0430\u0437\u0438\u0441 B\u2192 \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c LLL\u2192 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0440\u0435\u0434\u0443\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0431\u0430\u0437\u0438\u0441 B'<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041d\u043e \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0445 \u0438 \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u043d\u044b\u0445 \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u044f\u0445 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435 \u043e\u0434\u0438\u043d \u0431\u0430\u0437\u0438\u0441, \u0430 \u0446\u0435\u043b\u043e\u0435 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432:<\/p>\n<pre><code>B\u2081, B\u2082, B\u2083, ..., B_N<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043c\u043e\u0433\u0443\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f:<\/p>\n<pre><code>\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e;\u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0430\u043c\u0438;embedding weight;\u0433\u0440\u0430\u043d\u0438\u0446\u0430\u043c\u0438 \u043e\u0448\u0438\u0431\u043e\u043a;\u043f\u043e\u0434\u0432\u044b\u0431\u043e\u0440\u043a\u0430\u043c\u0438 \u0441\u0442\u0440\u043e\u043a;\u043f\u043e\u0440\u044f\u0434\u043a\u043e\u043c \u0441\u0442\u0440\u043e\u043a;\u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0435\u0439;\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438 backend-\u0430.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0418 \u0437\u0434\u0435\u0441\u044c \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u043e\u0432\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430:<\/p>\n<blockquote>\n<p>\u0435\u0441\u043b\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0441\u043e\u0442\u043d\u0438 \u0438\u043b\u0438 \u0442\u044b\u0441\u044f\u0447\u0438, \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0442\u044f\u0436\u0451\u043b\u044b\u0439 backend \u043d\u0430 \u0432\u0441\u0435\u0445 \u2014 \u0434\u043e\u0440\u043e\u0433\u043e \u0438 \u043d\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e.<\/p>\n<\/blockquote>\n<p>\u041d\u0443\u0436\u0435\u043d \u0441\u043b\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442 \u043d\u0430 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e \u0440\u0435\u0448\u0451\u0442\u043e\u043a \u0438 \u0441\u043a\u0430\u0436\u0435\u0442:<\/p>\n<pre><code>\u044d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0435\u0440\u0441\u043f\u0435\u043a\u0442\u0438\u0432\u043d\u043e;\u044d\u0442\u043e\u0442 \u2014 \u043f\u043e\u0447\u0442\u0438 \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u0435\u043d;\u0432 \u044d\u0442\u043e\u043c \u0431\u0430\u0437\u0438\u0441\u0435 \u0441\u0438\u043b\u044c\u043d\u044b\u0439 Lov\u00e1sz-\u0434\u0435\u0444\u0435\u043a\u0442 \u0437\u0434\u0435\u0441\u044c;\u044d\u0442\u0443 \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u043e\u0439.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0418\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u0440\u0438\u0432\u0435\u043b\u0430 \u043d\u0430\u0441 \u043a Q-LLL.<\/p>\n<hr\/>\n<h2>2. \u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL \u0437\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0438\u043d\u0443\u0442<\/h2>\n<p>\u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d \u0431\u0430\u0437\u0438\u0441 \u0440\u0435\u0448\u0451\u0442\u043a\u0438:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"B = (b_1, b_2, \\ldots, b_n), \\quad b_i \\in \\mathbb{Z}^m.\" alt=\"B = (b_1, b_2, \\ldots, b_n), \\quad b_i \\in \\mathbb{Z}^m.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/85\/85d\/85d0c86b75435ecaddb9d819d83070c3.svg\" width=\"240\" height=\"16\" data-width=\"30.051\" data-height=\"2.262\" data-vertical-align=\"-0.566\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/85\/85d\/85d0c86b75435ecaddb9d819d83070c3.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/85\/85d\/85d0c86b75435ecaddb9d819d83070c3.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0414\u043b\u044f \u043d\u0435\u0433\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f Gram\u2013Schmidt \u043e\u0440\u0442\u043e\u0433\u043e\u043d\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"b_i^* = b_i - \\sum_{j&lt;i} \\mu_{i,j} b_j^*,\" alt=\"b_i^* = b_i - \\sum_{j&lt;i} \\mu_{i,j} b_j^*,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9\/94\/946\/946df856912ecd301a922b3533214b7c.svg\" width=\"144\" height=\"40\" data-width=\"18.89\" data-height=\"5.155\" data-vertical-align=\"-2.012\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9\/94\/946\/946df856912ecd301a922b3533214b7c.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9\/94\/946\/946df856912ecd301a922b3533214b7c.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0433\u0434\u0435:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\mu_{i,j} = \\frac{\\langle b_i, b_j^* \\rangle}{|b_j^*|^2},\" alt=\"\\mu_{i,j} = \\frac{\\langle b_i, b_j^* \\rangle}{|b_j^*|^2},\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b7\/b7c\/b7c077ed08fdbd180d9594def04b0c21.svg\" width=\"112\" height=\"48\" data-width=\"14.284\" data-height=\"6.271\" data-vertical-align=\"-2.57\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b7\/b7c\/b7c077ed08fdbd180d9594def04b0c21.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b7\/b7c\/b7c077ed08fdbd180d9594def04b0c21.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0430 \u0442\u0430\u043a\u0436\u0435:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"D_i = |b_i^*|^2.\" alt=\"D_i = |b_i^*|^2.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/15\/15e\/15e62e81f4bdeaa005f68bc48c3c9570.svg\" width=\"80\" height=\"16\" data-width=\"10.463\" data-height=\"2.576\" data-vertical-align=\"-0.576\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/15\/15e\/15e62e81f4bdeaa005f68bc48c3c9570.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/15\/15e\/15e62e81f4bdeaa005f68bc48c3c9570.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>LLL-\u0440\u0435\u0434\u0443\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0431\u0430\u0437\u0438\u0441 \u0434\u043e\u043b\u0436\u0435\u043d \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0442\u044c \u0434\u0432\u0443\u043c \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c.<\/p>\n<p>\u041f\u0435\u0440\u0432\u043e\u0435 \u2014 size reduction:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"|\\mu_{i,j}| \\le \\frac{1}{2}, \\quad j &lt; i.\" alt=\"|\\mu_{i,j}| \\le \\frac{1}{2}, \\quad j &lt; i.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/c6\/c66\/c66747620a2f5591536630d7937b6e24.svg\" width=\"144\" height=\"32\" data-width=\"18.237\" data-height=\"4.588\" data-vertical-align=\"-1.729\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/c6\/c66\/c66747620a2f5591536630d7937b6e24.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/c6\/c66\/c66747620a2f5591536630d7937b6e24.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0412\u0442\u043e\u0440\u043e\u0435 \u2014 Lov\u00e1sz condition:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\delta D_{k-1} \\le D_k + \\mu_{k,k-1}^2 D_{k-1}.\" alt=\"\\delta D_{k-1} \\le D_k + \\mu_{k,k-1}^2 D_{k-1}.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4\/4d\/4d3\/4d3f6fafdd7235692a25e3c08cf8fecf.svg\" width=\"200\" height=\"16\" data-width=\"25.897\" data-height=\"2.893\" data-vertical-align=\"-0.881\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4\/4d\/4d3\/4d3f6fafdd7235692a25e3c08cf8fecf.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4\/4d\/4d3\/4d3f6fafdd7235692a25e3c08cf8fecf.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0414\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0432\u0432\u0435\u0434\u0451\u043c <strong>Lov\u00e1sz slack<\/strong>:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\Delta_k(B) =D_k + \\mu_{k,k-1}^2 D_{k-1} - \\delta D_{k-1}.\" alt=\"\\Delta_k(B) =D_k + \\mu_{k,k-1}^2 D_{k-1} - \\delta D_{k-1}.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6b\/6b7\/6b7f0c85ef775a1cda1d544e2e5cf40f.svg\" width=\"280\" height=\"16\" data-width=\"35.046\" data-height=\"2.893\" data-vertical-align=\"-0.881\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6b\/6b7\/6b7f0c85ef775a1cda1d544e2e5cf40f.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6b\/6b7\/6b7f0c85ef775a1cda1d544e2e5cf40f.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0415\u0441\u043b\u0438:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\Delta_k(B) &lt; 0,\" alt=\"\\Delta_k(B) &lt; 0,\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/d0\/d00\/d002b577bc78e86deb454db4dfd3086f.svg\" width=\"88\" height=\"16\" data-width=\"11.161\" data-height=\"2.262\" data-vertical-align=\"-0.566\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/d0\/d00\/d002b577bc78e86deb454db4dfd3086f.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/d0\/d00\/d002b577bc78e86deb454db4dfd3086f.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0442\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u044f (k) \u043d\u0430\u0440\u0443\u0448\u0430\u0435\u0442 Lov\u00e1sz condition, \u0438 swap \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"(b_{k-1})\" alt=\"(b_{k-1})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/54\/540\/54077ed4792cbf00071b3ad05d4839dc.svg\" width=\"40\" height=\"16\" data-width=\"5.797\" data-height=\"2.262\" data-vertical-align=\"-0.566\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/54\/540\/54077ed4792cbf00071b3ad05d4839dc.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/54\/540\/54077ed4792cbf00071b3ad05d4839dc.svg 781w\" loading=\"lazy\" decode=\"async\"\/> \u0438 <img decoding=\"async\" class=\"formula inline\" source=\"(b_k)\" alt=\"(b_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/51\/51e\/51ebe8ea67416b4ec2b3c86563dcf81b.svg\" width=\"24\" height=\"16\" data-width=\"3.752\" data-height=\"2.262\" data-vertical-align=\"-0.566\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/51\/51e\/51ebe8ea67416b4ec2b3c86563dcf81b.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/51\/51e\/51ebe8ea67416b4ec2b3c86563dcf81b.svg 781w\" loading=\"lazy\" decode=\"async\"\/> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u043c \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435\u043c.<\/p>\n<p>\u0418\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e:<\/p>\n<blockquote>\n<p>Lov\u00e1sz slack \u2014 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f \u043c\u0435\u0440\u0430 \u0442\u043e\u0433\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e \u0431\u0430\u0437\u0438\u0441 \u043d\u0430\u0440\u0443\u0448\u0430\u0435\u0442 LLL-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e.<\/p>\n<\/blockquote>\n<p>\u0427\u0435\u043c \u0441\u0438\u043b\u044c\u043d\u0435\u0435 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"(\\Delta_k)\" alt=\"(\\Delta_k)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6a\/6a7\/6a721a9579001b389d672356a513cee6.svg\" width=\"32\" height=\"16\" data-width=\"4.666\" data-height=\"2.262\" data-vertical-align=\"-0.566\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6a\/6a7\/6a721a9579001b389d672356a513cee6.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6a\/6a7\/6a721a9579001b389d672356a513cee6.svg 781w\" loading=\"lazy\" decode=\"async\"\/>, \u0442\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0439 \u0434\u0435\u0444\u0435\u043a\u0442.<\/p>\n<hr\/>\n<h2>3. \u0427\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 LLL<\/h2>\n<p>\u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e:<\/p>\n<pre><code>1. \u0411\u0435\u0440\u0451\u043c \u043f\u043e\u0437\u0438\u0446\u0438\u044e k.2. \u0414\u0435\u043b\u0430\u0435\u043c size reduction.3. \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c Lov\u00e1sz condition.4. \u0415\u0441\u043b\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u043e \u2014 \u0434\u0435\u043b\u0430\u0435\u043c swap.5. \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043d\u0430\u0437\u0430\u0434.6. \u0415\u0441\u043b\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u2014 \u0438\u0434\u0451\u043c \u0434\u0430\u043b\u044c\u0448\u0435.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043a\u0440\u0430\u0441\u0438\u0432\u0430\u044f \u0438 \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u0430\u044f \u0441\u0445\u0435\u043c\u0430.<\/p>\n<p>\u041d\u043e \u043e\u043d\u0430 \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441:<\/p>\n<blockquote>\n<p>\u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043e\u0432\u0435\u0441\u0442\u0438 \u0431\u0430\u0437\u0438\u0441 \u0434\u043e LLL-reduced \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f?<\/p>\n<\/blockquote>\n<p>\u041e\u043d\u0430 \u043d\u0435 \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u0432\u043e\u043f\u0440\u043e\u0441\u044b:<\/p>\n<pre><code>\u0433\u0434\u0435 \u0441\u0430\u043c\u044b\u0439 \u0441\u0438\u043b\u044c\u043d\u044b\u0439 \u0434\u0435\u0444\u0435\u043a\u0442?\u043a\u0430\u043a\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u043e\u0439?\u043a\u0430\u043a\u043e\u0439 \u0438\u0437 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u0435\u0440\u0441\u043f\u0435\u043a\u0442\u0438\u0432\u0435\u043d?\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0431\u0435\u0437 \u043f\u043e\u043b\u043d\u043e\u0433\u043e exact GSO?<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u043b\u044f \u044d\u0442\u0438\u0445 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432 \u043d\u0443\u0436\u0435\u043d \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u043b\u043e\u0439 \u2014 \u0441\u043b\u043e\u0439 \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u044f.<\/p>\n<hr\/>\n<h2>4. \u0418\u0434\u0435\u044f Q-LLL<\/h2>\n<p>Q-LLL \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442 \u043a \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 LLL \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u044a\u0435\u043a\u0442:<\/p>\n<blockquote>\n<p><strong>\u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 Gram\/Lov\u00e1sz oracle.<\/strong><\/p>\n<\/blockquote>\n<p>\u041e\u043d \u0441\u0442\u0440\u043e\u0438\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0431\u0430\u0437\u0438\u0441\u0430:<\/p>\n<pre><code>basis B\u2192 approximate Gram matrix\u2192 approximate GSO\u2192 approximate Lov\u00e1sz slack\u2192 ranked candidate positions<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041d\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0435\u0441\u0442\u044c \u0436\u0451\u0441\u0442\u043a\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e:<\/p>\n<blockquote>\n<p>oracle \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0440\u0430\u0432\u0430 \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043d\u044f\u0442\u044c \u0431\u0430\u0437\u0438\u0441.<\/p>\n<\/blockquote>\n<p>\u041e\u043d \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442:<\/p>\n<pre><code>\u043f\u043e\u0437\u0438\u0446\u0438\u044f k \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u043e\u0434\u043e\u0437\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e;\u0442\u0430\u043c \u0432\u0435\u0440\u043e\u044f\u0442\u0435\u043d Lov\u00e1sz-\u0434\u0435\u0444\u0435\u043a\u0442;\u043f\u0440\u043e\u0432\u0435\u0440\u044c \u0435\u0451 \u043f\u0435\u0440\u0432\u043e\u0439.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0417\u0430\u0442\u0435\u043c \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f exact gate:<\/p>\n<pre><code>\u0435\u0441\u043b\u0438 exact \u0394_k &lt; 0,\u0442\u043e swap \u0440\u0430\u0437\u0440\u0435\u0448\u0451\u043d;\u0438\u043d\u0430\u0447\u0435 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u043e\u0442\u043a\u043b\u043e\u043d\u044f\u0435\u0442\u0441\u044f.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, Q-LLL \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u0430\u043a:<\/p>\n<pre><code>LLL \u0441 \u043d\u043e\u0432\u044b\u043c \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u043e\u043c \u0432\u044b\u0431\u043e\u0440\u0430 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432,\u043d\u043e \u0441\u043e \u0441\u0442\u0430\u0440\u043e\u0439 \u0441\u0442\u0440\u043e\u0433\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>5. \u0427\u0435\u043c Q-LLL \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e LLL<\/h2>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<th>\n<p align=\"left\">\u041a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442<\/p>\n<\/th>\n<th>\n<p align=\"left\">\u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL<\/p>\n<\/th>\n<th>\n<p align=\"left\">Q-LLL<\/p>\n<\/th>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 reduced-\u0431\u0430\u0437\u0438\u0441\u0430<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">Size reduction<\/p>\n<\/td>\n<td>\n<p align=\"left\">exact<\/p>\n<\/td>\n<td>\n<p align=\"left\">exact<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">Lov\u00e1sz decision<\/p>\n<\/td>\n<td>\n<p align=\"left\">exact<\/p>\n<\/td>\n<td>\n<p align=\"left\">exact<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041f\u043e\u0440\u044f\u0434\u043e\u043a \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u043e\u0437\u0438\u0446\u0438\u0439<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0447\u0435\u0440\u0435\u0437 quantized Lov\u00e1sz ranking<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">Approximate \u0441\u043b\u043e\u0439<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043d\u0435\u0442<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0435\u0441\u0442\u044c, advisory-only<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0421\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043e\u0431\u044b\u0447\u043d\u043e \u0432\u043d\u0435\u0448\u043d\u0438\u0439\/\u043d\u0435\u044f\u0432\u043d\u044b\u0439<\/p>\n<\/td>\n<td>\n<p align=\"left\">proof-carrying certificate<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">Independent verifier<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043e\u0431\u044b\u0447\u043d\u043e \u043d\u0435 \u0447\u0430\u0441\u0442\u044c workflow<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0432\u0441\u0442\u0440\u043e\u0435\u043d<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0420\u0430\u0431\u043e\u0442\u0430 \u0441 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043b\u044c\u044e<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0447\u0430\u0441\u0442\u044c \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u044b<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">Evidence\/reporting<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043b\u044c\u044e<\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0447\u0430\u0441\u0442\u044c \u0441\u0438\u0441\u0442\u0435\u043c\u044b<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u0413\u043b\u0430\u0432\u043d\u043e\u0435:<\/p>\n<blockquote>\n<p>Q-LLL \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u0438 LLL. \u041e\u043d \u043c\u0435\u043d\u044f\u0435\u0442 \u043c\u0435\u0445\u0430\u043d\u0438\u043a\u0443 \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0435\u0439.<\/p>\n<\/blockquote>\n<hr\/>\n<h2>6. Quantized Gram\/Lov\u00e1sz oracle<\/h2>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0433\u043b\u0430\u0432\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441:<\/p>\n<blockquote>\n<p>\u043a\u0430\u043a \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c approximate Lov\u00e1sz-\u043a\u0430\u0440\u0442\u0443 \u0434\u0435\u0448\u0435\u0432\u043b\u0435 \u0438\u043b\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u0432\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u043e\u043b\u043d\u044b\u0439 exact-\u0430\u043d\u0430\u043b\u0438\u0437?<\/p>\n<\/blockquote>\n<p>\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e Q-LLL \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0441\u0442\u0440\u043e\u043a \u0431\u0430\u0437\u0438\u0441\u0430.<\/p>\n<p>\u0423\u043f\u0440\u043e\u0449\u0451\u043d\u043d\u0430\u044f \u0441\u0445\u0435\u043c\u0430:<\/p>\n<pre><code>integer basis rows\u2192 normalization\u2192 randomized projection \/ orthogonal transform\u2192 low-bit scalar quantization\u2192 approximate Gram matrix\u2192 approximate GSO\u2192 approximate Lov\u00e1sz slack\u2192 top-K candidates<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, oracle \u0441\u0442\u0440\u043e\u0438\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0431\u0430\u0437\u0438\u0441\u0430. \u0418\u0437 \u044d\u0442\u043e\u0439 \u043a\u0430\u0440\u0442\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f approximate Gram matrix, \u0437\u0430\u0442\u0435\u043c approximate GSO, \u0437\u0430\u0442\u0435\u043c approximate Lov\u00e1sz slack.<\/p>\n<p>\u041d\u0430 \u044d\u0442\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u043c\u044b \u043d\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c:<\/p>\n<pre><code>approximate slack = exact slack.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041c\u044b \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c \u0434\u0440\u0443\u0433\u043e\u0435:<\/p>\n<pre><code>approximate slack \u043c\u043e\u0436\u0435\u0442 \u0434\u0430\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0439 ranking signal.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u0430\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 exact gate.<\/p>\n<hr\/>\n<h2>7. \u041e\u0442\u043a\u0443\u0434\u0430 \u0432\u0437\u044f\u043b\u0430\u0441\u044c \u0438\u0434\u0435\u044f \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438<\/h2>\n<p>\u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0432\u0434\u043e\u0445\u043d\u043e\u0432\u0435\u043d\u0438\u044f \u0441\u0442\u0430\u043b\u0430 \u0438\u0434\u0435\u044f low-bit \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432. \u0412 TurboQuant \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u043d\u043b\u0430\u0439\u043d-\u0432\u0435\u043a\u0442\u043e\u0440\u043d\u043e\u0433\u043e \u043a\u0432\u0430\u043d\u0442\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0435\u043c MSE \u0438 \u043e\u0448\u0438\u0431\u043a\u0438 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f. \u0422\u0430\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u0435, scalar quantization, Lloyd-Max codebooks, \u0430 product-mode \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043a\u0430\u043a MSE-\u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0430\u0442\u043e\u0440 \u043d\u0430 (b-1) \u0431\u0438\u0442 \u043f\u043b\u044e\u0441 QJL \u043d\u0430 \u043e\u0441\u0442\u0430\u0442\u043a\u0435, \u0447\u0442\u043e \u0434\u0430\u0451\u0442 \u043d\u0435\u0441\u043c\u0435\u0449\u0451\u043d\u043d\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 inner product.<\/p>\n<p>\u041d\u043e Q-LLL \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442 \u044d\u0442\u0443 \u0438\u0434\u0435\u044e \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u043c\u0438\u0440.<\/p>\n<p>TurboQuant \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u0437\u0430\u0434\u0430\u0447\u0435\u0439:<\/p>\n<pre><code>\u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u044b \u0432\u0435\u043a\u0442\u043e\u0440\u044b\u2192 low-bit representation\u2192 \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c MSE \/ inner product<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Q-LLL \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u0437\u0430\u0434\u0430\u0447\u0435\u0439:<\/p>\n<pre><code>\u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 lattice basis\u2192 approximate Gram\u2192 approximate GSO\u2192 approximate Lov\u00e1sz slack\u2192 exact-certified reduction<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043d\u0435 \u201c\u0433\u043e\u0442\u043e\u0432\u0443\u044e \u0442\u0435\u043e\u0440\u0435\u043c\u0443 \u0434\u043b\u044f LLL\u201d, \u0430 \u0441\u0430\u043c \u043f\u0440\u0438\u043d\u0446\u0438\u043f:<\/p>\n<blockquote>\n<p>\u0435\u0441\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0442\u044c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 Gram\/Lov\u00e1sz-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438.<\/p>\n<\/blockquote>\n<p>\u0418 \u0434\u0430\u043b\u044c\u0448\u0435 \u044d\u0442\u0430 \u043a\u0430\u0440\u0442\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u0430\u043a advisory layer.<\/p>\n<hr\/>\n<h2>8. \u041f\u043e\u0447\u0435\u043c\u0443 approximate \u0441\u043b\u043e\u0439 \u043d\u0435 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0439<\/h2>\n<p>\u042d\u0442\u043e \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u044b\u0439 \u0438 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043f\u0440\u0438\u043d\u0446\u0438\u043f Q-LLL.<\/p>\n<p>Approximate \u0441\u043b\u043e\u0439 \u043c\u043e\u0436\u0435\u0442 \u043e\u0448\u0438\u0431\u0430\u0442\u044c\u0441\u044f. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u043f\u0435\u0440\u0435\u043e\u0446\u0435\u043d\u0438\u0442\u044c \u0438\u043b\u0438 \u043d\u0435\u0434\u043e\u043e\u0446\u0435\u043d\u0438\u0442\u044c Lov\u00e1sz slack. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0440\u0430\u043d\u0436\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0435\u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u044b\u043c \u043d\u0430 \u043f\u043b\u043e\u0445\u043e \u043e\u0431\u0443\u0441\u043b\u043e\u0432\u043b\u0435\u043d\u043d\u043e\u043c \u0431\u0430\u0437\u0438\u0441\u0435.<\/p>\n<p>\u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0440\u0430\u0432\u0430 \u0434\u0435\u043b\u0430\u0442\u044c basis-changing operation.<\/p>\n<p>\u0412 Q-LLL \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u043e:<\/p>\n<pre><code>oracle proposes;exact gate decides;certificate proves.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442:<\/p>\n<pre><code>1. Oracle \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e k.2. Q-LLL \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 exact Lov\u00e1sz slack \u0394_k.3. \u0415\u0441\u043b\u0438 \u0394_k &lt; 0, swap \u0440\u0430\u0437\u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f.4. \u0415\u0441\u043b\u0438 \u043d\u0435\u0442, \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u043e\u0442\u043a\u043b\u043e\u043d\u044f\u0435\u0442\u0441\u044f.5. \u0412 \u043a\u043e\u043d\u0446\u0435 \u0432\u0435\u0441\u044c \u0431\u0430\u0437\u0438\u0441 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f exact certificate.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u0434\u0432\u0435 \u0432\u0435\u0449\u0438:<\/p>\n<pre><code>\u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u044c approximate \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u044f;\u0441\u0442\u0440\u043e\u0433\u043e\u0441\u0442\u044c exact-\u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>9. Evidence mode<\/h2>\n<p>\u0412 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0435\u0441\u0442\u044c \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0436\u0438\u043c evidence.<\/p>\n<p>\u0412 \u043d\u0451\u043c \u0437\u0430\u043f\u0440\u0435\u0449\u0435\u043d\u044b:<\/p>\n<pre><code>fallback;unsafe approximate swaps;debug\/uniform codebooks;approximate mutation \u0431\u0435\u0437 exact gate.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0440\u0435\u0436\u0438\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u0435\u0435, \u043d\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0436\u0438\u043c \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0441\u0442\u0440\u043e\u0433\u0438\u043c.<\/p>\n<p>\u0412 evidence mode \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0434\u043e\u043b\u0436\u0435\u043d \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c:<\/p>\n<pre><code class=\"json\">{  \"algorithm_class\": \"q-lll\",  \"valid\": true,  \"transform_matches\": true,  \"exact_certified_mutations\": true,  \"fair_scheduler\": true,  \"final_exact_certificate\": true,  \"fallback\": false,  \"exact_gso_calls_during_oracle\": 0}<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041f\u043e\u043b\u0435:<\/p>\n<pre><code>exact_gso_calls_during_oracle = 0<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u043e. \u041e\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u0447\u0442\u043e quantized oracle \u043d\u0435 \u201c\u043f\u043e\u0434\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u043b\u201d \u0432 exact GSO \u043f\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 ranking signal.<\/p>\n<hr\/>\n<h2>10. Fair scheduler<\/h2>\n<p>\u0427\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442, \u0435\u0441\u043b\u0438 oracle \u043e\u0448\u0438\u0431\u0441\u044f \u0438 \u043d\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u043b \u0440\u0430\u0431\u043e\u0447\u0438\u0439 candidate?<\/p>\n<p>\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432 Q-LLL \u0435\u0441\u0442\u044c fair scheduler.<\/p>\n<p>\u0418\u0434\u0435\u044f:<\/p>\n<pre><code>1. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u043e\u0431\u0443\u0435\u043c top-K candidates \u043e\u0442 oracle.2. \u0415\u0441\u043b\u0438 \u043d\u0438 \u043e\u0434\u0438\u043d \u043d\u0435 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 exact gate,   \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c fair exact scan.3. \u0415\u0441\u043b\u0438 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0435 Lov\u00e1sz \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442,   exact scan \u0435\u0433\u043e \u043d\u0430\u0439\u0434\u0451\u0442.4. \u0415\u0441\u043b\u0438 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0439 \u043d\u0435\u0442,   final certificate \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043b\u043e\u0445\u043e\u0439 oracle \u043c\u043e\u0436\u0435\u0442 \u0443\u0445\u0443\u0434\u0448\u0438\u0442\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c, \u043d\u043e \u043d\u0435 \u043b\u043e\u043c\u0430\u0435\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u044c \u0438 \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0437\u0430\u0432\u0438\u0441\u0430\u043d\u0438\u044e.<\/p>\n<p>\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u043e\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u201c\u043e\u043f\u0430\u0441\u043d\u043e\u0439 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438\u201d.<\/p>\n<hr\/>\n<h2>11. Proof-carrying certificates<\/h2>\n<p>\u041e\u0434\u0438\u043d \u0438\u0437 \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u2014 proof-carrying certificate.<\/p>\n<p>\u0418\u0434\u0435\u044f \u043f\u0440\u043e\u0441\u0442\u0430:<\/p>\n<blockquote>\n<p>\u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.<\/p>\n<\/blockquote>\n<p>\u0421\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442:<\/p>\n<pre><code>input basis hash;output basis hash;transform matrix U;delta;first_norm2;min_lovasz_slack;oracle diagnostics;evidence flags.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Verifier \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442:<\/p>\n<pre><code>U * B_in = B_out;U unimodular;exact size reduction;exact Lov\u00e1sz conditions;exact first_norm2;exact min Lov\u00e1sz slack;fallback=false;unsafe approximate swaps=false;exact_gso_calls_during_oracle=0.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0438\u0437 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0438:<\/p>\n<pre><code>\u201c\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0441\u043a\u0430\u0437\u0430\u043b\u0430, \u0447\u0442\u043e \u0432\u0441\u0451 \u0445\u043e\u0440\u043e\u0448\u043e\u201d<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0432 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u044e:<\/p>\n<pre><code>\u201c\u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u043e\u0436\u043d\u043e \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043f\u0435\u0440\u0435\u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c\u201d.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b \u0434\u0432\u0430 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 verifier-\u0441\u043b\u043e\u044f:<\/p>\n<pre><code>cmd\/qlllverify\/main.goscripts\/verify_qlll_certificate.py<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>12. \u041c\u0438\u043d\u0438-\u043f\u0440\u0438\u043c\u0435\u0440: \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 Q-LLL<\/h2>\n<p>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u0431\u0430\u0437\u0438\u0441 \u0438\u0437 10 \u0441\u0442\u0440\u043e\u043a.<\/p>\n<p>\u041e\u0431\u044b\u0447\u043d\u044b\u0439 LLL \u0431\u0443\u0434\u0435\u0442 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:<\/p>\n<pre><code>k = 2k = 3k = 4...<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041e\u043d \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443.<\/p>\n<p>Q-LLL \u0434\u0435\u043b\u0430\u0435\u0442 \u0438\u043d\u0430\u0447\u0435.<\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f approximate Lov\u00e1sz-\u043a\u0430\u0440\u0442\u0430:<\/p>\n<pre><code>k=2:   \u0394\u0302 = +0.12k=3:   \u0394\u0302 = +0.05k=4:   \u0394\u0302 = -0.01k=5:   \u0394\u0302 = +0.20k=6:   \u0394\u0302 = -0.34k=7:   \u0394\u0302 = -0.08k=8:   \u0394\u0302 = +0.02k=9:   \u0394\u0302 = -0.15<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Oracle \u0433\u043e\u0432\u043e\u0440\u0438\u0442:<\/p>\n<pre><code>\u0441\u0430\u043c\u0430\u044f \u043f\u043e\u0434\u043e\u0437\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043f\u043e\u0437\u0438\u0446\u0438\u044f: k=6<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Q-LLL \u043d\u0435 \u0432\u0435\u0440\u0438\u0442 oracle \u043d\u0430 \u0441\u043b\u043e\u0432\u043e. \u041e\u043d \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 exact slack:<\/p>\n<pre><code>\u0394_6 = -17\/104<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0435. \u0417\u043d\u0430\u0447\u0438\u0442 swap \u0440\u0430\u0437\u0440\u0435\u0448\u0451\u043d.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u0431\u044b exact slack \u043e\u043a\u0430\u0437\u0430\u043b\u0441\u044f \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c, Q-LLL \u043e\u0442\u043a\u043b\u043e\u043d\u0438\u043b \u0431\u044b candidate \u0438 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439.<\/p>\n<p>\u0412 \u043a\u043e\u043d\u0446\u0435 verifier \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u0432\u0435\u0441\u044c output basis. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 oracle \u043e\u0448\u0438\u0431\u0430\u043b\u0441\u044f \u043f\u043e \u0434\u043e\u0440\u043e\u0433\u0435, \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f exact-certified.<\/p>\n<hr\/>\n<h2>13. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u043e\u0441\u0442\u044c: eta_delta<\/h2>\n<p>\u0427\u0442\u043e\u0431\u044b \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043e\u0442 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043a \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0438\u0440\u0443\u0435\u043c\u043e\u0439 \u0442\u0435\u043e\u0440\u0438\u0438, \u043c\u044b \u0432\u0432\u0435\u043b\u0438 \u043e\u0446\u0435\u043d\u043a\u0443 \u043e\u0448\u0438\u0431\u043a\u0438 Lov\u00e1sz slack.<\/p>\n<p>\u041f\u0443\u0441\u0442\u044c \u0435\u0441\u0442\u044c exact Gram matrix:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"G\" alt=\"G\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/df\/dfc\/dfcf28d0734569a6a693bc8194de62bf.svg\" width=\"12\" height=\"12\" data-width=\"1.778\" data-height=\"1.645\" data-vertical-align=\"-0.05\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/df\/dfc\/dfcf28d0734569a6a693bc8194de62bf.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/df\/dfc\/dfcf28d0734569a6a693bc8194de62bf.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0438 approximate Gram estimate:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\widehat{G} = G + E.\" alt=\"\\widehat{G} = G + E.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/57\/57b\/57b044b32cdee1b68884f146ae8ab945.svg\" width=\"88\" height=\"24\" data-width=\"11.697\" data-height=\"3.061\" data-vertical-align=\"-0.965\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/57\/57b\/57b044b32cdee1b68884f146ae8ab945.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/57\/57b\/57b044b32cdee1b68884f146ae8ab945.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u041e\u0448\u0438\u0431\u043a\u0430 Gram \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442 \u0432 \u043e\u0448\u0438\u0431\u043a\u0443 GSO:<\/p>\n<pre><code>Gram error\u2192 \u03bc error\u2192 D error<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0410 \u0437\u0430\u0442\u0435\u043c \u0432 \u043e\u0448\u0438\u0431\u043a\u0443 Lov\u00e1sz slack:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"|\\widehat{\\Delta}*k - \\Delta_k| \\le \\eta*\\Delta(k).\" alt=\"|\\widehat{\\Delta}*k - \\Delta_k| \\le \\eta*\\Delta(k).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/89\/892\/892b16b363044f6d90d3f6d0eb691d99.svg\" width=\"184\" height=\"24\" data-width=\"23.86\" data-height=\"3.086\" data-vertical-align=\"-0.977\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/89\/892\/892b16b363044f6d90d3f6d0eb691d99.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/89\/892\/892b16b363044f6d90d3f6d0eb691d99.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0412 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0432\u0432\u0435\u0434\u0451\u043d computable benchmark\/theory layer \u0434\u043b\u044f \u043e\u0446\u0435\u043d\u043a\u0438:<\/p>\n<pre><code>eta_mu(i,j);eta_D(i);eta_Delta(k);margin_stable;sign_preserved_when_margin_stable.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0415\u0441\u043b\u0438 exact violation \u0438\u043c\u0435\u0435\u0442 margin:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"-\\Delta_k &gt; \\eta_\\Delta(k),\" alt=\"-\\Delta_k &gt; \\eta_\\Delta(k),\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6a\/6a1\/6a1ef7b24725911fa1c54c5f4de80353.svg\" width=\"104\" height=\"16\" data-width=\"13.896\" data-height=\"2.262\" data-vertical-align=\"-0.566\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6a\/6a1\/6a1ef7b24725911fa1c54c5f4de80353.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6a\/6a1\/6a1ef7b24725911fa1c54c5f4de80353.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u0442\u043e \u0437\u043d\u0430\u043a \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u044f \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432:<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"\\widehat{\\Delta}_k &lt; 0.\" alt=\"\\widehat{\\Delta}_k &lt; 0.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6e\/6e4\/6e4018f8a6eeecdb425e0e40f62b7dfb.svg\" width=\"56\" height=\"24\" data-width=\"7.683\" data-height=\"3.086\" data-vertical-align=\"-0.977\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6e\/6e4\/6e4018f8a6eeecdb425e0e40f62b7dfb.svg 780w,&#10;       https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6e\/6e4\/6e4018f8a6eeecdb425e0e40f62b7dfb.svg 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<p>\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u044b\u0439 \u0448\u0430\u0433. \u041e\u043d \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e:<\/p>\n<pre><code>oracle \u0447\u0430\u0441\u0442\u043e \u0443\u0433\u0430\u0434\u044b\u0432\u0430\u0435\u0442<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0430:<\/p>\n<pre><code>\u0432 margin-stable \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u0435\u0441\u0442\u044c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u0440\u0438\u0447\u0438\u043d\u0430, \u043f\u043e\u0447\u0435\u043c\u0443 \u0437\u043d\u0430\u043a \u0434\u043e\u043b\u0436\u0435\u043d \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c\u0441\u044f.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>14. \u0427\u0442\u043e \u0443\u0436\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e<\/h2>\n<p>\u0422\u0435\u043a\u0443\u0449\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442:<\/p>\n<pre><code>Q-LLL API;CLI .\/turbolll qlll;reduce -algo qlll;batch-qlll JSONL mode;oraclebench;proof-carrying certificates;independent verifier;release attestation;claim matrix;pilot contour;review package;Python client;competitor harness;benchmark runners.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0415\u0441\u0442\u044c buyer\/auditor package:<\/p>\n<pre><code>00_EXECUTIVE_SUMMARY.md01_CLAIM_MATRIX.md02_Q_LLL_THEORY.md03_REPRODUCIBILITY_GUIDE.md04_EVIDENCE_REPORT.md05_SECURITY_BOUNDARY.md06_LIMITATIONS.md07_BENCHMARK_RESULTS.md08_IP_AND_LICENSE_NOTES.md09_THIRD_PARTY_DEPENDENCIES.md10_RELEASE_INTEGRITY.md<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u043e: \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u043e\u0444\u043e\u0440\u043c\u043b\u0435\u043d\u0430 \u043d\u0435 \u043a\u0430\u043a \u043d\u0430\u0431\u043e\u0440 \u0441\u043a\u0440\u0438\u043f\u0442\u043e\u0432, \u0430 \u043a\u0430\u043a \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c\u044b\u0439 reference package.<\/p>\n<hr\/>\n<h2>15. Reference evidence corpus<\/h2>\n<p>\u0414\u043b\u044f Q-LLL \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d reference corpus \u0438\u0437 \u0448\u0435\u0441\u0442\u0438 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432:<\/p>\n<pre><code>random;qary;hnp-like;ill-conditioned;near-reduced;adversarial-scaled.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e reference case \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u044e\u0442\u0441\u044f:<\/p>\n<pre><code>valid=true;transform_matches=true;fallback=false;final_exact_certificate=true;exact_certified_mutations=true.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u0442\u0430\u043b\u043e\u043d\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442:<\/p>\n<pre><code>Q-LLL \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0442\u0438\u043f\u0430\u0445 \u0431\u0430\u0437\u0438\u0441\u043e\u0432;\u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0442 exact certificate;transform matrix \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u0435\u043d;fallback \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>16. Oracle benchmark<\/h2>\n<p>\u0414\u043b\u044f \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 quantized oracle \u0435\u0441\u0442\u044c <code>oraclebench<\/code>.<\/p>\n<p>\u041e\u043d \u0441\u0447\u0438\u0442\u0430\u0435\u0442:<\/p>\n<pre><code>candidate recall;random top-k baseline;Lov\u00e1sz rank lift;mean normalized Gram error;mean cosine error;ApproxGSO repair diagnostics;exact candidate runtime;quantized oracle runtime;exact_gso_calls_during_oracle.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0412 bounded release grid \u043f\u043e\u043b\u0443\u0447\u0435\u043d checkpoint:<\/p>\n<pre><code>cases: 60hit_at_k: 57\/60random_hit_at_k: 0\/60exact_gso_calls_during_oracle: 0<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043d\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435, \u0447\u0442\u043e Q-LLL \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0432\u0441\u0435\u0445. \u042d\u0442\u043e \u0434\u0440\u0443\u0433\u043e\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<blockquote>\n<p>quantized oracle \u043d\u0435\u0441\u0451\u0442 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0439 ranking signal \u0438 \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 exact GSO \u0432\u043d\u0443\u0442\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f oracle.<\/p>\n<\/blockquote>\n<hr\/>\n<h2>17. Full-grid \u0438\u043d\u0444\u0440\u0430\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430<\/h2>\n<p>\u0414\u043b\u044f \u0431\u043e\u043b\u0435\u0435 \u0441\u0438\u043b\u044c\u043d\u043e\u0439 \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0431\u0430\u0437\u044b \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d full oracle grid:<\/p>\n<pre><code>6 familiesdimensions: 16, 32, 64, 96qbits: 1, 2, 3, 4projections: srht, gaussian, orthogonalestimators: mse, prod<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0412\u0441\u0435\u0433\u043e:<\/p>\n<pre><code>576 planned cases.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Runner \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442:<\/p>\n<pre><code>resume;checkpointing;timeout;failure accounting;planned_cases;completed_cases;failed_cases.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442 benchmark \u0438\u0437 \u0440\u0443\u0447\u043d\u043e\u0433\u043e smoke-\u0442\u0435\u0441\u0442\u0430 \u0432 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u043c\u044b\u0439 \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u043d\u0442\u0443\u0440.<\/p>\n<hr\/>\n<h2>18. TurboLattice Router<\/h2>\n<p>Q-LLL \u0440\u0435\u0448\u0430\u0435\u0442 \u0437\u0430\u0434\u0430\u0447\u0443 \u0432\u043d\u0443\u0442\u0440\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0430\u0437\u0438\u0441\u0430. \u041d\u043e \u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0447\u0430\u0441\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0438\u0437 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432.<\/p>\n<p>\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0435\u0441\u0442\u044c TurboLattice Router.<\/p>\n<p>\u041e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code>lattice variants\u2192 feature extraction\u2192 visibility score\u2192 top-k selection\u2192 backend execution\u2192 recovery\/no-recovery evidence<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0412 HNP-like \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u044d\u0442\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f:<\/p>\n<pre><code>sample count;secret scale;embedding weight;error bounds;row ordering;diagonal balance;lattice model.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Router \u043d\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442 backend. \u041e\u043d \u0440\u0435\u0448\u0430\u0435\u0442:<\/p>\n<pre><code>\u043a\u0443\u0434\u0430 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0442\u044c backend \u043f\u0435\u0440\u0432\u044b\u043c.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>19. \u0421\u0432\u044f\u0437\u044c \u0441 nonce-observatory<\/h2>\n<p>\u0414\u043b\u044f <code>nonce-observatory<\/code> Q-LLL \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u043c lattice-core.<\/p>\n<p>\u041e\u0431\u0449\u0430\u044f \u0441\u0445\u0435\u043c\u0430:<\/p>\n<pre><code>signatures\u2192 protocol validation\u2192 nonce-family hypotheses\u2192 feature contracts\u2192 HNP\/lattice variants\u2192 TurboLattice Router\u2192 Q-LLL \/ backend reduction\u2192 proof-carrying certificate\u2192 recovery\/no-recovery evidence<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c <code>nonce-observatory<\/code> \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0438\u0437 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u044f \u0432 full-stack proof-carrying audit platform.<\/p>\n<p>\u0411\u0435\u0437 Q-LLL:<\/p>\n<pre><code>\u043c\u044b \u0432\u0438\u0434\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0438 \u0440\u0430\u043d\u0436\u0438\u0440\u0443\u0435\u043c \u0440\u0438\u0441\u043a.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0421 Q-LLL:<\/p>\n<pre><code>\u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c lattice workflow,\u0440\u0435\u0434\u0443\u0446\u0438\u0440\u0443\u0435\u043c,\u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c,\u0441\u0435\u0440\u0442\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u0435\u043c,\u0432\u044b\u0434\u0430\u0451\u043c \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043e\u0442\u0447\u0451\u0442.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>20. \u041e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043a\u0430\u043a \u0447\u0430\u0441\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u0430<\/h2>\n<p>\u0412 \u043e\u0434\u043d\u043e\u043c \u0438\u0437 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u0437\u0430\u043f\u0443\u0441\u043a\u043e\u0432 Q-LLL \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0441\u044f \u043a\u0430\u043a backend \u0434\u043b\u044f signature-HNP pubkey recovery workflow.<\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<pre><code>Q-LLL variants tested: 80\/180Q-LLL OK: 80timeouts: 0failed: 0fallback=falseexact_gso_calls_during_oracle=0confirmed d \u2192 pubkey matches: 0<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c.<\/p>\n<p>\u042d\u0442\u043e \u043d\u0435 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442:<\/p>\n<pre><code>Q-LLL \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442:<\/p>\n<pre><code>Q-LLL backend \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442;\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0438 exact-certified;\u043b\u043e\u0436\u043d\u044b\u0445 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0439 \u043d\u0435\u0442;\u0442\u0435\u043a\u0443\u0449\u0430\u044f bounded-HNP\/direct-extraction \u043c\u043e\u0434\u0435\u043b\u044c \u043d\u0435 \u0434\u0430\u043b\u0430 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0451\u043d\u043d\u044b\u0439 d.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u043b\u044f \u043d\u0430\u0443\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u2014 \u0442\u043e\u0436\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442, \u0435\u0441\u043b\u0438 \u043e\u043d \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c.<\/p>\n<p>\u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u043b\u043e\u0439 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e workflow:<\/p>\n<pre><code>synthetic positive controls;enumeration;Babai\/CVP;small row combinations;transform-U analysis;fplll\/flatter comparison;BKZ backend.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<hr\/>\n<h2>21. \u0427\u0442\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u043c<\/h2>\n<p>\u0412 Q-LLL \u043d\u043e\u0432\u0438\u0437\u043d\u0430 \u043d\u0435 \u0432 \u043e\u0434\u043d\u043e\u043c \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0435, \u0430 \u0432 \u0438\u0445 \u0441\u0432\u044f\u0437\u043a\u0435.<\/p>\n<h3>1. Quantized Gram\/Lov\u00e1sz observability<\/h3>\n<p>\u041c\u044b \u0441\u0442\u0440\u043e\u0438\u043c \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0431\u0430\u0437\u0438\u0441\u0430:<\/p>\n<pre><code>Gram\u2192 GSO\u2192 Lov\u00e1sz slack\u2192 candidate ranking<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<h3>2. Exact-certified scheduler<\/h3>\n<p>\u0420\u0435\u0434\u0443\u043a\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u0432\u044b\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u043d\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c, \u0430 \u0447\u0435\u0440\u0435\u0437 ranking.<\/p>\n<p>\u041d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0441\u043b\u0435 exact gate.<\/p>\n<h3>3. Proof-carrying LLL output<\/h3>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0435\u0441\u0451\u0442 \u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e.<\/p>\n<h3>4. Margin-stability layer<\/h3>\n<p>\u0414\u043b\u044f approximate slack \u0432\u0432\u043e\u0434\u0438\u0442\u0441\u044f computable <code>eta_delta<\/code>.<\/p>\n<p>\u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044f\u0442\u044c \u0443\u0441\u0442\u043e\u0439\u0447\u0438\u0432\u044b\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 \u043e\u0442 \u043d\u0435\u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u044b\u0445.<\/p>\n<h3>5. Lattice-variant routing<\/h3>\n<p>Q-LLL \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0435\u0442\u0441\u044f \u0441 TurboLattice Router \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0435 \u0441 \u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439, \u0430 \u0441 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432.<\/p>\n<h3>6. \u0418\u043d\u0442\u0435\u0433\u0440\u0430\u0446\u0438\u044f \u0441 nonce-observatory<\/h3>\n<p>\u0421\u0438\u0441\u0442\u0435\u043c\u0430 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043c\u043e\u0441\u0442\u043e\u043c \u043e\u0442 \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u043c\u044b\u0445 nonce-\u0438\u043d\u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u043a proof-carrying lattice evidence.<\/p>\n<hr\/>\n<h2>22. \u0421\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c\u0438 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u043c\u0438<\/h2>\n<h3>fplll \/ fpylll<\/h3>\n<p><code>fplll<\/code> \u2014 \u0437\u0440\u0435\u043b\u044b\u0439 \u0438 \u0441\u0438\u043b\u044c\u043d\u044b\u0439 backend. \u041e\u043d \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043e\u0432 \u0434\u043b\u044f LLL\/BKZ\/SVP\/CVP.<\/p>\n<p>Q-LLL \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u043d \u043a\u043e\u043d\u043a\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441 \u043d\u0438\u043c \u043a\u0430\u043a \u201c\u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430 \u043e\u0434\u043d\u043e\u043c \u0437\u0430\u043f\u0443\u0441\u043a\u0435\u201d.<\/p>\n<p>\u041e\u0442\u043b\u0438\u0447\u0438\u0435 Q-LLL:<\/p>\n<pre><code>certified scheduler;quantized Lov\u00e1sz observability;proof-carrying certificates;evidence mode;nonce\/HNP integration.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f \u0440\u043e\u043b\u044c:<\/p>\n<pre><code>fplll \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c backend;Q-LLL \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c orchestration\/certification layer.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<h3>FLINT \/ NTL \/ Sage<\/h3>\n<p>\u042d\u0442\u0438 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0441\u0438\u043b\u044c\u043d\u044b \u043a\u0430\u043a \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0438 \u0441\u0440\u0435\u0434\u044b.<\/p>\n<p>Q-LLL \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u0435\u043c, \u0447\u0442\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c reference standard \u0434\u043b\u044f:<\/p>\n<pre><code>exact-certified reduction;certificate verification;lattice intelligence;audit\/evidence workflow.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<h3>flatter<\/h3>\n<p><code>flatter<\/code> \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0435\u043d \u043a\u0430\u043a \u0431\u044b\u0441\u0442\u0440\u044b\u0439 reducer. Q-LLL \u043c\u043e\u0436\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 backends \u043a\u0430\u043a \u0447\u0430\u0441\u0442\u044c workflow, \u043d\u043e \u0441\u0430\u043c \u0444\u043e\u043a\u0443\u0441\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043d\u0430 \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u0438, \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438 \u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438.<\/p>\n<h3>Polynonce \/ leakage-specific methods<\/h3>\n<p>\u0421\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u0438\u043b\u044c\u043d\u0435\u0435 \u0432 \u0441\u0432\u043e\u0451\u043c \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u043c leakage-\u043a\u043b\u0430\u0441\u0441\u0435.<\/p>\n<p>Q-LLL \u0448\u0438\u0440\u0435: \u044d\u0442\u043e \u043d\u0435 \u043e\u0434\u043d\u0430 \u0430\u0442\u0430\u043a\u0430 \u0438 \u043d\u0435 \u043e\u0434\u0438\u043d leakage-template, \u0430 \u0438\u043d\u0444\u0440\u0430\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f, \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0438\u0437\u0430\u0446\u0438\u0438, \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0438 \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 lattice-\u0433\u0438\u043f\u043e\u0442\u0435\u0437.<\/p>\n<hr\/>\n<h2>23. \u0427\u0435\u0433\u043e \u043c\u044b \u043d\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c<\/h2>\n<p>\u0414\u043b\u044f \u0447\u0435\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0438 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0432\u0430\u0436\u043d\u043e \u044f\u0432\u043d\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u0433\u0440\u0430\u043d\u0438\u0446\u044b.<\/p>\n<p>\u041c\u044b \u043d\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c:<\/p>\n<pre><code>Q-LLL \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 fplll;Q-LLL \u0434\u0430\u0451\u0442 \u043b\u0443\u0447\u0448\u0438\u0439 Hermite factor;Q-LLL \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442 BKZ;Q-LLL \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0440\u0435\u0448\u0430\u0435\u0442 \u043b\u044e\u0431\u043e\u0439 HNP;Q-LLL \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442 recovery \u043d\u0430 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u0440\u043f\u0443\u0441\u0430\u0445;\u0442\u0435\u043e\u0440\u0435\u043c\u044b TurboQuant \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 superiority Q-LLL;\u0432\u0441\u0435 perturbation constants \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0437\u0430\u043a\u0440\u044b\u0442\u044b \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041c\u044b \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c:<\/p>\n<pre><code>Q-LLL \u2014 \u043d\u043e\u0432\u044b\u0439 exact-certified LLL-family algorithm;\u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0430\u044f LLL-\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f;candidate selection \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f quantized Gram\/Lov\u00e1sz oracle;basis-changing \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0442 exact gate;\u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f independent verifier;oracle \u043d\u0435 \u043f\u043e\u0434\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u0435\u0442 \u0432 exact GSO;\u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0432\u044b\u0434\u0430\u0451\u0442 proof-carrying evidence.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u0438\u043b\u044c\u043d\u044b\u0439 \u0438 \u0447\u0435\u0441\u0442\u043d\u044b\u0439 claim.<\/p>\n<hr\/>\n<h2>24. \u041f\u043e\u0447\u0435\u043c\u0443 \u044d\u0442\u043e \u0432\u0430\u0436\u043d\u043e \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u043e<\/h2>\n<p>\u0411\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u0441\u0442\u0440\u0430\u0434\u0430\u0435\u0442 \u043e\u0442 \u043e\u0434\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b:<\/p>\n<pre><code>\u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442, \u043d\u043e \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e,\u043a\u0430\u043a \u0435\u0433\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c,\u043a\u0430\u043a \u043f\u043e\u0432\u0442\u043e\u0440\u0438\u0442\u044c,\u0433\u0434\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u044b,\u0447\u0442\u043e \u0431\u044b\u043b\u043e exact,\u0430 \u0447\u0442\u043e \u0431\u044b\u043b\u043e \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u043e\u0439.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>Q-LLL \u0441\u0442\u0440\u043e\u0438\u043b\u0441\u044f \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442.<\/p>\n<p>\u0412 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0435\u0441\u0442\u044c:<\/p>\n<pre><code>claim matrix;security boundary;proof certificates;independent verifier;release attestation;public\/internal report split;pilot contour;review package.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 Q-LLL \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c, \u0430 \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u044b\u043c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430.<\/p>\n<hr\/>\n<h2>25. Roadmap<\/h2>\n<p>\u0411\u043b\u0438\u0436\u0430\u0439\u0448\u0438\u0435 \u0448\u0430\u0433\u0438:<\/p>\n<pre><code>1. \u0417\u0430\u0432\u0435\u0440\u0448\u0438\u0442\u044c full oracle grid.2. \u0417\u0430\u0432\u0435\u0440\u0448\u0438\u0442\u044c full HNP sweep \u043f\u043e easy\/medium\/hard\/extreme.3. \u0421\u0434\u0435\u043b\u0430\u0442\u044c ablation report \u043f\u043e HNP scoring features.4. \u0414\u043e\u0431\u0430\u0432\u0438\u0442\u044c synthetic positive controls \u0434\u043b\u044f signature-HNP.5. \u0414\u043e\u0431\u0430\u0432\u0438\u0442\u044c Q-LLL + enumeration\/CVP postprocessing.6. \u0421\u0440\u0430\u0432\u043d\u0438\u0442\u044c Q-LLL\/fplll\/flatter \u043d\u0430 identical variants.7. \u0418\u043d\u0442\u0435\u0433\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c Q-LLL \u0432 nonce-observatory \u043a\u0430\u043a first-class lattice core.8. \u041f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u0442\u044c \u0432\u043d\u0435\u0448\u043d\u044e\u044e technical review \u0432\u0435\u0440\u0441\u0438\u044e.9. \u0423\u0442\u043e\u0447\u043d\u0438\u0442\u044c paper-grade eta_delta constants.10. \u0421\u043e\u0431\u0440\u0430\u0442\u044c reproducible Docker\/Nix package.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u041e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u044b\u0439 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0448\u0430\u0433:<\/p>\n<blockquote>\n<p>\u0435\u0441\u043b\u0438 HNP-\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u043d\u0430 \u0438 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430, pipeline \u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u0435\u043a\u0440\u0435\u0442 \u0438 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0442\u044c \u0435\u0433\u043e exact-\u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439.<\/p>\n<\/blockquote>\n<p>\u042d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 positive-control \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e solver-completeness.<\/p>\n<hr\/>\n<h2>26. \u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h2>\n<p>Q-LLL \u0440\u043e\u0434\u0438\u043b\u0441\u044f \u0438\u0437 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438\u0434\u0435\u0438:<\/p>\n<blockquote>\n<p>LLL-\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e exact-\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0439, \u043d\u043e \u0438 \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u043c\u043e\u0439.<\/p>\n<\/blockquote>\n<p>\u041c\u044b \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u043c \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 Lov\u00e1sz-\u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439. \u041c\u044b \u043c\u0435\u043d\u044f\u0435\u043c \u0442\u043e, \u043a\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0438\u0434\u0438\u0442 \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f.<\/p>\n<p>\u0418\u0442\u043e\u0433\u043e\u0432\u0430\u044f \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u0430:<\/p>\n<pre><code>integer lattice basis\u2192 quantized Gram\/Lov\u00e1sz oracle\u2192 ranked candidates\u2192 exact Lov\u00e1sz gate\u2192 exact-certified mutation\u2192 fair scheduler\u2192 final exact certificate\u2192 independent verifier<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0413\u043b\u0430\u0432\u043d\u043e\u0435 \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0435:<\/p>\n<pre><code>approximate geometry \u0441\u0442\u0430\u043b\u0430 advisory-\u0441\u043b\u043e\u0435\u043c,\u0430 exact certificate \u043e\u0441\u0442\u0430\u043b\u0441\u044f \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u043c \u0438\u0441\u0442\u0438\u043d\u044b.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0414\u043b\u044f <code>nonce-observatory<\/code> \u044d\u0442\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u044b\u0439 \u043f\u0443\u0442\u044c:<\/p>\n<pre><code>\u043f\u043e\u0434\u043f\u0438\u0441\u0438\u2192 \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u043c\u044b\u0435 nonce-\u0438\u043d\u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b\u2192 lattice hypotheses\u2192 Q-LLL\/TurboLattice\u2192 proof-carrying recovery\/no-recovery evidence.<\/code><div class=\"code-explainer\"><a href=\"https:\/\/sourcecraft.dev\/\" class=\"tm-button code-explainer__link\" style=\"visibility: hidden;\"><img style=\"width:14px;height:14px;object-fit:cover;object-position:left;\"\/><\/a><\/div><\/pre>\n<p>\u0421\u0430\u043c\u0430\u044f \u043a\u043e\u0440\u043e\u0442\u043a\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 Q-LLL:<\/p>\n<blockquote>\n<p><strong>Q-LLL \u2014 \u044d\u0442\u043e exact-certified LLL-family algorithm, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0435\u0439 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f Gram\/Lov\u00e1sz-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044f, \u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u043c \u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u043e\u043c.<\/strong><\/p>\n<\/blockquote>\n<p>\u0418 \u0432 \u044d\u0442\u043e\u043c, \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434, \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u043e\u0442\u043a\u0440\u044b\u0442\u0438\u0435: LLL \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u0430\u043a \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0443 \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0438, \u043d\u043e \u0438 \u043a\u0430\u043a \u043f\u0440\u043e\u0446\u0435\u0441\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u043c\u0443\u044e \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e, \u043d\u0435 \u0442\u0435\u0440\u044f\u044f exact-\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<\/div>\n<p>\u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/1031386\/\">https:\/\/habr.com\/ru\/articles\/1031386\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u041d\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430 LLL \u0441 \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 Gram\/Lov\u00e1sz-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0435\u0439 \u0438 exact-\u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442\u0430\u043c\u0438\u0410\u043d\u043d\u043e\u0442\u0430\u0446\u0438\u044fLLL-\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044f \u0434\u0430\u0432\u043d\u043e \u0441\u0442\u0430\u043b\u0430 \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438, \u0442\u0435\u043e\u0440\u0438\u0438 \u0447\u0438\u0441\u0435\u043b, \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0438 \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u0440\u0435\u0448\u0451\u0442\u043e\u043a. \u041e\u0431\u044b\u0447\u043d\u043e LLL \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u201c\u0447\u0451\u0440\u043d\u044b\u0439 \u044f\u0449\u0438\u043a\u201d: \u043d\u0430 \u0432\u0445\u043e\u0434 \u043f\u043e\u0434\u0430\u0451\u0442\u0441\u044f \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0431\u0430\u0437\u0438\u0441, \u0432\u043d\u0443\u0442\u0440\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044f, \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u0431\u0430\u0437\u0438\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c LLL.\u041d\u043e \u0432 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0432\u0441\u0451 \u0447\u0430\u0449\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0434\u0440\u0443\u0433\u0430\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430. \u041d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0434\u0438\u043d \u0437\u0430\u043f\u0443\u0441\u043a LLL, \u0430 \u0443\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0439 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u0446\u0435\u043b\u043e\u0433\u043e \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430 \u0440\u0435\u0448\u0451\u0442\u043e\u043a: \u0441 \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0430\u043c\u0438, embedding-\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438, \u0432\u0435\u0441\u0430\u043c\u0438, \u043f\u043e\u0434\u0432\u044b\u0431\u043e\u0440\u043a\u0430\u043c\u0438 \u0441\u0442\u0440\u043e\u043a \u0438 \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0430\u043c\u0438 \u043e \u0441\u043a\u0440\u044b\u0442\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u0412 \u0442\u0430\u043a\u043e\u0439 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u0432\u0430\u0436\u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0434\u0443\u0446\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0431\u0430\u0437\u0438\u0441, \u043d\u043e \u0438 \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c:\u0433\u0434\u0435 \u0432 \u0431\u0430\u0437\u0438\u0441\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0434\u0435\u0444\u0435\u043a\u0442\u044b;\u043a\u0430\u043a\u0438\u0435 Lov\u00e1sz-\u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u0432\u043d\u044b;\u043a\u0430\u043a\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0440\u0435\u0448\u0451\u0442\u043a\u0438 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u043c\u0438;\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442;\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043e\u0442\u0434\u0435\u043b\u0438\u0442\u044c \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0443 \u043e\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0438\u0441\u0442\u0438\u043d\u044b.\u0422\u0430\u043a \u043f\u043e\u044f\u0432\u0438\u043b\u0430\u0441\u044c \u0441\u0438\u0441\u0442\u0435\u043c\u0430 Q-LLL \u2014 Quantized-Certified Lattice Reduction.\u0413\u043b\u0430\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f Q-LLL:\u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044f \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0435\u0442,exact-\u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u044f,\u0441\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442.Q-LLL \u043d\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 LLL-reduced \u0431\u0430\u0437\u0438\u0441\u0430. \u041d\u0430\u043f\u0440\u043e\u0442\u0438\u0432, \u043e\u043d \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0443\u044e exact-\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u044c. \u041d\u043e\u0432\u0438\u0437\u043d\u0430 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u043c: \u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c \u043d\u043e\u0432\u0443\u044e \u043c\u043e\u0434\u0435\u043b\u044c \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f LLL-\u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0435\u0439, \u0433\u0434\u0435 \u0432\u044b\u0431\u043e\u0440 \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 Gram\/Lov\u00e1sz-\u043a\u0430\u0440\u0442\u043e\u0439, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u0438\u0441\u0430 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442\u0441\u044f exact-\u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439.1. \u041f\u043e\u0447\u0435\u043c\u0443 \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u043e\u0441\u044c \u043f\u0435\u0440\u0435\u043e\u0441\u043c\u044b\u0441\u043b\u0438\u0442\u044c LLL\u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL \u2014 \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u0430\u043c\u044b\u0445 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0438 \u0440\u0435\u0448\u0451\u0442\u043e\u043a. \u041e\u043d \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0431\u0430\u0437\u0438\u0441 \u0440\u0435\u0448\u0451\u0442\u043a\u0438 \u0438 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0430\u0435\u0442 \u0435\u0433\u043e \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044f size reduction \u0438 swap-\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043f\u043e\u043a\u0430 \u0431\u0430\u0437\u0438\u0441 \u043d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u0438\u0442 Lov\u00e1sz-\u0443\u0441\u043b\u043e\u0432\u0438\u044e.\u0412 \u0443\u0447\u0435\u0431\u043d\u043e\u0439 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0440\u043e\u0441\u0442\u043e:\u0434\u0430\u043d \u043e\u0434\u0438\u043d \u0431\u0430\u0437\u0438\u0441 B\u2192 \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c LLL\u2192 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0440\u0435\u0434\u0443\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0431\u0430\u0437\u0438\u0441 B&#8217;\u041d\u043e \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0445 \u0438 \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u043d\u044b\u0445 \u0441\u0446\u0435\u043d\u0430\u0440\u0438\u044f\u0445 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435 \u043e\u0434\u0438\u043d \u0431\u0430\u0437\u0438\u0441, \u0430 \u0446\u0435\u043b\u043e\u0435 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432:B\u2081, B\u2082, B\u2083, &#8230;, B_N\u042d\u0442\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u043c\u043e\u0433\u0443\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f:\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e;\u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0430\u043c\u0438;embedding weight;\u0433\u0440\u0430\u043d\u0438\u0446\u0430\u043c\u0438 \u043e\u0448\u0438\u0431\u043e\u043a;\u043f\u043e\u0434\u0432\u044b\u0431\u043e\u0440\u043a\u0430\u043c\u0438 \u0441\u0442\u0440\u043e\u043a;\u043f\u043e\u0440\u044f\u0434\u043a\u043e\u043c \u0441\u0442\u0440\u043e\u043a;\u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0435\u0439;\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438 backend-\u0430.\u0418 \u0437\u0434\u0435\u0441\u044c \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u043e\u0432\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430:\u0435\u0441\u043b\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0441\u043e\u0442\u043d\u0438 \u0438\u043b\u0438 \u0442\u044b\u0441\u044f\u0447\u0438, \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0442\u044f\u0436\u0451\u043b\u044b\u0439 backend \u043d\u0430 \u0432\u0441\u0435\u0445 \u2014 \u0434\u043e\u0440\u043e\u0433\u043e \u0438 \u043d\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e.\u041d\u0443\u0436\u0435\u043d \u0441\u043b\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442 \u043d\u0430 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e \u0440\u0435\u0448\u0451\u0442\u043e\u043a \u0438 \u0441\u043a\u0430\u0436\u0435\u0442:\u044d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0435\u0440\u0441\u043f\u0435\u043a\u0442\u0438\u0432\u043d\u043e;\u044d\u0442\u043e\u0442 \u2014 \u043f\u043e\u0447\u0442\u0438 \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u0435\u043d;\u0432 \u044d\u0442\u043e\u043c \u0431\u0430\u0437\u0438\u0441\u0435 \u0441\u0438\u043b\u044c\u043d\u044b\u0439 Lov\u00e1sz-\u0434\u0435\u0444\u0435\u043a\u0442 \u0437\u0434\u0435\u0441\u044c;\u044d\u0442\u0443 \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u043e\u0439.\u0418\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u0440\u0438\u0432\u0435\u043b\u0430 \u043d\u0430\u0441 \u043a Q-LLL.2. \u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL \u0437\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0438\u043d\u0443\u0442\u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d \u0431\u0430\u0437\u0438\u0441 \u0440\u0435\u0448\u0451\u0442\u043a\u0438:\u0414\u043b\u044f \u043d\u0435\u0433\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f Gram\u2013Schmidt \u043e\u0440\u0442\u043e\u0433\u043e\u043d\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f:\u0433\u0434\u0435:\u0430 \u0442\u0430\u043a\u0436\u0435:LLL-\u0440\u0435\u0434\u0443\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0431\u0430\u0437\u0438\u0441 \u0434\u043e\u043b\u0436\u0435\u043d \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0442\u044c \u0434\u0432\u0443\u043c \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c.\u041f\u0435\u0440\u0432\u043e\u0435 \u2014 size reduction:\u0412\u0442\u043e\u0440\u043e\u0435 \u2014 Lov\u00e1sz condition:\u0414\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0432\u0432\u0435\u0434\u0451\u043c Lov\u00e1sz slack:\u0415\u0441\u043b\u0438:\u0442\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u044f (k) \u043d\u0430\u0440\u0443\u0448\u0430\u0435\u0442 Lov\u00e1sz condition, \u0438 swap \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u0430\u043c\u0438  \u0438  \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u043c \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435\u043c.\u0418\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e:Lov\u00e1sz slack \u2014 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f \u043c\u0435\u0440\u0430 \u0442\u043e\u0433\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e \u0431\u0430\u0437\u0438\u0441 \u043d\u0430\u0440\u0443\u0448\u0430\u0435\u0442 LLL-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u044e.\u0427\u0435\u043c \u0441\u0438\u043b\u044c\u043d\u0435\u0435 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 , \u0442\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0439 \u0434\u0435\u0444\u0435\u043a\u0442.3. \u0427\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 LLL\u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLL \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u0442 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u043e \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e:1. \u0411\u0435\u0440\u0451\u043c \u043f\u043e\u0437\u0438\u0446\u0438\u044e k.2. \u0414\u0435\u043b\u0430\u0435\u043c size reduction.3. \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c Lov\u00e1sz condition.4. \u0415\u0441\u043b\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u043e \u2014 \u0434\u0435\u043b\u0430\u0435\u043c swap.5. \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043d\u0430\u0437\u0430\u0434.6. \u0415\u0441\u043b\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u2014 \u0438\u0434\u0451\u043c \u0434\u0430\u043b\u044c\u0448\u0435.\u042d\u0442\u043e \u043a\u0440\u0430\u0441\u0438\u0432\u0430\u044f \u0438 \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u0430\u044f \u0441\u0445\u0435\u043c\u0430.\u041d\u043e \u043e\u043d\u0430 \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0432\u043e\u043f\u0440\u043e\u0441:\u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043e\u0432\u0435\u0441\u0442\u0438 \u0431\u0430\u0437\u0438\u0441 \u0434\u043e LLL-reduced \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f?\u041e\u043d\u0430 \u043d\u0435 \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u0432\u043e\u043f\u0440\u043e\u0441\u044b:\u0433\u0434\u0435 \u0441\u0430\u043c\u044b\u0439 \u0441\u0438\u043b\u044c\u043d\u044b\u0439 \u0434\u0435\u0444\u0435\u043a\u0442?\u043a\u0430\u043a\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u0441\u0442\u043e\u0438\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u043e\u0439?\u043a\u0430\u043a\u043e\u0439 \u0438\u0437 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0440\u0435\u0448\u0451\u0442\u043a\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u0435\u0440\u0441\u043f\u0435\u043a\u0442\u0438\u0432\u0435\u043d?\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0431\u0435\u0437 \u043f\u043e\u043b\u043d\u043e\u0433\u043e exact GSO?\u0414\u043b\u044f \u044d\u0442\u0438\u0445 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u0432 \u043d\u0443\u0436\u0435\u043d \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u043b\u043e\u0439 \u2014 \u0441\u043b\u043e\u0439 \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u044f.4. \u0418\u0434\u0435\u044f Q-LLLQ-LLL \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442 \u043a \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 LLL \u043d\u043e\u0432\u044b\u0439 \u043e\u0431\u044a\u0435\u043a\u0442:\u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 Gram\/Lov\u00e1sz oracle.\u041e\u043d \u0441\u0442\u0440\u043e\u0438\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0431\u0430\u0437\u0438\u0441\u0430:basis B\u2192 approximate Gram matrix\u2192 approximate GSO\u2192 approximate Lov\u00e1sz slack\u2192 ranked candidate positions\u041d\u043e \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0435\u0441\u0442\u044c \u0436\u0451\u0441\u0442\u043a\u043e\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e:oracle \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0440\u0430\u0432\u0430 \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043d\u044f\u0442\u044c \u0431\u0430\u0437\u0438\u0441.\u041e\u043d \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442:\u043f\u043e\u0437\u0438\u0446\u0438\u044f k \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u043e\u0434\u043e\u0437\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e;\u0442\u0430\u043c \u0432\u0435\u0440\u043e\u044f\u0442\u0435\u043d Lov\u00e1sz-\u0434\u0435\u0444\u0435\u043a\u0442;\u043f\u0440\u043e\u0432\u0435\u0440\u044c \u0435\u0451 \u043f\u0435\u0440\u0432\u043e\u0439.\u0417\u0430\u0442\u0435\u043c \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f exact gate:\u0435\u0441\u043b\u0438 exact \u0394_k &lt; 0,\u0442\u043e swap \u0440\u0430\u0437\u0440\u0435\u0448\u0451\u043d;\u0438\u043d\u0430\u0447\u0435 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u043e\u0442\u043a\u043b\u043e\u043d\u044f\u0435\u0442\u0441\u044f.\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, Q-LLL \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u0430\u043a:LLL \u0441 \u043d\u043e\u0432\u044b\u043c \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u043e\u043c \u0432\u044b\u0431\u043e\u0440\u0430 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432,\u043d\u043e \u0441\u043e \u0441\u0442\u0430\u0440\u043e\u0439 \u0441\u0442\u0440\u043e\u0433\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430.5. \u0427\u0435\u043c Q-LLL \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e LLL\u041a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u041a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 LLLQ-LLL\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 reduced-\u0431\u0430\u0437\u0438\u0441\u0430\u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439\u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439Size reductionexactexactLov\u00e1sz decisionexactexact\u041f\u043e\u0440\u044f\u0434\u043e\u043a \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u043e\u0437\u0438\u0446\u0438\u0439\u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439\u0447\u0435\u0440\u0435\u0437 quantized Lov\u00e1sz rankingApproximate \u0441\u043b\u043e\u0439\u043d\u0435\u0442\u0435\u0441\u0442\u044c, advisory-only\u0421\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430\u043e\u0431\u044b\u0447\u043d\u043e \u0432\u043d\u0435\u0448\u043d\u0438\u0439\/\u043d\u0435\u044f\u0432\u043d\u044b\u0439proof-carrying certificateIndependent verifier\u043e\u0431\u044b\u0447\u043d\u043e \u043d\u0435 \u0447\u0430\u0441\u0442\u044c workflow\u0432\u0441\u0442\u0440\u043e\u0435\u043d\u0420\u0430\u0431\u043e\u0442\u0430 \u0441 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432\u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043b\u044c\u044e\u0447\u0430\u0441\u0442\u044c \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u044bEvidence\/reporting\u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043b\u044c\u044e\u0447\u0430\u0441\u0442\u044c \u0441\u0438\u0441\u0442\u0435\u043c\u044b\u0413\u043b\u0430\u0432\u043d\u043e\u0435:Q-LLL \u043d\u0435 \u043c\u0435\u043d\u044f\u0435\u0442 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0443 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u0438 LLL. \u041e\u043d \u043c\u0435\u043d\u044f\u0435\u0442 \u043c\u0435\u0445\u0430\u043d\u0438\u043a\u0443 \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u0435\u0439.6. Quantized Gram\/Lov\u00e1sz oracle\u0422\u0435\u043f\u0435\u0440\u044c \u0433\u043b\u0430\u0432\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441:\u043a\u0430\u043a \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c approximate Lov\u00e1sz-\u043a\u0430\u0440\u0442\u0443 \u0434\u0435\u0448\u0435\u0432\u043b\u0435 \u0438\u043b\u0438 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u0432\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u043e\u043b\u043d\u044b\u0439 exact-\u0430\u043d\u0430\u043b\u0438\u0437?\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e Q-LLL \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0441\u0442\u0440\u043e\u043a \u0431\u0430\u0437\u0438\u0441\u0430.\u0423\u043f\u0440\u043e\u0449\u0451\u043d\u043d\u0430\u044f \u0441\u0445\u0435\u043c\u0430:integer basis rows\u2192 normalization\u2192 randomized projection \/ orthogonal transform\u2192 low-bit scalar quantization\u2192 approximate Gram matrix\u2192 approximate GSO\u2192 approximate Lov\u00e1sz slack\u2192 top-K candidates\u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, oracle \u0441\u0442\u0440\u043e\u0438\u0442 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0445 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u043c\u0435\u0436\u0434\u0443 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0431\u0430\u0437\u0438\u0441\u0430. \u0418\u0437 \u044d\u0442\u043e\u0439 \u043a\u0430\u0440\u0442\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f approximate Gram matrix, \u0437\u0430\u0442\u0435\u043c approximate GSO, \u0437\u0430\u0442\u0435\u043c approximate Lov\u00e1sz slack.\u041d\u0430 \u044d\u0442\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u043c\u044b \u043d\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c:approximate slack = exact slack.\u041c\u044b \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u043c \u0434\u0440\u0443\u0433\u043e\u0435:approximate slack \u043c\u043e\u0436\u0435\u0442 \u0434\u0430\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0439 ranking signal.\u0414\u0430\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 exact gate.7. \u041e\u0442\u043a\u0443\u0434\u0430 \u0432\u0437\u044f\u043b\u0430\u0441\u044c \u0438\u0434\u0435\u044f \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438\u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0432\u0434\u043e\u0445\u043d\u043e\u0432\u0435\u043d\u0438\u044f \u0441\u0442\u0430\u043b\u0430 \u0438\u0434\u0435\u044f low-bit \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432. \u0412 TurboQuant \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u043d\u043b\u0430\u0439\u043d-\u0432\u0435\u043a\u0442\u043e\u0440\u043d\u043e\u0433\u043e \u043a\u0432\u0430\u043d\u0442\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u0435\u043c MSE \u0438 \u043e\u0448\u0438\u0431\u043a\u0438 \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f. \u0422\u0430\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0435 \u0432\u0440\u0430\u0449\u0435\u043d\u0438\u0435, scalar quantization, Lloyd-Max codebooks, \u0430 product-mode \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043a\u0430\u043a MSE-\u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0430\u0442\u043e\u0440 \u043d\u0430 (b-1) \u0431\u0438\u0442 \u043f\u043b\u044e\u0441 QJL \u043d\u0430 \u043e\u0441\u0442\u0430\u0442\u043a\u0435, \u0447\u0442\u043e \u0434\u0430\u0451\u0442 \u043d\u0435\u0441\u043c\u0435\u0449\u0451\u043d\u043d\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 inner product.\u041d\u043e Q-LLL \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442 \u044d\u0442\u0443 \u0438\u0434\u0435\u044e \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u043c\u0438\u0440.TurboQuant \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u0437\u0430\u0434\u0430\u0447\u0435\u0439:\u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u044b \u0432\u0435\u043a\u0442\u043e\u0440\u044b\u2192 low-bit representation\u2192 \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c MSE \/ inner productQ-LLL \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u0437\u0430\u0434\u0430\u0447\u0435\u0439:\u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 lattice basis\u2192 approximate Gram\u2192 approximate GSO\u2192 approximate Lov\u00e1sz slack\u2192 exact-certified reduction\u0422\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043d\u0435 \u201c\u0433\u043e\u0442\u043e\u0432\u0443\u044e \u0442\u0435\u043e\u0440\u0435\u043c\u0443 \u0434\u043b\u044f LLL\u201d, \u0430 \u0441\u0430\u043c \u043f\u0440\u0438\u043d\u0446\u0438\u043f:\u0435\u0441\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043a\u0432\u0430\u043d\u0442\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0442\u044c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0451\u043d\u043d\u0443\u044e \u043a\u0430\u0440\u0442\u0443 Gram\/Lov\u00e1sz-\u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0438.\u0418 \u0434\u0430\u043b\u044c\u0448\u0435 \u044d\u0442\u0430 \u043a\u0430\u0440\u0442\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u0430\u043a advisory layer.8. \u041f\u043e\u0447\u0435\u043c\u0443 approximate \u0441\u043b\u043e\u0439 \u043d\u0435 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0439\u042d\u0442\u043e \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u044b\u0439 \u0438 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043f\u0440\u0438\u043d\u0446\u0438\u043f Q-LLL.Approximate \u0441\u043b\u043e\u0439 \u043c\u043e\u0436\u0435\u0442 \u043e\u0448\u0438\u0431\u0430\u0442\u044c\u0441\u044f. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u043f\u0435\u0440\u0435\u043e\u0446\u0435\u043d\u0438\u0442\u044c \u0438\u043b\u0438 \u043d\u0435\u0434\u043e\u043e\u0446\u0435\u043d\u0438\u0442\u044c Lov\u00e1sz slack. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0440\u0430\u043d\u0436\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432. \u041e\u043d \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0435\u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u044b\u043c \u043d\u0430 \u043f\u043b\u043e\u0445\u043e \u043e\u0431\u0443\u0441\u043b\u043e\u0432\u043b\u0435\u043d\u043d\u043e\u043c \u0431\u0430\u0437\u0438\u0441\u0435.\u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u043d \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043f\u0440\u0430\u0432\u0430 \u0434\u0435\u043b\u0430\u0442\u044c basis-changing operation.\u0412 Q-LLL \u0434\u0435\u0439\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u043e:oracle proposes;exact gate decides;certificate proves.\u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442:1. Oracle \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e k.2. Q-LLL \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 exact Lov\u00e1sz slack \u0394_k.3. \u0415\u0441\u043b\u0438 \u0394_k &lt; 0, swap \u0440\u0430\u0437\u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f.4. \u0415\u0441\u043b\u0438 \u043d\u0435\u0442, \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442 \u043e\u0442\u043a\u043b\u043e\u043d\u044f\u0435\u0442\u0441\u044f.5. \u0412 \u043a\u043e\u043d\u0446\u0435 \u0432\u0435\u0441\u044c \u0431\u0430\u0437\u0438\u0441 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f exact certificate.\u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0438\u0442\u044c \u0434\u0432\u0435 \u0432\u0435\u0449\u0438:\u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0438 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u044c approximate \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u044f;\u0441\u0442\u0440\u043e\u0433\u043e\u0441\u0442\u044c exact-\u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438.9. Evidence mode\u0412 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0435\u0441\u0442\u044c \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0436\u0438\u043c evidence.\u0412 \u043d\u0451\u043c \u0437\u0430\u043f\u0440\u0435\u0449\u0435\u043d\u044b:fallback;unsafe approximate swaps;debug\/uniform codebooks;approximate mutation \u0431\u0435\u0437 exact gate.\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u0440\u0435\u0436\u0438\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u0435\u0435, \u043d\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0436\u0438\u043c \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0441\u0442\u0440\u043e\u0433\u0438\u043c.\u0412 evidence mode \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0434\u043e\u043b\u0436\u0435\u043d \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c:{  &#171;algorithm_class&#187;: &#171;q-lll&#187;,  &#171;valid&#187;: true,  &#171;transform_matches&#187;: true,  &#171;exact_certified_mutations&#187;: true,  &#171;fair_scheduler&#187;: true,  &#171;final_exact_certificate&#187;: true,  &#171;fallback&#187;: false,  &#171;exact_gso_calls_during_oracle&#187;: 0}\u041f\u043e\u043b\u0435:exact_gso_calls_during_oracle = 0\u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432\u0430\u0436\u043d\u043e. \u041e\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u0447\u0442\u043e quantized oracle \u043d\u0435 \u201c\u043f\u043e\u0434\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u043b\u201d \u0432 exact GSO \u043f\u0440\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0438 ranking signal.10. Fair scheduler\u0427\u0442\u043e \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442, \u0435\u0441\u043b\u0438 oracle \u043e\u0448\u0438\u0431\u0441\u044f \u0438 \u043d\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u043b \u0440\u0430\u0431\u043e\u0447\u0438\u0439 candidate?\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0432 Q-LLL \u0435\u0441\u0442\u044c fair scheduler.\u0418\u0434\u0435\u044f:1. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0440\u043e\u0431\u0443\u0435\u043c top-K candidates \u043e\u0442 oracle.2. \u0415\u0441\u043b\u0438 \u043d\u0438 \u043e\u0434\u0438\u043d \u043d\u0435 \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u0442 exact gate,   \u0437\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c fair exact scan.3. \u0415\u0441\u043b\u0438 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0435 Lov\u00e1sz \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442,   exact scan \u0435\u0433\u043e \u043d\u0430\u0439\u0434\u0451\u0442.4. \u0415\u0441\u043b\u0438 \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u0439 \u043d\u0435\u0442,   final certificate \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u043b\u043e\u0445\u043e\u0439 oracle \u043c\u043e\u0436\u0435\u0442 \u0443\u0445\u0443\u0434\u0448\u0438\u0442\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c, \u043d\u043e \u043d\u0435 \u043b\u043e\u043c\u0430\u0435\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u044c \u0438 \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043a \u0437\u0430\u0432\u0438\u0441\u0430\u043d\u0438\u044e.\u042d\u0442\u043e \u0432\u0430\u0436\u043d\u043e\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u201c\u043e\u043f\u0430\u0441\u043d\u043e\u0439 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438\u201d.11. Proof-carrying certificates\u041e\u0434\u0438\u043d \u0438\u0437 \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u2014 proof-carrying certificate.\u0418\u0434\u0435\u044f \u043f\u0440\u043e\u0441\u0442\u0430:\u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430.\u0421\u0435\u0440\u0442\u0438\u0444\u0438\u043a\u0430\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442:input basis hash;output basis hash;transform matrix U;delta;first_norm2;min_lovasz_slack;oracle diagnostics;evidence flags.Verifier \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442:U * B_in = B_out;U unimodular;exact size reduction;exact Lov\u00e1sz conditions;exact first_norm2;exact min Lov\u00e1sz slack;fallback=false;unsafe approximate swaps=false;exact_gso_calls_during_oracle=0.\u042d\u0442\u043e \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0438\u0442 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0438\u0437 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0438:\u201c\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0441\u043a\u0430\u0437\u0430\u043b\u0430, \u0447\u0442\u043e \u0432\u0441\u0451 \u0445\u043e\u0440\u043e\u0448\u043e\u201d\u0432 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u044e:\u201c\u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u043e\u0436\u043d\u043e \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u043f\u0435\u0440\u0435\u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c\u201d.\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b \u0434\u0432\u0430 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 verifier-\u0441\u043b\u043e\u044f:cmd\/qlllverify\/main.goscripts\/verify_qlll_certificate.py12. \u041c\u0438\u043d\u0438-\u043f\u0440\u0438\u043c\u0435\u0440: \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 Q-LLL\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c \u0431\u0430\u0437\u0438\u0441 \u0438\u0437 10 \u0441\u0442\u0440\u043e\u043a.\u041e\u0431\u044b\u0447\u043d\u044b\u0439 LLL \u0431\u0443\u0434\u0435\u0442 \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:k = 2k = 3k = 4&#8230;\u041e\u043d \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443.Q-LLL \u0434\u0435\u043b\u0430\u0435\u0442 \u0438\u043d\u0430\u0447\u0435.\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f approximate Lov\u00e1sz-\u043a\u0430\u0440\u0442\u0430:k=2:   \u0394\u0302 = +0.12k=3:   \u0394\u0302 = +0.05k=4:   \u0394\u0302 = -0.01k=5:   \u0394\u0302 = +0.20k=6:   \u0394\u0302 = -0.34k=7:   \u0394\u0302 = -0.08k=8:   \u0394\u0302 = +0.02k=9:   \u0394\u0302 = -0.15Oracle&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-478559","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/478559","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=478559"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/478559\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=478559"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=478559"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=478559"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}