{"id":437598,"date":"2024-11-07T03:00:28","date_gmt":"2024-11-07T03:00:28","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=437598"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=437598","title":{"rendered":"<span>\u041f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443: \u0442\u0435\u0441\u0442 \u0410\u0433\u0440\u0430\u0432\u0430\u043b\u0430-\u041a\u0430\u044f\u043b\u0430-\u0421\u0430\u043a\u0441\u0435\u043d\u044b<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h2>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0432\u0430\u0436\u043d\u0435\u0439\u0448\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0447\u0438\u0441\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443. \u0422\u043e \u0435\u0441\u0442\u044c \u043f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0438\u043b\u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u044b\u043c. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0440\u0435\u0448\u0430\u044e\u0449\u0438\u0435 \u044d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 (\u0438\u0445 \u0442\u0430\u043a\u0436\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0442\u0435\u0441\u0442\u0430\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b), \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0441 \u0434\u0440\u0435\u0432\u043d\u0438\u0445 \u0432\u0440\u0435\u043c\u0451\u043d, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430. \u041d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0438\u043c\u0435\u044e\u0449\u0435\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0434\u043e\u043b\u0433\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e \u043d\u0435 \u0431\u044b\u043b\u043e.<\/p>\n<p>\u0412 2002 \u0433\u043e\u0434\u0443 \u0438\u043d\u0434\u0438\u0439\u0441\u043a\u0438\u043c\u0438 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430\u043c\u0438 \u0410\u0433\u0440\u0430\u0432\u0430\u043b\u043e\u043c, \u041a\u0430\u0439\u044f\u043b\u043e\u043c \u0438 \u0421\u0430\u043a\u0441\u0435\u043d\u043e\u0439 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u00abPRIMES is in P\u00bb \u0431\u044b\u043b \u0432\u043f\u0435\u0440\u0432\u044b\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0447\u0438\u0441\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c, \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u044b\u043c, \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0438 \u0431\u0435\u0437\u0443\u0441\u043b\u043e\u0432\u043d\u044b\u043c. \u0414\u043e \u044d\u0442\u043e\u0433\u043e \u0431\u044b\u043b\u0438 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0431\u043b\u0430\u0434\u0430\u043b\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0442\u0440\u0435\u043c\u044f \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0451\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432.<\/p>\n<ul>\n<li>\n<p><strong>\u041f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/strong> \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0430 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u043c \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0438\u0442 \u0432 \u0447\u0438\u0441\u043b\u0435. \u041f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u0442\u0435\u0441\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u0441\u0442 \u0410\u0434\u043b\u0435\u043c\u0430\u043d\u0430-\u041f\u043e\u043c\u0435\u0440\u0430\u043d\u0446\u0430-\u0420\u0443\u043c\u0435\u043b\u0438.<\/p>\n<\/li>\n<li>\n<p><strong>\u0423\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/strong> \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u043a \u043b\u044e\u0431\u044b\u043c \u0447\u0438\u0441\u043b\u0430\u043c, \u0430 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043a \u0447\u0438\u0441\u043b\u0430\u043c \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430. \u041f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u043d\u0435\u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u0441\u0442 \u041b\u044e\u043a\u0430-\u041b\u0435\u043c\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u041c\u0435\u0440\u0441\u0435\u043d\u043d\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0414\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c<\/strong> \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u044b\u0434\u0430\u0451\u0442 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u043e\u0434\u043d\u0438\u0445 \u0438 \u0442\u0435\u0445 \u0436\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u043d\u0435\u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e (\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u043e\u0433\u043e) \u0442\u0435\u0441\u0442\u0430, \u043c\u043e\u0436\u0435\u0442 \u0441\u043b\u0443\u0436\u0438\u0442\u044c \u0442\u0435\u0441\u0442 \u041c\u0438\u043b\u043b\u0435\u0440\u0430-\u0420\u0430\u0431\u0438\u043d\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0411\u0435\u0437\u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u044c<\/strong> \u2014 \u044d\u0442\u043e \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0442 \u043d\u0435\u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0445 \u0433\u0438\u043f\u043e\u0442\u0435\u0437. \u041d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u0431\u0435\u0437\u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0435\u0441\u0442 \u041c\u0438\u043b\u043b\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u043f\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043e\u0431\u043e\u0431\u0449\u0451\u043d\u043d\u0443\u044e \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0443 \u0420\u0438\u043c\u0430\u043d\u0430.<\/p>\n<\/li>\n<\/ul>\n<h2>\u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f<\/h2>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\mathbb {Z}_n\" alt=\"\\mathbb {Z}_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7e\/7ed\/7ed469045c90d85138b959e7e67ccbad.svg\" width=\"auto\" height=\"auto\"\/> &#8212; \u043a\u043e\u043b\u044c\u0446\u043e \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e n.<\/p>\n<p>\u0417\u0430\u043f\u0438\u0441\u044c <img decoding=\"async\" class=\"formula inline\" source=\"g(x) = h(x) \\pmod{n}\" alt=\"g(x) = h(x) \\pmod{n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4\/4d\/4d8\/4d854a4fccd2836d68b134ef9aae452f.svg\" width=\"auto\" height=\"auto\"\/> \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u044b, \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u0432\u044b\u0447\u0435\u0442\u044b \u0438\u0437 <img decoding=\"async\" class=\"formula inline\" source=\"\\mathbb {Z}_n\" alt=\"\\mathbb {Z}_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7e\/7ed\/7ed469045c90d85138b959e7e67ccbad.svg\" width=\"auto\" height=\"auto\"\/>, \u0440\u0430\u0432\u043d\u044b.<\/p>\n<p>\u0417\u0430\u043f\u0438\u0441\u044c <img decoding=\"async\" class=\"formula inline\" source=\"g(x) = h(x) \\pmod{x^r - 1, n}\" alt=\"g(x) = h(x) \\pmod{x^r - 1, n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/81\/819\/819e745be7309f7c8b74812063c00ba4.svg\" width=\"auto\" height=\"auto\"\/> \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u044b \u0441 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u0438\u0437 <img decoding=\"async\" class=\"formula inline\" source=\"\\mathbb {Z}_n\" alt=\"\\mathbb {Z}_n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7e\/7ed\/7ed469045c90d85138b959e7e67ccbad.svg\" width=\"auto\" height=\"auto\"\/> \u0440\u0430\u0432\u043d\u044b \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"x^r - 1\" alt=\"x^r - 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/35\/35b\/35b72839e135d096696f7ae503655dd0.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"ord_r(n)\" alt=\"ord_r(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/25\/255\/255f9228e7e32da31d3a58c593653b32.svg\" width=\"auto\" height=\"auto\"\/> \u2014 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0447\u0438\u0441\u043b\u0430 n \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e r. \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e k, \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"n^k = 1 \\pmod{r}\" alt=\"n^k = 1 \\pmod{r}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/36\/36b\/36b8b211ffd49074f09d4412375ad62f.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\phi(n)\" alt=\"\\phi(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a0\/a00\/a0020daa3fec60004254eda5aa74adff.svg\" width=\"auto\" height=\"auto\"\/> \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u042d\u0439\u043b\u0435\u0440\u0430. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043c\u0435\u043d\u044c\u0448\u0438\u0445 n \u0438 \u0432\u0437\u0430\u0438\u043c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0441 \u043d\u0438\u043c.<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\log(n)\" alt=\"\\log(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/be\/be8\/be82f968ba5d0c8adfa33588cf8232d0.svg\" width=\"auto\" height=\"auto\"\/> \u2014 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044e \u0434\u0432\u0430 \u0447\u0438\u0441\u043b\u0430 n.<\/p>\n<h2>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f<\/h2>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u043f\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0442\u0435\u043e\u0440\u0435\u043c\u0443:<\/p>\n<p><strong>\u0422\u0435\u043e\u0440\u0435\u043c\u0430:<\/strong><br \/> \u0415\u0441\u043b\u0438 \u0447\u0438\u0441\u043b\u0430 a \u0438 n \u0432\u0437\u0430\u0438\u043c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"(x + a)^n = x^n + a \\pmod{n}\" alt=\"(x + a)^n = x^n + a \\pmod{n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/56\/560\/5607c8b93d613efb5cbe2d8d30704863.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u0433\u0434\u0430 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 n \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435.<\/p>\n<p>\u042d\u0442\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e \u0443\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b. \u041d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7b\/7ba\/7ba55e7c64a9405a0b39a1107e90ca94.svg\" width=\"auto\" height=\"auto\"\/> \u043f\u0440\u043e\u0432\u0435\u0440\u043e\u043a \u2014 \u043f\u043e \u0447\u0438\u0441\u043b\u0443 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u0432 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u0445. \u0418\u0434\u0435\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430, \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043c\u0435\u043d\u044c\u0448\u0435\u0439, \u0447\u0435\u043c n. \u0418\u0437 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0432\u044b\u0442\u0435\u043a\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435:<\/p>\n<p><strong>\u0421\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435:<\/strong><br \/> \u0415\u0441\u043b\u0438 n \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0442\u043e \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e r \u0438 \u043b\u044e\u0431\u043e\u0433\u043e \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e 0 &lt; a &lt; n \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f<\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"(x + a)^n= x^n + a \\pmod{x^r - 1, n} \" alt=\"(x + a)^n= x^n + a \\pmod{x^r - 1, n} \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/2b\/2b4\/2b43b342b847165ed99da5a65ab8c4da.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u041e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0435\u0432\u0435\u0440\u043d\u043e. \u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0438\u043d\u0434\u0438\u0439\u0441\u043a\u0438\u0445 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0432 \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043e, \u0447\u0442\u043e \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e r \u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 a \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0432\u0435\u0440\u043d\u043e:<\/p>\n<p><strong>\u0422\u0435\u043e\u0440\u0435\u043c\u0430:<\/strong><br \/> \u0415\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 r, \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u043e <\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"ord_{r}(n) &gt; \\log^2 n\" alt=\"ord_{r}(n) &gt; \\log^2 n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/ac\/ac0\/ac077b7f5a38dd42e0faf58190872923.svg\" width=\"auto\" height=\"auto\"\/>, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e <\/p>\n<p><img decoding=\"async\" class=\"formula\" source=\"(x + a)^n= x^n + a \\pmod{x^r - 1, n} \" alt=\"(x + a)^n= x^n + a \\pmod{x^r - 1, n} \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/2b\/2b4\/2b43b342b847165ed99da5a65ab8c4da.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u0412\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 <img decoding=\"async\" class=\"formula inline\" source=\"1 \\le a \\le  \\left \\lfloor {\\sqrt{\\phi(n)}\\log n} \\right \\rfloor\" alt=\"1 \\le a \\le  \\left \\lfloor {\\sqrt{\\phi(n)}\\log n} \\right \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/6f\/6f6\/6f658076380092c6d8dfe71c0526e272.svg\" width=\"auto\" height=\"auto\"\/>, \u0442\u043e n \u2014 \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u043b\u0438\u0431\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e.<\/p>\n<p>\u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443, \u0447\u0442\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u044b.<\/p>\n<h2>\u0422\u0435\u0441\u0442 AKS<\/h2>\n<h3>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/h3>\n<p><strong>\u0412\u0445\u043e\u0434:<\/strong> \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e n &gt; 1.<br \/> <strong>\u0412\u044b\u0445\u043e\u0434:<\/strong> \u041f\u0420\u041e\u0421\u0422\u041e\u0415, \u0435\u0441\u043b\u0438 n \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415 \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435.<\/p>\n<p><strong>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/strong><\/p>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 n \u2014 \u0442\u043e\u0447\u043d\u0430\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"(n = a^b, a, b \\in \\mathbb {N}, b &gt; 1)\" alt=\"(n = a^b, a, b \\in \\mathbb {N}, b &gt; 1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/3f\/3fe\/3fe3f6961efc922bac46401a5ea5e83e.svg\" width=\"auto\" height=\"auto\"\/>, \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430\u0439\u0442\u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 r, \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"ord_{r}(n) &gt; \\log^2 n\" alt=\"ord_{r}(n) &gt; \\log^2 n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/ac\/ac0\/ac077b7f5a38dd42e0faf58190872923.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 1 &lt; \u041d\u041e\u0414(a, n) &lt; n \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e <img decoding=\"async\" class=\"formula inline\" source=\"a \\le r\" alt=\"a \\le r\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/77\/77a\/77a3afb8d8b220c6ce168e95266bef02.svg\" width=\"auto\" height=\"auto\"\/>, \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"n \\le r\" alt=\"n \\le r\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/ac\/ac2\/ac2f473ad1ca07aec6fac4ff7b8cf414.svg\" width=\"auto\" height=\"auto\"\/> \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e <img decoding=\"async\" class=\"formula inline\" source=\"1 \\le a \\le  \\left \\lfloor {\\sqrt{\\phi(r)}\\log n} \\right \\rfloor\" alt=\"1 \\le a \\le  \\left \\lfloor {\\sqrt{\\phi(r)}\\log n} \\right \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9\/95\/950\/9501c32bf3165511a5a8255b8d6f1e05.svg\" width=\"auto\" height=\"auto\"\/>: \u0415\u0441\u043b\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"(x + a)^n \\ne x^n + a \\pmod{x^r - 1, n}\" alt=\"(x + a)^n \\ne x^n + a \\pmod{x^r - 1, n}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4\/4a\/4aa\/4aa959821696b27e1c21173be0ef8b4e.svg\" width=\"auto\" height=\"auto\"\/> \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0435\u0440\u043d\u0443\u0442\u044c \u041f\u0420\u041e\u0421\u0422\u041e\u0415.<\/p>\n<\/li>\n<\/ol>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0448\u0430\u0433\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0447\u0438\u0441\u043b\u0430 47.<\/p>\n<h3>\u0428\u0430\u0433 1<\/h3>\n<p>\u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0448\u0430\u0433\u0435 \u043d\u0443\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0447\u0438\u0441\u043b\u043e n \u0442\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430, \u0442. \u0435. <img decoding=\"async\" class=\"formula inline\" source=\"n = a^b\" alt=\"n = a^b\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/10\/102\/102f7b843dc83fa00bee7bfefb1d05ba.svg\" width=\"auto\" height=\"auto\"\/>. \u041f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u2014 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor n^{1\/b} \\right \\rfloor^b \\ne n\" alt=\"\\left \\lfloor n^{1\/b} \\right \\rfloor^b \\ne n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b6\/b61\/b6148b5e968d2967b4a58c53f78824f3.svg\" width=\"auto\" height=\"auto\"\/>. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f <img decoding=\"async\" class=\"formula inline\" source=\"2 \\le b &lt; \\log n\" alt=\"2 \\le b &lt; \\log n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/1b\/1b0\/1b0a58671d91f0257c49e6fb98cf86de.svg\" width=\"auto\" height=\"auto\"\/> (\u0442\u0430\u043a \u043a\u0430\u043a \u0435\u0441\u043b\u0438 <\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"b &gt;\\log n\" alt=\"b &gt;\\log n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/63\/637\/637c082fc9831ebb8ee3de10398d7934.svg\" width=\"auto\" height=\"auto\"\/>, \u0442\u043e <img decoding=\"async\" class=\"formula inline\" source=\"2^b &gt; n\" alt=\"2^b &gt; n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/fe\/fe2\/fe22027f5ff8a8cb4fbf0e75eb339b65.svg\" width=\"auto\" height=\"auto\"\/>) <\/p>\n<pre><code class=\"cpp\">function isPerfectPower(n) {     for (b = 2; b &lt; ceil(log(n)); b++) {         if (floor(n ** (1.0 \/ b)) ** b) == n:             return true;     }     return false; } <\/code><\/pre>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor \\log 47 \\right \\rfloor = 5\" alt=\"\\left \\lfloor \\log 47 \\right \\rfloor = 5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e\/e3\/e39\/e39fd67f042b59f5138486c2c4a9ffd1.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043e\u0442 2 \u0434\u043e 4:<\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor 47^{1\/2} \\right \\rfloor^2 = 36\" alt=\"\\left \\lfloor 47^{1\/2} \\right \\rfloor^2 = 36\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/04\/045\/045f0cfa0a5b6201603f9f5eef3e01f8.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor 47^{1\/3} \\right \\rfloor^3 = 27\" alt=\"\\left \\lfloor 47^{1\/3} \\right \\rfloor^3 = 27\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/0c\/0c6\/0c6fb528caf78e16bd72d6c6b6f07599.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor 47^{1\/4} \\right \\rfloor^4 = 16\" alt=\"\\left \\lfloor 47^{1\/4} \\right \\rfloor^4 = 16\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/ad\/ad0\/ad0afa96c0593801b253196a2f61c5f5.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u0421\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, 47 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430.<\/p>\n<h3>\u0428\u0430\u0433 2<\/h3>\n<p>\u041f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0435\u0435 r \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e r \u043d\u0443\u0436\u043d\u043e:<\/p>\n<ol>\n<li>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e  <img decoding=\"async\" class=\"formula inline\" source=\"n^k \\ne 1 \\pmod{r}\" alt=\"n^k \\ne 1 \\pmod{r}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b5\/b5e\/b5e8e0819f9e30fdd640fbf364e038eb.svg\" width=\"auto\" height=\"auto\"\/> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 <img decoding=\"async\" class=\"formula inline\" source=\"k \\le \\lfloor \\log^2n \\rfloor\" alt=\"k \\le \\lfloor \\log^2n \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/2d\/2d6\/2d61a6cf062740e550026d786b59fe5c.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u043e\u0434\u043d\u043e \u0438\u0437 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0440\u0430\u0432\u043d\u043e \u0435\u0434\u0438\u043d\u0438\u0446\u0435 \u2014 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 r.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0432\u0441\u0435 \u043d\u0435 \u0440\u0430\u0432\u043d\u044b \u0435\u0434\u0438\u043d\u0438\u0446\u0435 \u2014 r \u043d\u0430\u0439\u0434\u0435\u043d\u043e.<\/p>\n<\/li>\n<\/ol>\n<p>\u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0438\u0441\u043a\u043e\u043c\u043e\u0435 r \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log^5 n)\" alt=\"O(\\log^5 n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2\/20\/208\/20865956f9e89cba1d9a2d3e93a071c9.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<pre><code class=\"cpp\">function findR(n) {     r = 2;      while (true) {         find = true;         for (k = 1; k &lt; ceil(log(n) ** 2); k++) {             if (n ** k % r == 1) {                 find = false;                 break             }         }                          if (find) {             return r;         } else {             r++;         }     }        } <\/code><\/pre>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"\\lfloor \\log^2 47 \\rfloor = 32\" alt=\"\\lfloor \\log^2 47 \\rfloor = 32\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a\/a9\/a93\/a93b1277eff363a26a71e8f66c162856.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u0418\u0441\u043a\u043e\u043c\u043e\u0435 r = 41:<br \/> <img decoding=\"async\" class=\"formula inline\" source=\"47^{1} \\pmod{41} = 6\" alt=\"47^{1} \\pmod{41} = 6\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/68\/689\/6899bc287744093083e25982411e67b1.svg\" width=\"auto\" height=\"auto\"\/><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"47^{2} \\pmod{41} = 36\" alt=\"47^{2} \\pmod{41} = 36\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/8d\/8d3\/8d3bc6de8bf2c3264dcb87df00e93575.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\ldots\" alt=\"\\ldots\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/37\/379\/379ee6906339e7dd45144eee226905c4.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"47^{32} \\pmod{41} = 37\" alt=\"47^{32} \\pmod{41} = 37\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/68\/68b\/68b3a114b0b4baa40ccdc9cf83c64729.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<h3>\u0428\u0430\u0433\u0438 3-4<\/h3>\n<p>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u044b\u0435, \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u041d\u041e\u0414 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b.<\/p>\n<h3>\u0428\u0430\u0433 5<\/h3>\n<p>\u0414\u043b\u044f \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u044f \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430\u043c\u0438. \u0417\u0434\u0435\u0441\u044c \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0434\u043d\u0443 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e: \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0431\u0435\u0437 \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u0441\u0442\u0435\u043f\u0435\u043d\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"r - 1\" alt=\"r - 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/dd\/dda\/dda3813c0552010ac1cf6cea22ef81ff.svg\" width=\"auto\" height=\"auto\"\/> \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0442\u043e \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u0441\u0442\u0435\u043f\u0435\u043d\u0438 <img decoding=\"async\" class=\"formula inline\" source=\"2r-2\" alt=\"2r-2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/56\/567\/567a9261f28b6cb82ac2fc9465243f2b.svg\" width=\"auto\" height=\"auto\"\/>:<br \/> <img decoding=\"async\" class=\"formula inline\" source=\"f(x) = c_{2r-2}x^{2r-2} + \\ldots + c_rx^r +c_{r - 1}x^{r-1} + c_{r-1}x^{r-1} + \\ldots +  c_1x + c_0\" alt=\"f(x) = c_{2r-2}x^{2r-2} + \\ldots + c_rx^r +c_{r - 1}x^{r-1} + c_{r-1}x^{r-1} + \\ldots +  c_1x + c_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/57\/57b\/57b15df10644fb33bbfb946107dfe2db.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"x^r - 1\" alt=\"x^r - 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/35\/35b\/35b72839e135d096696f7ae503655dd0.svg\" width=\"auto\" height=\"auto\"\/>:<br \/> <img decoding=\"async\" class=\"formula inline\" source=\"f(x) = a(x)(x^r - 1) + b(x)\" alt=\"f(x) = a(x)(x^r - 1) + b(x)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/df\/dfe\/dfe36e12f6837a0b7dd1729b82c50127.svg\" width=\"auto\" height=\"auto\"\/>, \u0433\u0434\u0435<br \/> <img decoding=\"async\" class=\"formula inline\" source=\"a(x) = a_{r-2}x^{r-2} + \\ldots + a_0\" alt=\"a(x) = a_{r-2}x^{r-2} + \\ldots + a_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8\/86\/868\/8683d841e07f8a7778b41215d29ea42e.svg\" width=\"auto\" height=\"auto\"\/><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"b(x) = b_{r-2}x^{r-2} + \\ldots + b_0\" alt=\"b(x) = b_{r-2}x^{r-2} + \\ldots + b_0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/65\/65c\/65ce8c1d5f491c369a21a8c2e24146d5.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p>\u0420\u0430\u0441\u043a\u0440\u044b\u0432\u0430\u044f \u0441\u043a\u043e\u0431\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b <img decoding=\"async\" class=\"formula inline\" source=\"b\" alt=\"b\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9\/92\/92e\/92eb5ffee6ae2fec3ad71c777531578f.svg\" width=\"auto\" height=\"auto\"\/>:<br \/> <img decoding=\"async\" class=\"formula inline\" source=\"b_0 = c_0 + a_0 = c_0 + c_r\" alt=\"b_0 = c_0 + a_0 = c_0 + c_r\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/d2\/d28\/d2818bee826ae7af9688cd5b6b38adc5.svg\" width=\"auto\" height=\"auto\"\/><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"b_1 = c_1 + a_1 = c_1 + c_{1 + r}\" alt=\"b_1 = c_1 + a_1 = c_1 + c_{1 + r}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/03\/030\/0304fbb5968ae8a198787e05099fb60b.svg\" width=\"auto\" height=\"auto\"\/><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"\\ldots\" alt=\"\\ldots\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/37\/379\/379ee6906339e7dd45144eee226905c4.svg\" width=\"auto\" height=\"auto\"\/><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"b_{r - 2} = c_{r - 2} + a_{r - 2} = c_{r - 2} + c_{2r - 2}\" alt=\"b_{r - 2} = c_{r - 2} + a_{r - 2} = c_{r - 2} + c_{2r - 2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/16\/16d\/16d225a7bad83dc717834e8ce3730749.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<pre><code class=\"cpp\">function mod (p) {     for (i = p.degree(); i &gt;= r; i--){         p[i - r] = p[i - r] + p[i];         p[i] = 0;     } } <\/code><\/pre>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><br \/> <img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor {\\sqrt{\\phi(41)}\\log 41} \\right \\rfloor = 36\" alt=\"\\left \\lfloor {\\sqrt{\\phi(41)}\\log 41} \\right \\rfloor = 36\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e\/ee\/eef\/eef0325fb0663c262440e61a5c984400.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"a = 1: (x + 1)^{47} = x^{47} + 1 \\pmod{x^{41} - 1, 47}  = x^6 + 1\" alt=\"a = 1: (x + 1)^{47} = x^{47} + 1 \\pmod{x^{41} - 1, 47}  = x^6 + 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/7a\/7ad\/7ad4d3eadb3ab23aefa9fe3dfc842139.svg\" width=\"auto\" height=\"auto\"\/>  <img decoding=\"async\" class=\"formula inline\" source=\"a = 2: (x + 2)^{47} = x^{47} + 2 \\pmod{x^41 - 1, 47}  = x^6 + 2\" alt=\"a = 2: (x + 2)^{47} = x^{47} + 2 \\pmod{x^41 - 1, 47}  = x^6 + 2\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/35\/35a\/35a78b38548f8f71d6f1f8ba6e9e70b7.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"\\ldots\" alt=\"\\ldots\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/37\/379\/379ee6906339e7dd45144eee226905c4.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<p><img decoding=\"async\" class=\"formula inline\" source=\"a = 36: (x + 36)^{47} = x^{47} + 36 \\pmod{x^{41} - 1, 47}  = x^6 + 36\" alt=\"a = 36: (x + 36)^{47} = x^{47} + 36 \\pmod{x^{41} - 1, 47}  = x^6 + 36\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9\/92\/92f\/92f5874f238c95ba02009db257785856.svg\" width=\"auto\" height=\"auto\"\/><\/p>\n<h2>\u041e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438<\/h2>\n<p>\u0412\u0432\u0435\u0434\u0451\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435: <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(t(n)) = O(t(n) \\cdot poly(\\log(t(n))))\" alt=\"\\widetilde{O}(t(n)) = O(t(n) \\cdot poly(\\log(t(n))))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/0d\/0d0\/0d04b9a35ced87273e1b6dd3bcb1c08a.svg\" width=\"auto\" height=\"auto\"\/>, \u0433\u0434\u0435 <img decoding=\"async\" class=\"formula inline\" source=\"t(n)\" alt=\"t(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/ce\/ce3\/ce335ed7cda4017234864a41e8bbf8f3.svg\" width=\"auto\" height=\"auto\"\/> \u2014 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u0442 n.<\/p>\n<p>\u041f\u0440\u0438 \u043e\u0446\u0435\u043d\u043a\u0430\u0445 \u0431\u0443\u0434\u0435\u043c \u043e\u043f\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 m-\u0431\u0438\u0442\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0438\u043c\u0435\u044e\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(m)\" alt=\"\\widetilde{O}(m)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e\/e8\/e8e\/e8e1e18e3f5b776aea823e079e2ea4c3.svg\" width=\"auto\" height=\"auto\"\/>. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0430\u0434 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 d \u0438\u043c\u0435\u044e\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(dm)\" alt=\"\\widetilde{O}(dm)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6\/66\/662\/662b9618f67988a0bc2840b6a6cd6f85.svg\" width=\"auto\" height=\"auto\"\/>. \u041d\u041e\u0414 \u0434\u0432\u0443\u0445 m-\u0431\u0438\u0442\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0437\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log n)\" alt=\"O(\\log n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/0c\/0ca\/0ca47d9a481af371d1210a620c1945db.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p>\u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0448\u0430\u0433\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0447\u0438\u0441\u043b\u043e \u0442\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e, \u0438\u043c\u0435\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(\\log^3n)\" alt=\"\\widetilde{O}(\\log^3n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f\/fa\/fa7\/fa7bae64e52c2e55a068d9f22b438e12.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p>\u041d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u0448\u0430\u0433\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 r. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 r \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439 <img decoding=\"async\" class=\"formula inline\" source=\"n^k \\ne 1 \\pmod{r}\" alt=\"n^k \\ne 1 \\pmod{r}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b5\/b5e\/b5e8e0819f9e30fdd640fbf364e038eb.svg\" width=\"auto\" height=\"auto\"\/> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 <img decoding=\"async\" class=\"formula inline\" source=\"k \\le \\log^2n\" alt=\"k \\le \\log^2n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/34\/342\/342f7e18fbe622670edaf3d0a7784119.svg\" width=\"auto\" height=\"auto\"\/>. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e r \u044d\u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log^2n)\" alt=\"O(\\log^2n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1\/12\/124\/1245d412ae9fab2fd7892fb683c6fa61.svg\" width=\"auto\" height=\"auto\"\/> \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e r, \u0437\u043d\u0430\u0447\u0438\u0442 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e r \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(\\log^2n \\log r)\" alt=\"\\widetilde{O}(\\log^2n \\log r)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/db\/dbe\/dbef596ebb9ec54898b80806203b9738.svg\" width=\"auto\" height=\"auto\"\/>. \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u044f, \u0447\u0442\u043e r \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0440\u044f\u0434\u043e\u043a <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log^5n)\" alt=\"O(\\log^5n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c\/c0\/c01\/c01f37426dccaf94161162fff9ed669d.svg\" width=\"auto\" height=\"auto\"\/>, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0448\u0430\u0433\u0430 \u0440\u0430\u0432\u043d\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(\\log^7n)\" alt=\"\\widetilde{O}(\\log^7n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b\/b3\/b3d\/b3da95e8c3e7a3fbce5935e542c63d8c.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p>\u0422\u0440\u0435\u0442\u0438\u0439 \u0448\u0430\u0433 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u041d\u041e\u0414 \u0434\u043b\u044f r \u0447\u0438\u0441\u0435\u043b. \u041e\u0431\u0449\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0448\u0430\u0433\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"O(r \\log n) = O(\\log^6 n)\" alt=\"O(r \\log n) = O(\\log^6 n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d\/d2\/d22\/d221aee340a4ba4201a7b4d3c4dcf84c.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p>\u041d\u0430 \u043f\u044f\u0442\u043e\u043c \u0448\u0430\u0433\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c <img decoding=\"async\" class=\"formula inline\" source=\"\\left \\lfloor {\\sqrt{\\phi(n)}\\log n} \\right \\rfloor\" alt=\"\\left \\lfloor {\\sqrt{\\phi(n)}\\log n} \\right \\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3\/35\/35e\/35ed8f7137647842277b3c43e020d428.svg\" width=\"auto\" height=\"auto\"\/> \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432. \u041a\u0430\u0436\u0434\u043e\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log n)\" alt=\"O(\\log n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/0c\/0ca\/0ca47d9a481af371d1210a620c1945db.svg\" width=\"auto\" height=\"auto\"\/> \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 r, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"O(\\log n)\" alt=\"O(\\log n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0\/0c\/0ca\/0ca47d9a481af371d1210a620c1945db.svg\" width=\"auto\" height=\"auto\"\/>. \u041a\u0430\u0436\u0434\u043e\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u0435\u043d\u043e \u0437\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(r \\log^2 n)\" alt=\"\\widetilde{O}(r \\log^2 n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7\/74\/746\/7468e66ce91dd93220bad919d7fbb74a.svg\" width=\"auto\" height=\"auto\"\/>. \u0418\u0442\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0448\u0430\u0433\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(r \\sqrt{\\phi (r)} \\log^3 n) = \\widetilde{O}(r^{3\/2} \\log^3 n) = \\widetilde{O}(\\log^{21\/2}n)\" alt=\"\\widetilde{O}(r \\sqrt{\\phi (r)} \\log^3 n) = \\widetilde{O}(r^{3\/2} \\log^3 n) = \\widetilde{O}(\\log^{21\/2}n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/5a\/5a2\/5a28dc90ca5cef44c1e7315a81c68731.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<p>\u042d\u0442\u0443 \u043e\u0446\u0435\u043d\u043a\u0443 \u0438\u0437 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u043c\u043e\u0436\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c. \u041b\u0443\u0447\u0448\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 <img decoding=\"async\" class=\"formula inline\" source=\"\\widetilde{O}(\\log^6n)\" alt=\"\\widetilde{O}(\\log^6n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4\/41\/416\/416729beba4d6831b3fd5e038b18b524.svg\" width=\"auto\" height=\"auto\"\/>.<\/p>\n<h2>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435<\/h2>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c AKS \u0438\u043c\u0435\u0435\u0442 \u0432\u0430\u0436\u043d\u043e\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043e\u0434\u043d\u0430\u043a\u043e \u043d\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043d \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438. \u0414\u0430\u0436\u0435 \u043f\u0440\u0438 \u043e\u0446\u0435\u043d\u043a\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430 <img decoding=\"async\" class=\"formula inline\" source=\"r = O(\\log^2{n})\" alt=\"r = O(\\log^2{n})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5\/5c\/5cf\/5cfbf6dae232503dde194a12bf28d15f.svg\" width=\"auto\" height=\"auto\"\/> \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0447\u0438\u0441\u043b\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 1024 \u0431\u0438\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u043a\u043e\u043b\u043e 1 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442\u0430 \u043f\u0430\u043c\u044f\u0442\u0438. \u0414\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043b\u0443\u0447\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b.<\/p>\n<hr\/>\n<p><a href=\"https:\/\/t.me\/seregablogtg\" rel=\"noopener noreferrer nofollow\">\u041a\u0430\u043d\u0430\u043b<\/a> \u0441 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430\u043c\u0438.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \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\/855792\/\"> https:\/\/habr.com\/ru\/articles\/855792\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<h2>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435<\/h2>\n<p>\u041e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0432\u0430\u0436\u043d\u0435\u0439\u0448\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0447\u0438\u0441\u0435\u043b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443. \u0422\u043e \u0435\u0441\u0442\u044c \u043f\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0438\u043b\u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u044b\u043c. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0440\u0435\u0448\u0430\u044e\u0449\u0438\u0435 \u044d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 (\u0438\u0445 \u0442\u0430\u043a\u0436\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0442\u0435\u0441\u0442\u0430\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b), \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0441 \u0434\u0440\u0435\u0432\u043d\u0438\u0445 \u0432\u0440\u0435\u043c\u0451\u043d, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0435\u0448\u0435\u0442\u043e \u042d\u0440\u0430\u0442\u043e\u0441\u0444\u0435\u043d\u0430. \u041d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0438\u043c\u0435\u044e\u0449\u0435\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0434\u043e\u043b\u0433\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e \u043d\u0435 \u0431\u044b\u043b\u043e.<\/p>\n<p>\u0412 2002 \u0433\u043e\u0434\u0443 \u0438\u043d\u0434\u0438\u0439\u0441\u043a\u0438\u043c\u0438 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430\u043c\u0438 \u0410\u0433\u0440\u0430\u0432\u0430\u043b\u043e\u043c, \u041a\u0430\u0439\u044f\u043b\u043e\u043c \u0438 \u0421\u0430\u043a\u0441\u0435\u043d\u043e\u0439 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u00abPRIMES is in P\u00bb \u0431\u044b\u043b \u0432\u043f\u0435\u0440\u0432\u044b\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0447\u0438\u0441\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c, \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u044b\u043c, \u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0438 \u0431\u0435\u0437\u0443\u0441\u043b\u043e\u0432\u043d\u044b\u043c. \u0414\u043e \u044d\u0442\u043e\u0433\u043e \u0431\u044b\u043b\u0438 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0431\u043b\u0430\u0434\u0430\u043b\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0442\u0440\u0435\u043c\u044f \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0451\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432.<\/p>\n<ul>\n<li>\n<p><strong>\u041f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/strong> \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0430 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u043c \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0438\u0442 \u0432 \u0447\u0438\u0441\u043b\u0435. \u041f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u0442\u0435\u0441\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u0441\u0442 \u0410\u0434\u043b\u0435\u043c\u0430\u043d\u0430-\u041f\u043e\u043c\u0435\u0440\u0430\u043d\u0446\u0430-\u0420\u0443\u043c\u0435\u043b\u0438.<\/p>\n<\/li>\n<li>\n<p><strong>\u0423\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/strong> \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u043a \u043b\u044e\u0431\u044b\u043c \u0447\u0438\u0441\u043b\u0430\u043c, \u0430 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043a \u0447\u0438\u0441\u043b\u0430\u043c \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430. \u041f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u043d\u0435\u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u0441\u0442 \u041b\u044e\u043a\u0430-\u041b\u0435\u043c\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u041c\u0435\u0440\u0441\u0435\u043d\u043d\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0414\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c<\/strong> \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u0441\u0435\u0433\u0434\u0430 \u0432\u044b\u0434\u0430\u0451\u0442 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u043e\u0442\u0432\u0435\u0442 \u043d\u0430 \u043e\u0434\u043d\u0438\u0445 \u0438 \u0442\u0435\u0445 \u0436\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u0438\u043c\u0435\u0440\u043e\u043c \u043d\u0435\u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e (\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u043e\u0433\u043e) \u0442\u0435\u0441\u0442\u0430, \u043c\u043e\u0436\u0435\u0442 \u0441\u043b\u0443\u0436\u0438\u0442\u044c \u0442\u0435\u0441\u0442 \u041c\u0438\u043b\u043b\u0435\u0440\u0430-\u0420\u0430\u0431\u0438\u043d\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0411\u0435\u0437\u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u044c<\/strong> \u2014 \u044d\u0442\u043e \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0442 \u043d\u0435\u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0445 \u0433\u0438\u043f\u043e\u0442\u0435\u0437. \u041d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u0431\u0435\u0437\u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0441\u0442\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0435\u0441\u0442 \u041c\u0438\u043b\u043b\u0435\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u043f\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043e\u0431\u043e\u0431\u0449\u0451\u043d\u043d\u0443\u044e \u0433\u0438\u043f\u043e\u0442\u0435\u0437\u0443 \u0420\u0438\u043c\u0430\u043d\u0430.<\/p>\n<\/li>\n<\/ul>\n<h2>\u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f<\/h2>\n<p> &#8212; \u043a\u043e\u043b\u044c\u0446\u043e \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e n.<\/p>\n<p>\u0417\u0430\u043f\u0438\u0441\u044c  \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u044b, \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u0432\u044b\u0447\u0435\u0442\u044b \u0438\u0437 , \u0440\u0430\u0432\u043d\u044b.<\/p>\n<p>\u0417\u0430\u043f\u0438\u0441\u044c  \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u044b \u0441 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u0438\u0437  \u0440\u0430\u0432\u043d\u044b \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 .<\/p>\n<p> \u2014 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0447\u0438\u0441\u043b\u0430 n \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e r. \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e k, \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u043e .<\/p>\n<p> \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u042d\u0439\u043b\u0435\u0440\u0430. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043c\u0435\u043d\u044c\u0448\u0438\u0445 n \u0438 \u0432\u0437\u0430\u0438\u043c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0441 \u043d\u0438\u043c.<\/p>\n<p> \u2014 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044e \u0434\u0432\u0430 \u0447\u0438\u0441\u043b\u0430 n.<\/p>\n<h2>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f<\/h2>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u043f\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0442\u0435\u043e\u0440\u0435\u043c\u0443:<\/p>\n<p><strong>\u0422\u0435\u043e\u0440\u0435\u043c\u0430:<\/strong><br \/> \u0415\u0441\u043b\u0438 \u0447\u0438\u0441\u043b\u0430 a \u0438 n \u0432\u0437\u0430\u0438\u043c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u044b, \u0442\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e<\/p>\n<p>\u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u0433\u0434\u0430 \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e\u0433\u0434\u0430, \u043a\u043e\u0433\u0434\u0430 n \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435.<\/p>\n<p>\u042d\u0442\u043e \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e \u0443\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b. \u041d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c  \u043f\u0440\u043e\u0432\u0435\u0440\u043e\u043a \u2014 \u043f\u043e \u0447\u0438\u0441\u043b\u0443 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u0432 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u0445. \u0418\u0434\u0435\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430, \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043c\u0435\u043d\u044c\u0448\u0435\u0439, \u0447\u0435\u043c n. \u0418\u0437 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0432\u044b\u0442\u0435\u043a\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435:<\/p>\n<p><strong>\u0421\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435:<\/strong><br \/> \u0415\u0441\u043b\u0438 n \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u0442\u043e \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e r \u0438 \u043b\u044e\u0431\u043e\u0433\u043e \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e 0 &lt; a &lt; n \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f<\/p>\n<p>\u041e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0435\u0432\u0435\u0440\u043d\u043e. \u0412 \u0441\u0442\u0430\u0442\u044c\u0435 \u0438\u043d\u0434\u0438\u0439\u0441\u043a\u0438\u0445 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0432 \u0434\u043e\u043a\u0430\u0437\u0430\u043d\u043e, \u0447\u0442\u043e \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e r \u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 a \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0432\u0435\u0440\u043d\u043e:<\/p>\n<p><strong>\u0422\u0435\u043e\u0440\u0435\u043c\u0430:<\/strong><br \/> \u0415\u0441\u043b\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 r, \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u043e <\/p>\n<p>, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u043e <\/p>\n<p>\u0412\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 , \u0442\u043e n \u2014 \u043b\u0438\u0431\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u043b\u0438\u0431\u043e \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e.<\/p>\n<p>\u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443, \u0447\u0442\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u044b.<\/p>\n<h2>\u0422\u0435\u0441\u0442 AKS<\/h2>\n<h3>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/h3>\n<p><strong>\u0412\u0445\u043e\u0434:<\/strong> \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e n &gt; 1.<br \/> <strong>\u0412\u044b\u0445\u043e\u0434:<\/strong> \u041f\u0420\u041e\u0421\u0422\u041e\u0415, \u0435\u0441\u043b\u0438 n \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415 \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435.<\/p>\n<p><strong>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/strong><\/p>\n<ol>\n<li>\n<p>\u0415\u0441\u043b\u0438 n \u2014 \u0442\u043e\u0447\u043d\u0430\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 , \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430\u0439\u0442\u0438 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 r, \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u043e .<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 1 &lt; \u041d\u041e\u0414(a, n) &lt; n \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e , \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438  \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e : \u0415\u0441\u043b\u0438  \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0421\u041e\u0421\u0422\u0410\u0412\u041d\u041e\u0415.<\/p>\n<\/li>\n<li>\n<p>\u0412\u0435\u0440\u043d\u0443\u0442\u044c \u041f\u0420\u041e\u0421\u0422\u041e\u0415.<\/p>\n<\/li>\n<\/ol>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0448\u0430\u0433\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0447\u0438\u0441\u043b\u0430 47.<\/p>\n<h3>\u0428\u0430\u0433 1<\/h3>\n<p>\u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0448\u0430\u0433\u0435 \u043d\u0443\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0447\u0438\u0441\u043b\u043e n \u0442\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430, \u0442. \u0435. . \u041f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u2014 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e . \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f  (\u0442\u0430\u043a \u043a\u0430\u043a \u0435\u0441\u043b\u0438 <\/p>\n<p>, \u0442\u043e ) <\/p>\n<pre><code class=\"cpp\">function isPerfectPower(n) {     for (b = 2; b &lt; ceil(log(n)); b++) {         if (floor(n ** (1.0 \/ b)) ** b) == n:             return true;     }     return false; } <\/code><\/pre>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong> <\/p>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043e\u0442 2 \u0434\u043e 4:<\/p>\n<\/p>\n<\/p>\n<p>\u0421\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, 47 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430.<\/p>\n<h3>\u0428\u0430\u0433 2<\/h3>\n<p>\u041f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0435\u0435 r \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c. \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e r \u043d\u0443\u0436\u043d\u043e:<\/p>\n<ol>\n<li>\n<p>\u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e   \u0434\u043b\u044f \u0432\u0441\u0435\u0445 .<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u043e\u0434\u043d\u043e \u0438\u0437 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0440\u0430\u0432\u043d\u043e \u0435\u0434\u0438\u043d\u0438\u0446\u0435 \u2014 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 r.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0432\u0441\u0435 \u043d\u0435 \u0440\u0430\u0432\u043d\u044b \u0435\u0434\u0438\u043d\u0438\u0446\u0435 \u2014 r \u043d\u0430\u0439\u0434\u0435\u043d\u043e.<\/p>\n<\/li>\n<\/ol>\n<p>\u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0438\u0441\u043a\u043e\u043c\u043e\u0435 r \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 .<\/p>\n<pre><code class=\"cpp\">function findR(n) {     r = 2;      while (true) {         find = true;         for (k = 1; k &lt; ceil(log(n) ** 2); k++) {             if (n ** k % r == 1) {                 find = false;                 break             }         }                          if (find) {             return r;         } else {             r++;         }     }        } <\/code><\/pre>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong> <\/p>\n<p>\u0418\u0441\u043a\u043e\u043c\u043e\u0435 r = 41:<\/p>\n<\/p>\n<h3>\u0428\u0430\u0433\u0438 3-4<\/h3>\n<p>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u044b\u0435, \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u041d\u041e\u0414 \u0434\u0432\u0443\u0445 \u0447\u0438\u0441\u0435\u043b.<\/p>\n<h3>\u0428\u0430\u0433 5<\/h3>\n<p>\u0414\u043b\u044f \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u044f \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430\u043c\u0438. \u0417\u0434\u0435\u0441\u044c \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0434\u043d\u0443 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044e: \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0431\u0435\u0437 \u043f\u0440\u044f\u043c\u043e\u0433\u043e \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0415\u0441\u043b\u0438 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u0441\u0442\u0435\u043f\u0435\u043d\u0438  \u0432\u043e\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0442\u043e \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u0441\u0442\u0435\u043f\u0435\u043d\u0438 : <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430 :<br \/> , \u0433\u0434\u0435<\/p>\n<p>\u0420\u0430\u0441\u043a\u0440\u044b\u0432\u0430\u044f \u0441\u043a\u043e\u0431\u043a\u0438, \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b :<\/p>\n<pre><code class=\"cpp\">function mod (p) {     for (i = p.degree(); i &gt;= r; i--){         p[i - r] = p[i - r] + p[i];         p[i] = 0;     } } <\/code><\/pre>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong> <\/p>\n<\/p>\n<\/p>\n<h2>\u041e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438<\/h2>\n<p>\u0412\u0432\u0435\u0434\u0451\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435: , \u0433\u0434\u0435  \u2014 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u0442 n.<\/p>\n<p>\u041f\u0440\u0438 \u043e\u0446\u0435\u043d\u043a\u0430\u0445 \u0431\u0443\u0434\u0435\u043c \u043e\u043f\u0438\u0440\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 m-\u0431\u0438\u0442\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0438\u043c\u0435\u044e\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c . \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0430\u0434 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430\u043c\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 d \u0438\u043c\u0435\u044e\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c . \u041d\u041e\u0414 \u0434\u0432\u0443\u0445 m-\u0431\u0438\u0442\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0437\u0430 .<\/p>\n<p>\u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0448\u0430\u0433\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0447\u0438\u0441\u043b\u043e \u0442\u043e\u0447\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e, \u0438\u043c\u0435\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c .<\/p>\n<p>\u041d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u0448\u0430\u0433\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 r. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 r \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439  \u0434\u043b\u044f \u0432\u0441\u0435\u0445 . \u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e r \u044d\u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442  \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e r, \u0437\u043d\u0430\u0447\u0438\u0442 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e r \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c . \u0423\u0447\u0438\u0442\u044b\u0432\u0430\u044f, \u0447\u0442\u043e r \u0438\u043c\u0435\u0435\u0442 \u043f\u043e\u0440\u044f\u0434\u043e\u043a , \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u0448\u0430\u0433\u0430 \u0440\u0430\u0432\u043d\u0430 .<\/p>\n<p>\u0422\u0440\u0435\u0442\u0438\u0439 \u0448\u0430\u0433 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u041d\u041e\u0414 \u0434\u043b\u044f r \u0447\u0438\u0441\u0435\u043b. \u041e\u0431\u0449\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0448\u0430\u0433\u0430 .<\/p>\n<p>\u041d\u0430 \u043f\u044f\u0442\u043e\u043c \u0448\u0430\u0433\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c  \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432. \u041a\u0430\u0436\u0434\u043e\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442  \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0439 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 r, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043f\u043e\u0440\u044f\u0434\u043a\u0430 . \u041a\u0430\u0436\u0434\u043e\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u0435\u043d\u043e \u0437\u0430 . \u0418\u0442\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0448\u0430\u0433\u0430 .<\/p>\n<p>\u042d\u0442\u0443 \u043e\u0446\u0435\u043d\u043a\u0443 \u0438\u0437 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u043c\u043e\u0436\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c. \u041b\u0443\u0447\u0448\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 .<\/p>\n<h2>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435<\/h2>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c AKS \u0438\u043c\u0435\u0435\u0442 \u0432\u0430\u0436\u043d\u043e\u0435 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043e\u0434\u043d\u0430\u043a\u043e \u043d\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u043e\u043b\u0438\u043d\u043e\u043c \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043d \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438. \u0414\u0430\u0436\u0435 \u043f\u0440\u0438 \u043e\u0446\u0435\u043d\u043a\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430  \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0447\u0438\u0441\u043b\u0430 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 1024 \u0431\u0438\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u043a\u043e\u043b\u043e 1 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442\u0430 \u043f\u0430\u043c\u044f\u0442\u0438. \u0414\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043b\u0443\u0447\u0448\u0435 \u0432\u0441\u0435\u0433\u043e \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b.<\/p>\n<hr\/>\n<p><a href=\"https:\/\/t.me\/seregablogtg\" rel=\"noopener noreferrer nofollow\">\u041a\u0430\u043d\u0430\u043b<\/a> \u0441 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430\u043c\u0438.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \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\/855792\/\"> https:\/\/habr.com\/ru\/articles\/855792\/<\/a><br \/><\/br><\/br><\/p>\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-437598","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/437598","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=437598"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/437598\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=437598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=437598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=437598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}