{"id":313570,"date":"2020-11-22T21:00:24","date_gmt":"2020-11-22T21:00:24","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=313570"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=313570","title":{"rendered":"\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u0430\u043d\u0446\u0435 \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 (Knapsack problem in cryptography)"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\">\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 (\u0438\u043b\u0438 \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u0430\u043d\u0446\u0435) \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 (\u0430\u043d\u0433\u043b. Knapsack problem) \u2014 \u044d\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430, \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0430\u043c\u0435\u0440\u0438\u043a\u0430\u043d\u0441\u043a\u0438\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u044b \u0420\u0430\u043b\u044c\u0444 \u041c\u0435\u0440\u043a\u043b \u0438 \u041c\u0430\u0440\u0442\u0438\u043d \u0425\u0435\u043b\u043b\u043c\u0430\u043d \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c.<\/p>\n<p>  <b>\u0414\u0430\u043b\u0435\u0435 \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435<\/b><br \/>  <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/f-\/3q\/-k\/f-3q-kjzcfguauyssd_v4k1poju.png\" width=\"130\" height=\"130\" align=\"right\"\/>  <\/p>\n<ul>\n<li>\u0424\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 (+\u043f\u043e\u0447\u0435\u043c\u0443 \u0440\u044e\u043a\u0437\u0430\u043a?)<\/li>\n<li>\u041b\u0435\u0433\u043a\u0430\u044f \u0438 \u0442\u0440\u0443\u0434\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b<\/li>\n<li>\u041f\u0440\u0438\u043c\u0435\u0440\u044b<\/li>\n<li>\u0418\u0441\u0442\u043e\u0440\u0438\u044f<\/li>\n<\/ul>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c?<\/b>                         <\/p>\n<div class=\"spoiler_text\">\u0414\u043b\u044f \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0434\u0432\u0430 \u043a\u043b\u044e\u0447\u0430. <\/p>\n<ul>\n<li> \u041e\u0434\u0438\u043d \u043a\u043b\u044e\u0447 \u0441\u043e\u043e\u0431\u0449\u0430\u0435\u0442 \u0432\u0430\u043c, \u043a\u0430\u043a \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435, \u0438 \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u00ab\u043e\u0431\u0449\u0435\u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u043c\u00bb, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043b\u044e\u0431\u043e\u0439 \u043c\u043e\u0436\u0435\u0442 \u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c. <\/li>\n<\/ul>\n<p>  <\/p>\n<ul>\n<li> \u0414\u0440\u0443\u0433\u043e\u0439 \u043a\u043b\u044e\u0447 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435. \u042d\u0442\u043e\u0442 \u043a\u043e\u0434 \u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0432 \u0441\u0435\u043a\u0440\u0435\u0442\u0435, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0435\u043b\u043e\u0432\u0435\u043a, \u0437\u043d\u0430\u044e\u0449\u0438\u0439 \u043a\u043b\u044e\u0447, \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435. <\/li>\n<\/ul>\n<p>  <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/0f\/cm\/hv\/0fcmhvnoq68x7sxrh74dxywgtvo.jpeg\" width=\"90\" height=\"95\" align=\"right\"\/>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438\u043c\u0435\u044e\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a\u0443: \u043a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043a\u043b\u044e\u0447\u0435\u0439 \u043c\u043e\u0436\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u043a \u0434\u043b\u044f \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f \u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<\/p>\n<p>  \u0425\u043e\u0442\u044f \u044d\u0442\u043e \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043c\u0430\u043b\u043e\u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c, \u0435\u0441\u043b\u0438 \u0432\u044b \u043f\u044b\u0442\u0430\u0435\u0442\u0435\u0441\u044c \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u0432 \u0441\u0435\u043a\u0440\u0435\u0442\u0435!  <\/div>\n<\/p><\/div>\n<p>  <b>\u041f\u0435\u0440\u0432\u044b\u0439 \u043e\u0431\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0440\u0430\u043d\u0446\u0430. <\/b><\/p>\n<p>  \u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0441\u0438\u0441\u0442\u0435\u043c \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c (\u0438 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c) \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u043d\u0443\u0436\u043d\u044b \u0434\u0432\u0430 \u043a\u043b\u044e\u0447\u0430. \u00ab\u041b\u0435\u0433\u0430\u043b\u044c\u043d\u044b\u0439\u00bb \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u0435\u043b\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u0435\u0442 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u043a\u043b\u044e\u0447 <math>$inline$\u0410$inline$<\/math>, \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u0435\u043b\u044c \u0436\u0435 \u0432\u043b\u0430\u0434\u0435\u0435\u0442 \u0434\u0440\u0443\u0433\u0438\u043c \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c <math>$inline$B$inline$<\/math>. <\/p>\n<p>  <i>\u0427\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c, \u0435\u0441\u043b\u0438 \u0437\u043b\u043e\u0443\u043c\u044b\u0448\u043b\u0435\u043d\u043d\u0438\u043a\u0443 \u0441\u0442\u0430\u043b \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447?<\/i><\/p>\n<p>  \u0415\u0441\u0442\u044c \u043e\u0442\u0432\u0435\u0442: \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c\u0441\u044f \u0438\u0437 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u043f\u0440\u0438 \u043f\u043e\u043c\u043e\u0449\u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f (<i> \u043e\u0434\u043d\u043e\u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0435\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/i>) <math>$inline$f$inline$<\/math>, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0435\u0433\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c\u0438 \u0434\u0432\u0443\u043c\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438:<\/p>\n<ul>\n<li><math>$inline$B = f(A)$inline$<\/math>, \u0437\u043d\u0430\u044f A, \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0441\u0430\u043c\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043b\u0435\u0433\u043a\u043e <\/li>\n<\/ul>\n<p>  <\/p>\n<ul>\n<li><i><b><math>$inline$A = f^{-1} (B)$inline$<\/math><\/b><\/i>, \u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0442\u0440\u0443\u0434\u043d\u043e<\/li>\n<\/ul>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/n6\/hs\/dm\/n6hsdmfusvd4zx3hxuxjswzbqm8.png\" width=\"400\" height=\"400\" \/><\/div>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u00ab\u043b\u0435\u0433\u043a\u043e\u00bb \u0438 \u00ab\u0442\u0440\u0443\u0434\u043d\u043e\u00bb?<\/b>                         <\/p>\n<div class=\"spoiler_text\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447.<br \/>  \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u043e \u0442\u0435\u0440\u043c\u0438\u043d <u>\u00ab\u043b\u0435\u0433\u043a\u043e\u00bb<\/u> \u043e\u0431\u044b\u0447\u043d\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u0442 \u0434\u043b\u0438\u043d\u044b \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f. \u0422.\u0435. \u043f\u0443\u0441\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 <math>$inline$n$inline$<\/math> \u0431\u0438\u0442\u043e\u0432, \u0442\u043e\u0433\u0434\u0430 \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u2014 <math>$inline$t \\propto n^a$inline$<\/math>, \u0433\u0434\u0435 <math>$inline$a $inline$<\/math> \u2014 \u0437\u0430\u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430. \u0411\u0443\u0434\u0435\u043c \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0437 \u043a\u043b\u0430\u0441\u0441\u0430 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0420. <\/p>\n<p>  \u0422\u0435\u0440\u043c\u0438\u043d <u>\u00ab\u0442\u0440\u0443\u0434\u043d\u043e\u00bb<\/u> \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c. \u0412 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443, \u0435\u0441\u043b\u0438 \u0443\u0441\u0438\u043b\u0438\u044f \u0434\u043b\u044f \u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043e\u0442 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f. <\/p>\n<p>  \u0422.\u0435. \u043f\u0443\u0441\u0442\u044c \u0432\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 <math>$inline$n$inline$<\/math> \u0431\u0438\u0442\u043e\u0432, \u0438 \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <math>$inline$t \\propto 2n$inline$<\/math>, \u0442\u043e \u0431\u0443\u0434\u0435\u043c \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430. <\/p><\/div>\n<\/p><\/div>\n<p>  <\/p>\n<h2>\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0442\u0430\u043a<\/h2>\n<p>  \u0417\u0430\u0434\u0430\u043d \u043d\u0430\u0431\u043e\u0440 (\u0440\u044e\u043a\u0437\u0430\u0447\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440) <math>$inline$A = (a_1, &#8230; , a_n) $inline$<\/math> \u2014 \u044d\u0442\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0438\u0437 <math>$inline$n$inline$<\/math> (<math>$inline$n &gt; 2), $inline$<\/math> \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <math>$inline$a_i$inline$<\/math>. \u041f\u0443\u0441\u0442\u044c \u0435\u0441\u0442\u044c \u0447\u0438\u0441\u043b\u043e <math>$inline$k$inline$<\/math> \u2014 \u0446\u0435\u043b\u043e\u0435 \u0438 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435. \u0417\u0430\u0434\u0430\u0447\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 <math>$inline$a_i$inline$<\/math>, \u0447\u0442\u043e\u0431\u044b \u0432 \u0441\u0443\u043c\u043c\u0435 \u043e\u043d\u0438 \u0434\u0430\u0432\u0430\u043b\u0438 \u0440\u043e\u0432\u043d\u043e <math>$inline$k$inline$<\/math>.<\/p>\n<p>  \u0412 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u044f\u0441\u043d\u0438\u0442\u044c, \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u043b\u0438 \u0434\u0430\u043d\u043d\u0430\u044f \u043f\u0430\u0440\u0430 <math>$inline$(A , k)$inline$<\/math> \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c. \u0412 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u043c \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u043d\u0443\u0436\u043d\u043e \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0432\u0445\u043e\u0434\u0430 <math>$inline$(A , k)$inline$<\/math> \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0437\u043d\u0430\u044f, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442. \u041e\u0431\u0430 \u044d\u0442\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f <a href=\"https:\/\/ru.wikipedia.org\/wiki\/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0\"> NP-\u043f\u043e\u043b\u043d\u044b\u043c\u0438.<\/a><\/p>\n<h2>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u044f \u0441 \u0440\u044e\u043a\u0437\u0430\u043a\u043e\u043c<\/h2>\n<p>  \u0412 \u0441\u0430\u043c\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <math>$inline$k$inline$<\/math> \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 (\u0432\u043c\u0435\u0441\u0442\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c) \u0440\u044e\u043a\u0437\u0430\u043a\u0430, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0438\u0437 \u0447\u0438\u0441\u0435\u043b <math>$inline$a_i$inline$<\/math> \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 (\u0432\u0435\u0441) \u043f\u0440\u0435\u0434\u043c\u0435\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d \u0432 \u0440\u044e\u043a\u0437\u0430\u043a. \u0417\u0430\u0434\u0430\u0447\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043f\u0440\u0435\u0434\u043c\u0435\u0442\u043e\u0432, \u0447\u0442\u043e\u0431\u044b<br \/>  \u0440\u044e\u043a\u0437\u0430\u043a \u0431\u044b\u043b \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d.<\/p>\n<p>  \u0422.\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u044c\u0442\u0435, \u0447\u0442\u043e \u0443 \u0432\u0430\u0441 \u0435\u0441\u0442\u044c \u043d\u0430\u0431\u043e\u0440 \u0433\u0438\u0440\u044c 1, 6, 8, 15 \u0438 24, \u0432\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u0442\u044c \u0440\u044e\u043a\u0437\u0430\u043a \u0432\u0435\u0441\u043e\u043c 30.<\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/c8\/yk\/xj\/c8ykxjgyfsh4aqnjn5hv7h5zqny.png\" \/><\/div>\n<p>  \u0412 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 <math>$inline$\u0410$inline$<\/math> \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439, \u043a\u0430\u043a\u0430\u044f \u0438\u0437 \u0438\u0445 \u0441\u0443\u043c\u043c \u0440\u0430\u0432\u043d\u0430 <math>$inline$k$inline$<\/math>. \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u044d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 <math>$inline$2^5 = 32$inline$<\/math> \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 (\u0432\u043a\u043b\u044e\u0447\u0430\u044f \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0438 \u043f\u0443\u0441\u0442\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e). \u042d\u0442\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0438\u043c\u043e.<\/p>\n<p>  <i>\u041d\u043e \u0447\u0442\u043e \u0431\u0443\u0434\u0435\u0442, \u0435\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0442\u0435\u043d \u0447\u0438\u0441\u0435\u043b <math>$inline$a_i$inline$<\/math>? <\/i><br \/>  \u0412 \u043d\u0430\u0448\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 n = 5, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0443\u0441\u043b\u043e\u0436\u043d\u044f\u0442\u044c \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435. \u0412 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445 \u043fp\u0438\u043c\u0435\u0440 \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c, \u0441\u043a\u0430\u0436\u0435\u043c, 300 <math>$inline$a_i-\u0445$inline$<\/math>. \u0421\u0443\u0442\u044c \u0437\u0434\u0435\u0441\u044c \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0438\u043c\u0435\u044e\u0449\u0438\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u0441p\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 \u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c. \u041f\u043e\u0438\u0441\u043a \u0441\u0440\u0435\u0434\u0438 <math>$inline$2^{300}$inline$<\/math> \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043d\u0435 \u043f\u043e\u0434\u0434\u0430\u0435\u0442\u0441\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435. \u0412 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430 \u043a\u0430\u043a <a href=\"https:\/\/ru.wikipedia.org\/wiki\/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0\"> NP-\u043f\u043e\u043b\u043d\u0430\u044f<\/a>\u2026 NP-\u043f\u043e\u043b\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u0442\u0440\u0443\u0434\u043d\u043e\u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043c\u044b\u0435.<\/p>\n<p>  <b>\u041f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043b\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0434 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f?<\/b><\/p>\n<p>  \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e <math>$inline$f(x)$inline$<\/math> \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c. \u041b\u044e\u0431\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <math>$inline$0 \u2264 x \u2264 2n \u2212 1$inline$<\/math> \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0437\u0430\u0434\u0430\u043d\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0438\u0437 <math>$inline$n$inline$<\/math> p\u0430\u0437p\u044f\u0434\u043e\u0432, \u0433\u0434\u0435 \u043fp\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u043d\u0443\u043b\u0438. \u0422\u0435\u043f\u0435\u0440\u044c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c <math>$inline$ f(x)$inline$<\/math> \u043a\u0430\u043a \u0447\u0438\u0441\u043b\u043e, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c\u043e\u0435 \u0438\u0437 <math>$inline$A$inline$<\/math> \u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0432\u0441\u0435\u0445 \u0442\u0430\u043a\u0438\u0445 <math>$inline$a_i$inline$<\/math>, \u0447\u0442\u043e \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 p\u0430\u0437p\u044f\u0434 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 <math>$inline$x$inline$<\/math> \u0440\u0430\u0432\u0435\u043d 1. <\/p>\n<p>  \u0422.\u0435.  <\/p>\n<p><math>$$display$$f(1) = f(0 . . . 001) = a_n$$display$$<\/math><\/p>\n<p>  <\/p>\n<p><math>$$display$$f(2) = f(0 . . . 010) = a_{n\u22121}$$display$$<\/math><\/p>\n<p>  <\/p>\n<p><math>$$display$$f(3) = f(0 . . . 011) = a_{n\u22121} + a_n$$display$$<\/math><\/p>\n<p>  <\/p>\n<p><math>$$display$$&#8230;$$display$$<\/math><\/p>\n<p>  \u0424\u0443\u043d\u043a\u0446\u0438\u044f <math>$inline$f(\u0445 )$inline$<\/math> \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u043b\u0430\u0441\u044c <math>$inline$n-$inline$<\/math> \u043d\u0430\u0431\u043e\u0440\u043e\u043c <math>$inline$ A$inline$<\/math>. \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u043c\u044b \u0432 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c <math>$inline$x$inline$<\/math> \u0438\u0437 <math>$inline$f(x)$inline$<\/math>, \u0442\u043e \u043fp\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0437\u0430 \u0442\u043e \u0436\u0435 \u0432\u0440\u0435\u043c\u044f \u0431\u0443\u0434\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435: \u043f\u043e <math>$inline$x$inline$<\/math> \u043d\u0435\u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0435\u0433\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0434\u0430\u0435\u0442 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u044b \u043d\u0430\u0431\u043e\u0440\u0430 <math>$inline$A$inline$<\/math>, \u0432\u0445\u043e\u0434\u044f\u0449\u0438\u0435 \u0432 \u0441\u0443\u043c\u043c\u0443 \u0434\u043b\u044f <math>$inline$f(x)$inline$<\/math>. \u0421 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 <math>$inline$f(x)$inline$<\/math> \u0438\u0437 <math>$inline$x$inline$<\/math> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0435\u0433\u043a\u0438\u043c. \u0422\u0430\u043a \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 NP-\u043f\u043e\u043b\u043d\u0430, <math>$inline$f(x)$inline$<\/math> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0445\u043e\u0440\u043e\u0448\u0438\u043c \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u043c \u0434\u043b\u044f \u043e\u0434\u043d\u043e\u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0435\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. <b>\u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043d\u0430\u0434\u043e \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b <math>$inline$n$inline$<\/math> \u0431\u044b\u043b\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c, \u0441\u043a\u0430\u0436\u0435\u043c, \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 <math>$inline$200$inline$<\/math>.<\/b><\/p>\n<h2>\u0428\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h2>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0442\u0435\u043a\u0441\u0442<\/b>                         <\/p>\n<div class=\"spoiler_text\">\u041e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0442\u0435\u043a\u0441\u0442 (\u0430\u043d\u0433\u043b. plain text) \u2014 \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0442\u0435\u043a\u0441\u0442, \u043f\u043e\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u0439 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044e, \u043b\u0438\u0431\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0438\u0439\u0441\u044f \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u0438. \u041c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043d \u0431\u0435\u0437 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 (\u0431\u0435\u0437 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u0438).  <\/div>\n<\/p><\/div>\n<p>  \u0428\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u043c\u043e\u0436\u043d\u043e \u0434\u0432\u0443\u043c\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438:<\/p>\n<ol>\n<li> \u0428\u0438\u0444\u0440 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u0432\u043e\u0437\u0432\u0435\u0441\u0442\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u044e\u043a\u0437\u0430\u0447\u043d\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0438\u043c \u0431\u0438\u0442 \u0448\u0438\u0444\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0438 \u0434\u0430\u043b\u0435\u0435 \u043f\u0435\u0440\u0435\u043c\u043d\u043e\u0436\u0438\u0442\u044c \u0432\u0441\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b, \u0442\u043e \u0435\u0441\u0442\u044c \u0435\u0441\u043b\u0438 <math>$inline$A = (2,3,5)$inline$<\/math>, \u0430 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 <math>$inline$(100)$inline$<\/math>, \u0442\u043e \u0448\u0438\u0444\u0440\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0447\u0438\u0441\u043b\u043e <math>$inline$2^1*3^0*5^0=2$inline$<\/math>. \u042d\u0442\u043e <u>\u043c\u0443\u043b\u044c\u0442\u0438\u043f\u043b\u0438\u043a\u0430\u0442\u0438\u0432\u043d\u044b\u043c<\/u> \u0441\u043f\u043e\u0441\u043e\u0431.<\/li>\n<li>\u0428\u0438\u0444\u0440 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u0443\u043c\u043d\u043e\u0436\u0438\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u044e\u043a\u0437\u0430\u0447\u043d\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u043d\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0438\u043c \u0431\u0438\u0442\u044b \u0448\u0438\u0444\u0440\u0443\u0435\u043c\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0438 \u0434\u0430\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0443\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b, \u0442\u043e \u0435\u0441\u0442\u044c \u0435\u0441\u043b\u0438 <math>$inline$A = (2,3,5)$inline$<\/math>, \u0430 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435 <math>$inline$(100)$inline$<\/math>, \u0442\u043e \u0448\u0438\u0444\u0440\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0447\u0438\u0441\u043b\u043e <math>$inline$2^ *1+3^ *0+5^ *0= 2$inline$<\/math>. \u0422\u0430\u043a\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 <u>\u0430\u0434\u0434\u0438\u0442\u0438\u0432\u043d\u044b\u043c<\/u>.  <\/li>\n<\/ol>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440<\/b><\/p>\n<p>  \u0414\u043b\u044f \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0442\u043a\u0440\u044b\u0442\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0435\u0433\u043e \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u044e\u0442 \u043d\u0430 \u0431\u043b\u043e\u043a\u0438 \u0434\u043b\u0438\u043d\u044b <math>$inline$n$inline$<\/math> (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0412\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0435\u0441 30 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c 11110). \u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0435\u0434\u0438\u043d\u0438\u0446\u0430 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043f\u0440\u0435\u0434\u043c\u0435\u0442\u0430 \u0432 \u0440\u044e\u043a\u0437\u0430\u043a\u0435, \u0430 \u043d\u043e\u043b\u044c \u043d\u0430 \u0435\u0433\u043e \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435. <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/xm\/ep\/bx\/xmepbxtqw31kxvocfdklhrkkrbu.png\" \/><\/div>\n<p>  \u0428\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0440\u044e\u043a\u0437\u0430\u043a\u0430 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043a \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044e \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u0438 \u0437\u0430\u043a\u0440\u044b\u0442\u044b\u0445 \u043a\u043b\u044e\u0447\u0435\u0439, \u0433\u0434\u0435 \u0437\u0430\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 \u043f\u0440\u043e\u0441\u0442 \u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438, \u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 \u0442\u0440\u0443\u0434\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c.<br \/>  \u0422\u0430\u043a, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u0438\u0441\u0442\u0435\u043c\u0443, \u0433\u0434\u0435: <\/p>\n<p>  <u>\u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c<\/u> \u0431\u0443\u0434\u0435\u0442 \u0441\u043b\u0443\u0436\u0438\u0442\u044c \u00ab\u0442\u0440\u0443\u0434\u043d\u0430\u044f\u00bb \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430, \u0442.\u043a. \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043d\u0435\u0451 \u043c\u043e\u0436\u043d\u043e \u043b\u0435\u0433\u043a\u043e \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0438 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435. <\/p>\n<p>  <u>\u0437\u0430\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c<\/u> \u2014 \u0431\u0443\u0434\u0435\u0442 \u0436\u0435 \u0441\u043b\u0443\u0436\u0438\u0442\u044c \u00ab\u043b\u0451\u0433\u043a\u0430\u044f\u00bb \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430, \u0442.\u043a. \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043d\u0435\u0451 \u043c\u043e\u0436\u043d\u043e \u043b\u0435\u0433\u043a\u043e \u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0435. \u0411\u0435\u0437 \u0437\u0430\u043a\u0440\u044b\u0442\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u043f\u0440\u0438\u0434\u0451\u0442\u0441\u044f \u0440\u0435\u0448\u0430\u0442\u044c \u00ab\u0442\u0440\u0443\u0434\u043d\u0443\u044e\u00bb \u0437\u0430\u0434\u0430\u0447\u0443 \u0440\u044e\u043a\u0437\u0430\u043a\u0430.<\/p>\n<h2>\u00ab\u041b\u0451\u0433\u043a\u0430\u044f\u00bb \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430<\/h2>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0421\u0432\u0435\u0440\u0445\u0440\u0430\u0441\u0442\u0443\u0449\u0438\u0439 \u0440\u044e\u043a\u0437\u0430\u0447\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440<\/b>                         <\/p>\n<div class=\"spoiler_text\">\u0420\u044e\u043a\u0437\u0430\u0447\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 <math>$inline$A=(a_{1},&#8230;,a_{n})$inline$<\/math> \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <u>\u0441\u0432\u0435\u0440\u0445\u0440\u0430\u0441\u0442\u0443\u0449\u0438\u043c<\/u>, \u0435\u0441\u043b\u0438 <math>$inline$\u03a3_{i=1}^{j-1} a_{i} &lt; a_{j}$inline$<\/math> \u0434\u043b\u044f <math>$inline$j=2,&#8230;,n$inline$<\/math>, \u0442.\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0447\u043b\u0435\u043d \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u0443\u043c\u043c\u044b \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445.  <\/div>\n<\/p><\/div>\n<p>  \u0414\u043b\u044f \u0441\u0432\u0435\u0440\u0445\u0440\u0430\u0441\u0442\u0443\u0449\u0438\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0391 \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u043b\u0435\u0433\u043a\u043e \u0440\u0435\u0448\u0430\u0435\u043c\u0430. \u0422.\u0435. \u0440\u044e\u043a\u0437\u0430\u043a \u0441\u043e\u0431\u0440\u0430\u0442\u044c \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e. <br \/>  <b>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435:<\/b><\/p>\n<div style=\"text-align:center;\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/r6\/to\/pe\/r6topeyq9solkcl55t7vsdlw2j8.png\" width=\"500\" height=\"1000\" \/><\/div>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<ol>\n<li> \u041e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u0440\u0430\u043d\u0446\u0430 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0432\u0435\u0441\u043e\u043c \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. <br \/>  \u0415\u0441\u043b\u0438 \u043e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u043c\u0435\u043d\u044c\u0448\u0435 \u0447\u0438\u0441\u043b\u0430, \u0437\u043d\u0430\u0447\u0438\u0442, \u0432 \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0435\u0433\u043e \u043d\u0435\u0442. \u0415\u0441\u043b\u0438 \u043e\u0431\u0449\u0438\u0439 \u0432\u0435\u0441 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0438\u0441\u043b\u0430, \u043e\u043d \u0432 \u0440\u044e\u043a\u0437\u0430\u043a\u0435. <\/li>\n<li>\u0412\u044b\u0447\u0435\u0441\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0438\u0437 \u043e\u0431\u0449\u0435\u0439 \u0441\u0443\u043c\u043c\u044b \u0438 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u0435 \u0441\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043f\u043e \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0435 \u0447\u0438\u0441\u043b\u043e\u043c. <\/li>\n<li>\u041f\u043e\u0432\u0442\u043e\u0440\u0438\u0442\u044c (1)-(2) \u043f\u043e\u043a\u0430 \u043e\u0431\u0449\u0430\u044f \u0441\u0443\u043c\u043c\u0430 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u043d\u0435\u0442 \u043d\u0443\u043b\u044f. <br \/>  \u0415\u0441\u043b\u0438 \u0441\u0443\u043c\u043c\u0430 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043d\u0443\u043b\u044f, \u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0435\u0442. <\/li>\n<\/ol>\n<\/div><\/div>\n<p>  <\/p>\n<h2>\u00ab\u0422\u0440\u0443\u0434\u043d\u0430\u044f\u00bb \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430<\/h2>\n<p>  \u0420\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043e <u>\u043d\u0435\u0441\u0432\u0435\u0440\u0445\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0435\u043c\u0441\u044f<\/u> \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435. <br \/>  \u041e\u0434\u0438\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0441\u0432\u0435\u0440\u0445\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u0440\u044e\u043a\u0437\u0430\u043a \u0434\u043b\u044f \u0447\u0430\u0441\u0442\u043d\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u0438 \u043d\u0435\u0441\u0432\u0435\u0440\u0445\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0439\u0441\u044f \u0440\u044e\u043a\u0437\u0430\u043a \u0434\u043b\u044f \u043e\u0442\u043a\u0440\u044b\u0442\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430, \u0431\u044b\u043b \u0441\u043e\u0437\u0434\u0430\u043d \u041c\u0435\u0440\u043a\u043b\u043e\u043c \u0438 \u0425\u0435\u043b\u043b\u043c\u0430\u043d\u043e\u043c. <br \/>  \u041e\u043d\u0438 \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u044d\u0442\u043e, \u0432\u0437\u044f\u0432 \u0437\u0430\u0434\u0430\u0447\u0443 \u0441\u0432\u0435\u0440\u0445\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u0440\u044e\u043a\u0437\u0430\u043a\u0430 \u0438 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0432 \u0435\u0435 \u0432 \u043d\u0435\u0441\u0432\u0435\u0440\u0445\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443.<br \/>  (\u041c\u0435\u0440\u043a\u043b \u0438 \u0425\u0435\u043b\u043b\u043c\u0430\u043d, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043c\u043e\u0434\u0443\u043b\u044c\u043d\u0443\u044e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443, \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 \u0441\u043f\u043e\u0441\u043e\u0431 \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u00ab\u043b\u0451\u0433\u043a\u043e\u0433\u043e\u00bb \u0440\u044e\u043a\u0437\u0430\u043a\u0430 \u0432 \u00ab\u0442\u0440\u0443\u0434\u043d\u044b\u0439\u00bb)<\/p>\n<p>  <b>\u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043e\u0442\u043a\u0440\u044b\u0442\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430<\/b><\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u0430\u0436\u043d\u044b\u0445 \u043f\u043e\u043d\u044f\u0442\u0438\u0439<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<ul>\n<li> \u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c <math>$inline$(x, mod m)$inline$<\/math> <u>\u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u0439 \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043e\u0441\u0442\u0430\u0442\u043e\u043a<\/u> \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f <math>$inline$x$inline$<\/math> \u043d\u0430 <math>$inline$m$inline$<\/math>,<br \/>   \u0433\u0434\u0435 <math>$inline$x$inline$<\/math> \u2014 \u0446\u0435\u043b\u044b\u0435, <math>$inline$m &gt; 1$inline$<\/math>, [x\/m] \u2014 \u0446\u0435\u043b\u0430\u044f \u0447\u0430\u0441\u0442\u044c,\n<p><math>$$display$$x = (x, mod m) + [x\/m]*m$$display$$<\/math><\/p>\n<\/li>\n<\/ul>\n<p>  <\/p>\n<ul>\n<li><u>\u041c\u043e\u0434\u0443\u043b\u044c\u043d\u043e\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435<\/u><br \/>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0440\u044e\u043a\u0437\u0430\u0447\u043d\u044b\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 <math>$inline$A$inline$<\/math>, \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <math>$inline$m &gt; max A$inline$<\/math> \u0438 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 <math>$inline$t &lt; m$inline$<\/math> \u0442\u0430\u043a\u043e\u0435, \u0447\u0442\u043e \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c <math>$inline$(t, m) = 1$inline$<\/math>. <br \/>  \u0415\u0441\u043b\u0438 <math>$inline$B = (b_1, . . . , b_n)$inline$<\/math> \u0442\u0430\u043a\u043e\u0439 \u0432\u0435\u043a\u0442\u043e\u0440, \u0447\u0442\u043e <math>$inline$b_i = (ta_i, modm)$inline$<\/math>, \u0434\u043b\u044f <math>$inline$i = 1, . . . , n$inline$<\/math>, \u0442\u043e \u0433\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e \u0432\u0435\u043a\u0442\u043e\u0440 B \u043f\u043e\u043b\u0443\u0447\u0435\u043d \u0438\u0437 A \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043c\u043e\u0434\u0443\u043b\u044c\u043d\u043e\u0433\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u043e\u0434\u0443\u043b\u044f m \u0438 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044f t \u0438\u043b\u0438, \u043a\u043e\u0440\u043e\u0447\u0435, \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0430\u0440\u044b <math>$inline$(m, t)$inline$<\/math>.<br \/>   \u0423\u0441\u043b\u043e\u0432\u0438\u0435 <math>$inline$(t, m) = 1$inline$<\/math> \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0435 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0433\u043e<br \/>  \u0447\u0438\u0441\u043b\u0430 <math>$inline$t^{\u22121} = u$inline$<\/math>, \u0442\u0430\u043a\u043e\u0433\u043e, \u0447\u0442\u043e<br \/> \n<p><math>$$display$$tu \u2261 1 (mod m)$$display$$<\/math><\/p>\n<p>  \u0438 <math>$inline$1 \u2264 u &lt; m$inline$<\/math>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0442\u0430\u043a\u0436\u0435 \u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u043e <math>$inline$A $inline$<\/math>\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0438\u0437 <math>$inline$B$inline$<\/math><br \/>  \u043c\u043e\u0434\u0443\u043b\u044c\u043d\u044b\u043c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <math>$inline$m, u$inline$<\/math>. <\/li>\n<\/ul>\n<p>  <\/p>\n<ul>\n<li> \u0415\u0441\u043b\u0438 \u0432\u044b\u0448\u0435\u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 <math>$inline$m &gt; max A$inline$<\/math> \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u0441\u0438\u043b\u044c\u043d\u044b\u043c<br \/>  \u0443\u0441\u043b\u043e\u0432\u0438\u0435\u043c <math>$inline$m &gt; \u03a3_{i=1}^{n} a_{i} $inline$<\/math>, \u0442\u043e \u0433\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e <math>$inline$B$inline$<\/math> \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0438\u0437 <math>$inline$A$inline$<\/math> <u>\u0441\u0438\u043b\u044c\u043d\u044b\u043c \u043c\u043e\u0434\u0443\u043b\u044c\u043d\u044b\u043c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435\u043c<\/u> \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <math>$inline$m, t$inline$<\/math>.<\/li>\n<\/ul>\n<p>  <\/p>\n<ul>\n<li><u>\u041a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u0430<\/u> \u2014 \u044d\u0442\u043e \u0437\u0430\u0432\u0435\u0440\u0448\u0451\u043d\u043d\u0430\u044f \u043a\u043e\u043c\u043f\u043b\u0435\u043a\u0441\u043d\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u0430\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0434\u0432\u0443\u0441\u0442\u043e\u0440\u043e\u043d\u043d\u0438\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430\u0434 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0431\u044a\u0451\u043c\u0430 \u0438 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043e\u0442\u043f\u0440\u0430\u0432\u043a\u0438 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0430\u044f \u043c\u0435\u0445\u0430\u043d\u0438\u0437\u043c\u043e\u043c \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0430\u0440\u043e\u043b\u0435\u0439, \u043a\u043b\u044e\u0447\u0435\u0439 \u0438 \u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043d\u043e\u0433\u043e \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. <\/li>\n<\/ul>\n<p>  <\/div>\n<\/p><\/div>\n<p>  \u0421\u043e\u0437\u0434\u0430\u0442\u0435\u043b\u044c \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442 \u0442\u0430\u043a\u0443\u044e \u0441\u0438\u0441\u0442\u0435\u043c\u0443 <math>$inline$A, t, m, B$inline$<\/math>, \u0447\u0442\u043e \u0432\u0435\u043a\u0442\u043e\u0440 <math>$inline$A$inline$<\/math> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0432\u0435\u0440\u0445\u0440\u0430\u0441\u0442\u0443\u0449\u0438\u043c, \u0430 <math>$inline$B$inline$<\/math> \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0438\u0437 <math>$inline$A$inline$<\/math> \u0441\u0438\u043b\u044c\u043d\u044b\u043c \u043c\u043e\u0434\u0443\u043b\u044c\u043d\u044b\u043c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <math>$inline$m, t$inline$<\/math>. \u0412\u0435\u043a\u0442\u043e\u0440 <math>$inline$B$inline$<\/math> \u0440\u0430\u0441\u043a\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043a\u043b\u044e\u0447 \u0437\u0430\u0448\u0438\u0444p\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435 \u0431\u043b\u043e\u043a\u0438 \u0434\u043b\u0438\u043d\u044b <math>$inline$n$inline$<\/math> \u043f\u043e\u0441\u044b\u043b\u0430\u044e\u0442\u0441\u044f \u043a \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0443 \u043a\u0430\u043a \u0447\u0438\u0441\u043b\u0430 <math>$inline$\u03b2$inline$<\/math>, \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0432\u0435\u043a\u0442\u043e\u0440\u0430 <math>$inline$B$inline$<\/math>. <\/p>\n<p>  \u041f\u0435\u0440\u0435\u0445\u0432\u0430\u0442\u0447\u0438\u043a \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u0439 \u0434\u043e\u043b\u0436\u0435\u043d \u0440\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0434\u043b\u044f \u0432\u0445\u043e\u0434\u0430 <math>$inline$(B, \u03b2)$inline$<\/math>. \u0421\u043e\u0437\u0434\u0430\u0442\u0435\u043b\u044c \u0436\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 <math>$inline$\u03b1 = (u\u03b2, modm)$inline$<\/math><br \/>  \u0438 \u0440\u0435\u0448\u0430\u0435\u0442 \u0437\u0430\u0434\u0430\u0447\u0443 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u0434\u043b\u044f \u0432\u0445\u043e\u0434\u0430 <math>$inline$(A, \u03b1)$inline$<\/math>. \u041f\u043e\u0447\u0435\u043c\u0443 \u0432\u0441\u0435 \u044d\u0442\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442,<br \/>  \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u043b\u0435\u043c\u043c\u0430.<\/p>\n<p>  <b>\u041b\u0435\u043c\u043c\u0430<\/b>. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e <math>$inline$A = (a_1, . . . , a_n) $inline$<\/math>\u0441\u0432\u0435\u0440\u0445\u0440\u0430\u0441\u0442\u0443\u0449\u0438\u0439 \u0432\u0435\u043a\u0442\u043e\u0440 \u0438 \u0432\u0435\u043a\u0442\u043e\u0440 <math>$inline$B$inline$<\/math> \u043f\u043e\u043b\u0443\u0447\u0435\u043d \u0438\u0437 <math>$inline$ A$inline$<\/math> \u0441\u0438\u043b\u044c\u043d\u044b\u043c \u043c\u043e\u0434\u0443\u043b\u044c\u043d\u044b\u043c \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435\u043c \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <math>$inline$m, t$inline$<\/math>. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c \u0434\u0430\u043b\u0435\u0435, \u0447\u0442\u043e <math>$inline$u \u2261 t^{\u22121} (mod m)$inline$<\/math>, <math>$inline$\u03b2$inline$<\/math> \u2014\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0438 <math>$inline$\u03b1 = (u\u03b2,modm)$inline$<\/math>. \u0422\u043e\u0433\u0434\u0430 \u0441\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u044f.<\/p>\n<p>  (i) \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 <math>$inline$(A, \u03b1)$inline$<\/math> \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c\u0430 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0415\u0441\u043b\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043e\u043d\u043e \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e.<br \/>  (ii) \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 <math>$inline$(B, \u03b2)$inline$<\/math> \u0438\u043c\u0435\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f. <br \/>  (iii) \u0415\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0445\u043e\u0434\u0430 <math>$inline$(B, \u03b2)$inline$<\/math>, \u0442\u043e \u043e\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0434\u043b\u044f \u0432\u0445\u043e\u0434\u0430 <math>$inline$(A, \u03b1)$inline$<\/math>.<br \/>  <a href=\"http:\/\/web.archive.org\/web\/20111119210028\/http:\/\/www.ssl.stu.neva.ru\/psw\/crypto\/open_key_crypt.pdf\"> \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u0441\u0442\u0432\u043e(\u0441\u0442\u0440. 104)<\/a> <\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440<\/b><\/p>\n<p>  \u0412\u043e\u0437\u043c\u0451\u043c \u0441\u0432\u0435\u0440\u0445\u0440\u0430\u0441\u0442\u0443\u0449\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c; \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, {1, 2, 4, 10, 20, 40}. \u041c\u043e\u0434\u0443\u043b\u044c \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u0441\u0443\u043c\u043c\u044b \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 110. \u041c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044c \u043d\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u0438\u043c\u0435\u0442\u044c \u043e\u0431\u0449\u0438\u0445 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u0439 \u0441 \u043c\u043e\u0434\u0443\u043b\u0435\u043c. \u0418\u0442\u0430\u043a, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u044b\u0431\u0435\u0440\u0435\u043c 31. <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ud\/qp\/hb\/udqphbqmzkzd3rr2woq5crxcqju.png\" \/><\/div>\n<p>  \u0418\u0442\u0430\u043a, \u043c\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043b\u0438 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447: {31, 62, 14, 90, 70, 30} \u0438 \u0437\u0430\u043a\u0440\u044b\u0442\u044b\u0439 \u043a\u043b\u044e\u0447 \u2014 {1, 2, 4, 10, 20.40}.<\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u044c \u0434\u0432\u043e\u0438\u0447\u043d\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c: 100100111100101110 <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/a0\/pq\/6s\/a0pq6suktiryif3rwlhmrmhhzey.png\" \/><\/div>\n<p>  <\/p>\n<h2>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u0430 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0445 \u043a\u043b\u044e\u0447\u0435\u0439<\/h2>\n<p>  <\/p>\n<ul>\n<li> \u041f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u043e\u0431\u0435 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f, \u043e\u043d\u0438 \u0434\u0430\u0436\u0435 \u043c\u043e\u0433\u0443\u0442 \u043d\u0435 \u0437\u043d\u0430\u0442\u044c \u0434\u0440\u0443\u0433 \u0434\u0440\u0443\u0433\u0430 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043b\u044e\u0431\u044b\u0435 \u0432\u0438\u0434\u044b \u0441\u0432\u044f\u0437\u0438. <\/li>\n<\/ul>\n<p>  <\/p>\n<ul>\n<li> \u0414\u043b\u0438\u043d\u0430 \u043a\u043b\u044e\u0447\u0430. \u0412 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u0435\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u0434\u043b\u0438\u043d\u043d\u0435\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f, \u043d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430 \u043d\u0435 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442\u0441\u044f. \u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c, \u0442\u043e \u0443 \u043d\u0438\u0445 \u0434\u043b\u0438\u043d\u0430 \u043a\u043b\u044e\u0447\u0430 \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043e\u043d \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u0439 \u0438 \u043e\u0431\u0449\u0435\u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0439. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0438 \u0434\u043b\u0438\u043d\u0430 \u043a\u043b\u044e\u0447\u0430 \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435 \u0442\u0430\u043a \u0432\u0430\u0436\u043d\u0430 (\u043f\u043e\u043b\u0443\u0447\u0430\u0442\u0435\u043b\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0445\u0440\u0430\u043d\u0438\u0442 \u0435\u0433\u043e \u0432 \u0441\u0435\u043a\u0440\u0435\u0442\u043d\u043e\u043c \u043c\u0435\u0441\u0442\u0435)<\/li>\n<\/ul>\n<h2>\u0418\u0441\u0442\u043e\u0440\u0438\u044f<\/h2>\n<p>  <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/n7\/ex\/tl\/n7extllu-5fhmm7os4hx5agcktq.png\" width=\"120\" height=\"120\" align=\"right\"\/> \u0414\u043e\u043b\u0433\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u043d\u0446\u0435\u0432\u044b\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u043b\u0438\u0441\u044c \u043a\u0430\u043a \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0438 \u043f\u0435\u0440\u0441\u043f\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0438\u0445 NP-\u043f\u043e\u043b\u043d\u043e\u0442\u0435 \u0438 \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0434\u0435\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041c\u043d\u043e\u0433\u0438\u0435 \u0441\u0445\u0435\u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0437\u0430\u0434\u0430\u0447\u0443 \u043e \u0440\u0430\u043d\u0446\u0435 (\u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0432\u0430\u0440\u0438\u0430\u0446\u0438\u044f\u0445), \u0432\u043e\u0442 \u043b\u0438\u0448\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438\u0437 \u043d\u0438\u0445: the compact knapsack problem, the multiplicative knapsack problem, the modular knapsack problem, the matrixcover problem, the group factorization problem\u2026<\/p>\n<p>  <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ax\/ri\/fe\/axrifelqcbbiuve-ylykv7ybzn0.png\" width=\"120\" height=\"120\" align=\"right\"\/> \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0438\u0437 \u043d\u0438\u0445 \u0443\u044f\u0437\u0432\u0438\u043c\u044b \u0434\u043b\u044f \u0430\u0442\u0430\u043a. \u041e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0447\u0442\u043e \u043d\u0435\u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e \u0441\u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u0430\u0449\u0438\u0449\u0435\u043d\u043d\u0443\u044e \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0440\u0430\u043d\u0446\u0435, \u0445\u043e\u0442\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430 \u043a\u0430\u043a NP-\u043f\u043e\u043b\u043d\u0430\u044f. \u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0440\u0430\u043d\u0446\u0435\u0432\u044b\u0445 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c \u0431\u044b\u043b\u043e \u0432\u0437\u043b\u043e\u043c\u0430\u043d\u043e. \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u044d\u0442\u043e, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0430, \u043e\u0431\u0449\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 (\u0440\u0435\u0448\u0435\u043d\u0438\u0438) \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 NP-\u043f\u043e\u043b\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439. <\/p>\n<p>  \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0443\u043c\u0430\u044e\u0442, \u0447\u0442\u043e \u043e\u0434\u043d\u0430\u0436\u0434\u044b \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0435\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c \u0432\u0440\u0435\u043c\u0435\u043d\u0435\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0438 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0432 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u043f\u043e-\u043f\u0440\u0435\u0436\u043d\u0435\u043c\u0443 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f NP-\u043f\u043e\u043b\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. <\/p>\n<p>  <b>\u0422\u0443\u0442 \u0435\u0441\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u00ab\u041d\u041e\u00bb.<\/b><\/p>\n<p>  \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, NP-\u043f\u043e\u043b\u043d\u043e\u0442\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0430 \u043d\u0430 \u0430\u043d\u0430\u043b\u0438\u0437\u0435 \u043d\u0430\u0438\u0445\u0443\u0434\u0448\u0435\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f, \u0432\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, NP-\u043f\u043e\u043b\u043d\u043e\u0442\u0430 \u2014 \u044d\u0442\u043e \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043e\u0431\u0449\u0435\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u0430 \u043d\u0435 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0441\u0440\u0435\u0434\u043d\u044e\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e\u0439.<\/p>\n<p>  <i>\u041c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0430\u043d\u043d\u043e\u0439 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b:<\/i><\/p>\n<p>  <a href=\"http:\/\/web.archive.org\/web\/20111119210028\/http:\/\/www.ssl.stu.neva.ru\/psw\/crypto\/open_key_crypt.pdf\"> (1) <\/a> \u0410. \u0421\u0430\u043b\u043e\u043c\u0430\u0430. \u041a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u044f \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c\/ Public-Key Cryptography. \u2014 Springer-Verlag, 1990. \u2014 \u0421\u0442\u0440. 75-82, \u0441\u0442\u0440. 101\u2014111<\/p>\n<p>  <a href=\"http:\/\/ljk.imag.fr\/membres\/Jean-Guillaume.Dumas\/Enseignements\/ProjetsCrypto\/sac-a-dos-LLL\/knapsack.html\">(2)<\/a> \u041c\u0438\u043d \u041a\u0438\u043d \u041b\u0430\u0439. \u0420\u0430\u043d\u0446\u0435\u0432\u044b\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0441\u0438\u0441\u0442\u0435\u043c\u044b: \u043f\u0440\u043e\u0448\u043b\u043e\u0435 \u0438 \u0431\u0443\u0434\u0443\u0449\u0435\u0435 \u2014 \u041a\u0430\u043b\u0438\u0444\u043e\u0440\u043d\u0438\u0439\u0441\u043a\u0438\u0439 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442, 2001<br \/>  <a href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020025507001545?via%3Dihub\">(3)<\/a> Baocang Wang, Qianhong Wu, Yupu Hu. A knapsack-based probabilistic encryption scheme. 2007<\/p>\n<p>  <a href=\"https:\/\/en.wikipedia.org\/wiki\/Knapsack_problem\">(4)<\/a> \u2014 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5_%D0%B2_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D0%B8\">(5)<\/a><\/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\/post\/529346\/\"> https:\/\/habr.com\/ru\/post\/529346\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\">\u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 (\u0438\u043b\u0438 \u0417\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u0430\u043d\u0446\u0435) \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438 (\u0430\u043d\u0433\u043b. Knapsack problem) \u2014 \u044d\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430, \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0430\u043c\u0435\u0440\u0438\u043a\u0430\u043d\u0441\u043a\u0438\u0435 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u044b \u0420\u0430\u043b\u044c\u0444 \u041c\u0435\u0440\u043a\u043b \u0438 \u041c\u0430\u0440\u0442\u0438\u043d \u0425\u0435\u043b\u043b\u043c\u0430\u043d \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c.<\/p>\n<p>  <b>\u0414\u0430\u043b\u0435\u0435 \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435<\/b><br \/>  <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/f-\/3q\/-k\/f-3q-kjzcfguauyssd_v4k1poju.png\" width=\"130\" height=\"130\" align=\"right\"\/>  <\/p>\n<ul>\n<li>\u0424\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435 (+\u043f\u043e\u0447\u0435\u043c\u0443 \u0440\u044e\u043a\u0437\u0430\u043a?)<\/li>\n<li>\u041b\u0435\u0433\u043a\u0430\u044f \u0438 \u0442\u0440\u0443\u0434\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b<\/li>\n<li>\u041f\u0440\u0438\u043c\u0435\u0440\u044b<\/li>\n<li>\u0418\u0441\u0442\u043e\u0440\u0438\u044f<\/li>\n<\/ul>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-313570","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/313570","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=313570"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/313570\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=313570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=313570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=313570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}