{"id":328531,"date":"2022-01-24T21:00:33","date_gmt":"2022-01-24T21:00:33","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=328531"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=328531","title":{"rendered":"<span>\u0417\u043d\u0430\u043a\u043e\u043c\u0441\u0442\u0432\u043e \u0441 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438. \u0427\u0430\u0441\u0442\u044c 2, \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p><img decoding=\"async\" src=\"\/img\/image-loader.svg\" data-src=\"https:\/\/habrastorage.org\/webt\/7z\/6t\/mb\/7z6tmbsyyurtyn8g_bcx8mmmtxk.png\"\/><\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u0430 \u0447\u0430\u0441\u0442\u044c \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442 \u043d\u0435\u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0441\u0441\u043a\u0430\u0437 \u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u043b\u0430\u0445 \u0438 \u043e\u043d\u0430 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0430\u0441\u043f\u0435\u043a\u0442\u0430\u043c \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u044d\u0442\u043e\u0439 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u0438, \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0434\u0435\u0442\u0430\u043b\u044f\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0430\u043b\u0433\u0435\u0431\u0440\u044b \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Haskell. \u041e \u0442\u043e\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u0437\u0430 \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0438 \u0437\u0430\u0447\u0435\u043c \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f, \u0447\u0438\u0442\u0430\u0439\u0442\u0435 \u0432 <a href=\"https:\/\/habr.com\/ru\/post\/645939\/\">\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u0438<\/a>.<\/p>\n<p>  <\/p>\n<p>\u041c\u044b \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e\u0431 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u043c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b, \u043e \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0438 \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043d\u0438\u043c\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043e \u0434\u0432\u0443\u0445 \u043a\u043b\u0430\u0441\u0441\u043d\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u0445 \u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0442\u0438\u043f\u043e\u0432 \u044f\u0437\u044b\u043a\u0430 Haskell: \u043e \u0442\u0438\u043f\u0430\u0445-\u043b\u0438\u0442\u0435\u0440\u0430\u043b\u0430\u0445 (type literals) \u0438 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430\u0445 \u0442\u0438\u043f\u043e\u0432 (type families).<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<h2 id=\"kak-gotovit-p-adicheskie-chisla-recepty-i-hitrosti\">\u041a\u0430\u043a \u0433\u043e\u0442\u043e\u0432\u0438\u0442\u044c p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430. \u0420\u0435\u0446\u0435\u043f\u0442\u044b \u0438 \u0445\u0438\u0442\u0440\u043e\u0441\u0442\u0438.<\/h2>\n<p>  <\/p>\n<p>\u0427\u0430\u0449\u0435 \u0432\u0441\u0435\u0433\u043e, \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u0434\u0435\u043b\u043e \u0441 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0432 \u0438\u0445 \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0438, \u0442\u043e \u0435\u0441\u0442\u044c, \u0432 \u0432\u0438\u0434\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0446\u0438\u0444\u0440, \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e, \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439. \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0438\u0441\u043a\u0443\u0448\u0435\u043d\u0438\u0435 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0438\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u043e, \u043a\u0430\u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 (\u043c\u0430\u0441\u0441\u0438\u0432\u044b, \u0432\u0435\u043a\u0442\u043e\u0440\u044b \u0438\u043b\u0438 \u0441\u043f\u0438\u0441\u043a\u0438) \u0446\u0438\u0444\u0440, \u0430 \u0432\u0441\u044e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043f\u043e\u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e. \u042d\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u0443\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u043e \u043d\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e. <\/p>\n<p>  <\/p>\n<p>\u041c\u044b \u0443\u0436\u0435 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u043e\u0434\u043a\u043e\u0432\u0430\u043d\u044b \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c, \u0447\u0442\u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u2014 \u044d\u0442\u043e, \u0432\u0441\u0451-\u0442\u0430\u043a\u0438, \u043d\u0435 \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0446\u0438\u0444\u0440, \u0430 \u0447\u0438\u0441\u043b\u043e\u0432\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430. \u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435 \u0432\u0441\u0435\u0433\u043e \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441 \u0446\u0435\u043b\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438, \u0438 \u0432 \u0440\u043e\u043b\u0438 \u0441\u0438\u0441\u0442\u0435\u043c\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u0439 \u043a\u043e\u043b\u044c\u0446\u043e \u0446\u0435\u043b\u044b\u0445 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u043e\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fce\/525\/2bd\/fce5252bde946816c2cf744d932890f7.svg\" alt=\"$k$\" data-tex=\"inline\"\/> \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432, \u043c\u043e\u0436\u0435\u0442 \u0432\u044b\u0441\u0442\u0443\u043f\u0430\u0442\u044c \u043a\u043e\u043b\u044c\u0446\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0435 \u043e\u0431\u044b\u0447\u043d\u044b\u0435 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0441 \u043e\u0431\u044b\u0447\u043d\u043e\u0439 \u043c\u043e\u0434\u0443\u043b\u044f\u0440\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u043e\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432\u043c\u0435\u0441\u0442\u043e &#171;\u0447\u0435\u0441\u0442\u043d\u044b\u0445&#187; 2-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c 64-\u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0442\u0438\u043f\u0430 <code>Word64<\/code>, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f, \u043a\u0430\u043a \u0441 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u0435\u043b\u0435\u043c \u043a\u043e\u043b\u044c\u0446\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/941\/940\/12e\/94194012e615ce3f6268c05cebbc82d0.svg\" alt=\"$\\mathbb{Z}\/2^{64}\\mathbb{Z}$\" data-tex=\"inline\"\/>. \u0422\u0430\u043a\u0436\u0435 7-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u0430\u043a \u0447\u0438\u0441\u043b\u0430 \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c\u044b\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/19f\/eb5\/faf\/19feb5faf141ce216902597ff8674243.svg\" alt=\"$7^{22}$\" data-tex=\"inline\"\/>, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u043e\u0436\u0435 \u0432\u0441\u0435 \u043f\u043e\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432 <code>Word64<\/code>.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443, \u043f\u043e\u043d\u0438\u0436\u0430\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a3f\/531\/f02\/a3f531f021c91b1127ad360bcee2feee.svg\" alt=\"$\\mathbb{Z}_p$\" data-tex=\"inline\"\/> \u0434\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u043c\u044b \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u0435\u043c\u0441\u044f \u043b\u0438\u0448\u044c \u043f\u0435\u0440\u0432\u043e\u0439 \u0446\u0438\u0444\u0440\u043e\u0439 \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b62\/676\/c15\/b62676c15a464f4e3405f660dbce2c57.svg\" alt=\"$\\mathbb{Z}_{p^k}$\" data-tex=\"inline\"\/>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0435 \u0438\u0437\u043e\u043c\u043e\u0440\u0444\u0438\u0437\u043c\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u043c\u0438 \u0441\u0438\u0441\u0442\u0435\u043c\u0430\u043c\u0438, \u0443\u043f\u043e\u043c\u044f\u043d\u0443\u0442\u044b\u0445 \u0432 \u043f\u0435\u0440\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0441\u0442\u0430\u0442\u044c\u0438, \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435, \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0434\u0430\u0436\u0435 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u043f\u0435\u0440\u0432\u043e\u0439 \u0446\u0438\u0444\u0440\u044b \u0431\u0443\u0434\u0435\u0442 \u0432 \u043f\u043e\u043b\u043d\u043e\u0439 \u043c\u0435\u0440\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c. \u0410 \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0442\u043e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u0441 \u043d\u0438\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c <a href=\"http:\/\/gmplib.org\/\" rel=\"nofollow noopener noreferrer\">GMP<\/a> \u0438\u043b\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0435\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u0441\u0442\u043e\u0438\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 (\u0438 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u0438 \u0442\u0440\u0430\u043d\u0441\u0446\u0435\u043d\u0434\u0435\u043d\u0442\u043d\u044b\u0435) \u043a\u0430\u043a \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0446\u0435\u043b\u044b\u0435, \u0432\u0441\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e39\/bc9\/382\/e39bc938278ff24fa2bb42551eaf2e55.svg\" alt=\"$p^k$\" data-tex=\"inline\"\/>.<\/p>\n<p>  <\/p>\n<p>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0441\u0442\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043e\u0441\u043e\u0437\u043d\u0430\u043d\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0447\u0438\u0441\u0435\u043b. \u0418 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043e\u0442 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u043d\u044b\u0445 \u0441 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e, \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/> \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043e\u0431\u0440\u0430\u0442\u043d\u043e \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043f\u043e-\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438, \u043d\u0435 \u043f\u043e\u0442\u0435\u0440\u044f\u0442\u044c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0435. <\/p>\n<p>  <\/p>\n<p>\u0412 \u043d\u0430\u0448\u0435\u043c \u043a\u043e\u043d\u0442\u0435\u043a\u0441\u0442\u0435 <strong>\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c<\/strong> \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435 \u0447\u0438\u0441\u043b\u043e\u043c \u0437\u043d\u0430\u0447\u0430\u0449\u0438\u0445 \u0446\u0438\u0444\u0440 \u0434\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u0430 <strong>\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u044b\u043c\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044f \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f \u0434\u0440\u043e\u0431\u0438<\/strong>, \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0430\u044e\u0449\u0435\u0439 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u044c\u0441\u044f \u0434\u0440\u043e\u0431\u044f\u043c\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044c \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u044e\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/532\/3bd\/b07\/5323bdb07477909199bcd04b83c3fa7b.svg\" alt=\"$1000$\" data-tex=\"inline\"\/>, \u0430 \u0434\u043b\u044f \u0431\u043e\u043b\u0435\u0435 \u0442\u043e\u0447\u043d\u044b\u0445 \u0440\u0430\u0441\u0447\u0435\u0442\u043e\u0432 \u043f\u043e\u0432\u044b\u0441\u0438\u0442\u044c \u0432\u0435\u0440\u0445\u043d\u044e\u044e \u0433\u0440\u0430\u043d\u0438\u0446\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0445 \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u0435\u0439 \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u0435\u0439, \u0441\u043a\u0430\u0436\u0435\u043c, \u0434\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u043c\u043e\u0433\u043e \u0442\u0438\u043f\u043e\u043c <code>Word64<\/code> \u2014 \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3bc\/ee2\/aaa\/3bcee2aaac9434bf3c2af6958f1133e3.svg\" alt=\"$2^{64} \\approx 10^{20}$\" data-tex=\"inline\"\/>.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438\u0432\u0435\u0434\u0443 \u0434\u0432\u0430 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u0447\u0438\u0441\u0435\u043b \u0438\u0437 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cc5\/cde\/2c9\/cc5cde2c9093a27c681dfb76c28edccb.svg\" alt=\"$\\mathbb{Q}$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f25\/f7d\/0da\/f25f7d0dad995a4ad66d5369f8068fb3.svg\" alt=\"$\\mathbb{Q}_p$\" data-tex=\"inline\"\/> \u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442.<\/p>\n<p>  <\/p>\n<h3 id=\"otobrazhenie-racionalnogo-chisla-v-p-adicheskoe\">\u041e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0432 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0435<\/h3>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e3\/b52\/4c6\/1e3b524c6d52de5ad303dae07c92b41d.svg\" alt=\"$x = \\frac{r}{s}$\" data-tex=\"inline\"\/> \u0438\u0437 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cc5\/cde\/2c9\/cc5cde2c9093a27c681dfb76c28edccb.svg\" alt=\"$\\mathbb{Q}$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/> \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8bc\/837\/5dc\/8bc8375dc6b8abeff08d6da9da469b5d.svg\" alt=\"$s$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u0442\u043e \u0435\u0441\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dd3\/2eb\/14b\/dd32eb14ba5885f644e46a868b82d98f.svg\" alt=\"$q = s^{-1}$\" data-tex=\"inline\"\/>, \u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0f7\/e9a\/3e4\/0f7e9a3e43f60aa878bae8edb0c3218d.svg\" alt=\"$q\\cdot s \\equiv 1 \\mod p^k$\" data-tex=\"inline\"\/>. \u042d\u0442\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0415\u0432\u043a\u043b\u0438\u0434\u0430 \u0438\u043b\u0438 \u0447\u0435\u0440\u0435\u0437 \u0446\u0435\u043f\u043d\u044b\u0435 \u0434\u0440\u043e\u0431\u0438, \u0435c\u043b\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6cb\/948\/e3a\/6cb948e3a471983b96336805b80910ba.svg\" alt=\"$\\gcd(s, p) = 1$\" data-tex=\"inline\"\/>. <\/p>\n<p>  <\/p>\n<p>\u0412\u043e\u0442 \u043a\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043e\u043a\u0440\u0443\u0433\u043b\u0451\u043d\u043d\u043e\u0433\u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u0431\u0440\u0430\u0437\u0430 \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ace\/020\/484\/ace020484081e0f096829d9a35661133.svg\" alt=\"$x \\in Q$\" data-tex=\"inline\"\/>, \u043a\u0430\u043a \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>:<\/p>\n<p>  <\/p>\n<p><em>\u0412\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u0438\u0437 \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044f \u0438\u043b\u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a7d\/f0b\/0cf\/a7df0b0cf52583a7326d63832fe3d4ed.svg\" alt=\"$p$\" data-tex=\"inline\"\/>, \u0442\u043e \u0435\u0441\u0442\u044c, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0445\u043e\u0434\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043a\u0430\u043a \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9f4\/b6e\/475\/9f4b6e475e3b9119bc2b3ffc7a5d47a8.svg\" alt=\"$x = \\frac{r}{s}\\cdot p^v.$\" data-tex=\"display\"\/><\/p>\n<p><\/em><\/p>\n<p>  \u0415\u0441\u043b\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/405\/aa3\/ab4\/405aa3ab4aebab19d1c0a4d59877612b.svg\" alt=\"$\\gcd(s, p) = c \\neq 1$\" data-tex=\"inline\"\/>, \u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a7d\/f0b\/0cf\/a7df0b0cf52583a7326d63832fe3d4ed.svg\" alt=\"$p$\" data-tex=\"inline\"\/> \u0432 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u0435: <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dbd\/aa0\/69e\/dbdaa069e63cf2ffc8826f60ed2f6eaa.svg\" alt=\"$x = \\frac{p^{v'}}{p^{v'}} \\frac{c^{v'}}{c^{v'}}\\frac{r}{s} \\cdot p^{v} = \\frac{r\\cdot (p\/c)^{v'}}{s \/ c^{v'}}\\cdot p^{(v-v')}.$\" data-tex=\"display\"\/><\/p>\n<p>  \u041f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u0430\u044f \u0434\u0440\u043e\u0431\u044c \u0431\u0443\u0434\u0435\u0442 \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a3f\/531\/f02\/a3f531f021c91b1127ad360bcee2feee.svg\" alt=\"$\\mathbb{Z}_p$\" data-tex=\"inline\"\/>. \u0414\u043b\u044f \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/999\/5ef\/744\/9995ef7440026c7248ac1dc97c94a8e7.svg\" alt=\"$q = s^{-1} \\mod p^k$\" data-tex=\"inline\"\/> \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u044b\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c \u0415\u0432\u043a\u043b\u0438\u0434\u0430 \u0438\u043b\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u0447\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439, \u043d\u0430\u043f\u043e\u0434\u043e\u0431\u0438\u0435 <code>mpz_invert<\/code> \u0438\u0437 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 GMP.<br \/>  \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0431\u0443\u0434\u0435\u0442 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0441 \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8f4\/071\/c90\/8f4071c90968edfa8e7a80d0b4cb0ae6.svg\" alt=\"$u = r\\cdot q$\" data-tex=\"inline\"\/> \u0438 \u043f\u043e\u0440\u044f\u0434\u043a\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2ac\/211\/43d\/2ac21143d39638d2322c66f487d3efb6.svg\" alt=\"$v$\" data-tex=\"inline\"\/> .  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<p>\u041d\u0430\u0439\u0434\u0451\u043c \u043e\u0431\u0440\u0430\u0437 \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ea8\/d42\/7ae\/ea8d427aee59e53d0b14d627f754b14f.svg\" alt=\"$x = 637\/880$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9ee\/d00\/7ba\/9eed007ba6b44d165c1676c8a3ac8221.svg\" alt=\"$\\mathbb{Z}_7$\" data-tex=\"inline\"\/> \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u0435\u0437 \u043f\u043e\u0442\u0435\u0440\u0438 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0441 \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u0435\u043c \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u0435\u043c, \u0438\u043c\u0435\u044e\u0449\u0438\u043c\u0438 \u0442\u0438\u043f <code>Word16<\/code>.<\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u0439\u0434\u0451\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0443\u044e \u0434\u043b\u044f \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f: <\/p>\n<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2c7\/5f2\/687\/2c75f2687ec58d23c6fbfbd6b1181c42.svg\" alt=\"$(2^{16})^2 &lt; 7^k \/ 2 \\Longrightarrow k \\geq 33\\cdot \\log_7 2 \\approx 12,$\" data-tex=\"display\"\/><\/p>\n<p>  \u0437\u043d\u0430\u0447\u0438\u0442, \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8b2\/40f\/808\/8b240f808a4c3f58de0978aa134fb92c.svg\" alt=\"$7^{12} = 13841287201$\" data-tex=\"inline\"\/> \u0438 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0438\u0437 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u044d\u0442\u043e\u0433\u043e \u043a\u043e\u043b\u044c\u0446\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u0442\u0438\u043f\u0430 <code>Word32<\/code>.  <\/p>\n<p>\u0412\u044b\u0434\u0435\u043b\u0438\u043c \u0438\u0437 \u0447\u0438\u0441\u043b\u0430 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e8b\/4f4\/028\/e8b4f4028277053ab6831d602930c371.svg\" alt=\"$x = 7^2\\cdot 13\/880$\" data-tex=\"inline\"\/>, \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0438\u0441\u043b\u043e \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u043f\u043e\u0440\u044f\u0434\u043e\u043a <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c37\/24c\/45a\/c3724c45ab9dcf8945e6bcece2165788.svg\" alt=\"$2$\" data-tex=\"inline\"\/>. \u041d\u0430\u0439\u0434\u0451\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/349\/ab7\/695\/349ab769577dae51f951f13a121ad8f2.svg\" alt=\"$880^{-1} = 1242570101 \\mod 7^{12}$\" data-tex=\"inline\"\/>.<br \/>  \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u0431\u0440\u0430\u0437\u0430:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fe0\/438\/c01\/fe0438c014f55b3bbc580aed8cbb0db9.svg\" alt=\"$u = 13 \\cdot 1242570101 = 2312124112 \\mod 7^{12}.$\" data-tex=\"display\"\/><\/p>\n<p>  \u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18b\/682\/766\/18b6827669cea0808c13d6958ee835a5.svg\" alt=\"$x = u\\cdot 7^2.$\" data-tex=\"display\"\/><\/p>\n<\/div><\/div>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u043e\u0433\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<p>\u041d\u0430\u0439\u0434\u0451\u043c \u043e\u0431\u0440\u0430\u0437 \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ea8\/d42\/7ae\/ea8d427aee59e53d0b14d627f754b14f.svg\" alt=\"$x = 637\/880$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/81e\/8f1\/681\/81e8f1681a949695cd7beae7b4a663ce.svg\" alt=\"$\\mathbb{Z}_{10}$\" data-tex=\"inline\"\/>, \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0441\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u0439\u0434\u0451\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0443\u044e \u0434\u043b\u044f \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0435\u043d\u0438\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f: <\/p>\n<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4d7\/ca4\/b42\/4d7ca4b4219f743cc5b8952da69856f2.svg\" alt=\"$(2^{16})^2 &lt; 10^k \/ 2 \\Longrightarrow k \\geq 33\\cdot \\log_{10} 2 \\approx 10,$\" data-tex=\"display\"\/><\/p>\n<p>  \u0437\u043d\u0430\u0447\u0438\u0442 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f6a\/c3f\/55a\/f6ac3f55af9687a2a9be9fb7bf9936bc.svg\" alt=\"$10^{10}$\" data-tex=\"inline\"\/> \u0438 \u043d\u0430\u043c \u043e\u043f\u044f\u0442\u044c \u0445\u0432\u0430\u0442\u0438\u0442 \u0442\u0438\u043f\u0430 <code>Word32<\/code> \u0434\u043b\u044f \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f.  <\/p>\n<p>\u0412\u044b\u0434\u0435\u043b\u0438\u043c \u0438\u0437 \u0447\u0438\u0441\u043b\u0430 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/420\/f60\/ec0\/420f60ec001be8c12096c319f2f7191c.svg\" alt=\"$x = 10^{-1}\\cdot 637\/88$\" data-tex=\"inline\"\/>. \u041e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0438 \u0438\u043c\u0435\u0435\u0442 \u0441\u043e \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u0435\u043c \u043e\u0431\u0449\u0438\u0439 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c37\/24c\/45a\/c3724c45ab9dcf8945e6bcece2165788.svg\" alt=\"$2$\" data-tex=\"inline\"\/>. \u0417\u043d\u0430\u0447\u0438\u0442, \u0434\u0440\u043e\u0431\u044c \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u0442\u044c, \u0438\u0437\u0431\u0430\u0432\u0438\u0432\u0448\u0438\u0441\u044c \u043e\u0442 \u043d\u0435\u0433\u043e. <\/p>\n<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ee9\/23c\/180\/ee923c180cbd75fcd728d4584641b96c.svg\" alt=\"$x = \\frac{637}{88}\\cdot 10^{-1} = \\frac{(10\/2)^3 \\cdot 637}{88\/ 2^3}\\cdot 10^{-1-3} = \\frac{5^3 \\cdot 637}{11}\\cdot 10^{-4}.$\" data-tex=\"display\"\/><\/p>\n<p>  \u041d\u0430\u0439\u0434\u0451\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0434\u043b\u044f \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cf0\/5fb\/fc3\/cf05fbfc3fda8f6837cf2d04986b7cf9.svg\" alt=\"$11^{-1} = 9090909091 \\mod 10^{10}$\" data-tex=\"inline\"\/> \u0438 \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u0431\u0440\u0430\u0437\u0430 <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ba1\/442\/3b6\/ba14423b68fecaf8466b25bc323a5ada.svg\" alt=\"$u = 5^3\\cdot 637 \\cdot 9090909091 = 3636370875 \\mod 10^{10}.$\" data-tex=\"display\"\/><\/p>\n<p>  \u041a\u0441\u0442\u0430\u0442\u0438, \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043c\u044b \u0441\u0440\u0430\u0437\u0443 \u043c\u043e\u0436\u0435\u043c \u0437\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0435\u0433\u043e \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435: <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/36a\/a97\/74c\/36aa9774ccc2c8a6ec8581d98c52204e.svg\" alt=\"$x = u \\cdot 10^{-4} = ...363637.0875_{10}$\" data-tex=\"display\"\/><\/p>\n<p>  <\/div>\n<\/p><\/div>\n<p>  <\/p>\n<h3 id=\"vosstanovlenie-racionalnogo-chisla-iz-p-adicheskogo\">\u0412\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0438\u0437 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e<\/h3>\n<p>  <\/p>\n<p>\u041a\u0430\u043a \u043c\u044b \u0443\u0436\u0435 \u0433\u043e\u0432\u043e\u0440\u0438\u043b\u0438, \u0438\u0437-\u0437\u0430 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445, \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u0430\u044f \u0440\u0435\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430 \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0438 \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u043d\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043d\u0435 \u043f\u043e\u0440\u043e\u0436\u0434\u0430\u0435\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u0439, \u0441\u0445\u043e\u0434\u044f\u0449\u0435\u0439\u0441\u044f \u043a \u043a\u0430\u043a\u043e\u043c\u0443-\u0442\u043e \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443, \u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441\u043a\u043e\u0440\u0435\u0435, \u043a\u0430\u043a \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u043f\u0441\u0435\u0432\u0434\u043e\u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u041e\u0434\u043d\u0430\u043a\u043e, \u043a\u0430\u043a \u0432 1981 \u0433\u043e\u0434\u0443 \u043f\u043e\u043a\u0430\u0437\u0430\u043b \u041f\u043e\u043b \u0412\u0430\u043d\u0433, \u0435\u0441\u043b\u0438 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0430\u044f \u0440\u0435\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u0442\u043e \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u043d\u0430 \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0415\u0432\u043a\u043b\u0438\u0434\u0430, \u0431\u043e\u043b\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u043c, \u043a\u0430\u043a \u043c\u0435\u0442\u043e\u0434 \u041b\u0430\u0433\u0440\u0430\u043d\u0436\u0430 \u0434\u043b\u044f \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0431\u0430\u0437\u0438\u0441\u0430 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u0440\u0435\u0448\u0451\u0442\u043a\u0438. <\/p>\n<p>  <\/p>\n<p>\u0412\u043e\u0442 \u043a\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dab\/07a\/aad\/dab07aaadb1a6ba9ed90f074b3b2da3a.svg\" alt=\"$x = \\frac{r}{s}, r &lt; N, w &lt; D$\" data-tex=\"inline\"\/> \u0438\u0437 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430, \u043e\u043a\u0440\u0443\u0433\u043b\u0451\u043d\u043d\u043e\u0433\u043e \u0434\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fce\/525\/2bd\/fce5252bde946816c2cf744d932890f7.svg\" alt=\"$k$\" data-tex=\"inline\"\/> \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u043e\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/13e\/3ea\/680\/13e3ea680bc5e8456c1321bc791e4fab.svg\" alt=\"$n \\in \\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 (\u043d\u043e \u043d\u0435 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u0435) \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/76c\/0cb\/326\/76c0cb326718bc35bda47b7624ecddeb.svg\" alt=\"$p^k > 2ND$&#187; data-tex=&#187;inline&#187;\/>.<\/p>\n<p>  <\/p>\n<p><em>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0434\u0432\u0430 \u0432\u0435\u043a\u0442\u043e\u0440\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2cb\/476\/39b\/2cb47639bc7870cb419c6b81b3a1ce50.svg\" alt=\"$v = (p^k, 0),\\ w = (n, 1)$\" data-tex=\"inline\"\/>. \u041f\u043e\u043a\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f23\/1f5\/54a\/f231f554aff9abf7bffc8f2f6fcd9081.svg\" alt=\"$w_1 \\geq N$\" data-tex=\"inline\"\/> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5c9\/fab\/b83\/5c9fabb83000354f4b7eb90ad2bde344.svg\" alt=\"$w \\to v,\\quad v - \\left\\lfloor\\frac{v_1}{w_1}\\right\\rfloor w \\to w.$\" data-tex=\"display\"\/><\/p>\n<p><\/em><\/p>\n<p>  \u0415\u0441\u043b\u0438 \u043f\u043e \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u0438 \u0446\u0438\u043a\u043b\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8f7\/e01\/c7c\/8f7e01c7c8381bfc749383fc8b5ea9c6.svg\" alt=\"$w_2 &lt; D$\" data-tex=\"inline\"\/> \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/233\/98f\/b33\/23398fb3301a02d2f556521706a33e7d.svg\" alt=\"$\\gcd(w_1, w_2) = 1$\" data-tex=\"inline\"\/>, \u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0447\u0438\u0441\u043b\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8ba\/1ca\/648\/8ba1ca6486e927b0c1930f3aa749d598.svg\" alt=\"$x = w_1\/w_2$\" data-tex=\"inline\"\/>. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fce\/525\/2bd\/fce5252bde946816c2cf744d932890f7.svg\" alt=\"$k$\" data-tex=\"inline\"\/>.  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<p>\u0412\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1f7\/3a3\/0e2\/1f73a30e28de6364d690148310d58f79.svg\" alt=\"$13\/880$\" data-tex=\"inline\"\/> \u043f\u043e \u0435\u0433\u043e \u043e\u043a\u0440\u0443\u0433\u043b\u0451\u043d\u043d\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/567\/122\/0ce\/5671220cea7cd78f085d5769cf9c73d0.svg\" alt=\"$u = 2312124112 \\mod 7^{12}$\" data-tex=\"inline\"\/> \u0441 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b3a\/d5f\/87e\/b3ad5f87e34eba455514984a6f798a9e.svg\" alt=\"$2^{16}=65536$\" data-tex=\"inline\"\/> (\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044f \u0438 \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f)<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u0440\u043e\u0434\u0438\u0442 \u0446\u0435\u043f\u043e\u0447\u043a\u0443 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u0434\u043b\u044f \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2ac\/211\/43d\/2ac21143d39638d2322c66f487d3efb6.svg\" alt=\"$v$\" data-tex=\"inline\"\/> \u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/499\/78e\/f12\/49978ef12ee6820ac7fc4607771a3586.svg\" alt=\"$w$\" data-tex=\"inline\"\/>:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6b0\/4b9\/472\/6b04b9472576d881760472b049903d65.svg\" alt=\"$ \\begin{array} {} &amp;v &amp; w \\\\ {} &amp; (13841287201,0) &amp; (2312124112,1)\\\\ {} &amp; (2312124112,1) &amp; (2280666641,-5)\\\\ {} &amp; (2280666641,-5) &amp; (31457471,6) \\\\ {} &amp; (31457471,6) &amp; (13,880)\\qquad \\text{\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0438\u0433\u043d\u0443\u0442\u0430} \\end{array} $\" data-tex=\"display\"\/><\/p>\n<\/div><\/div>\n<p>  <\/p>\n<h3 id=\"lemma-genzelya\">\u041b\u0435\u043c\u043c\u0430 \u0413\u0435\u043d\u0437\u0435\u043b\u044f<\/h3>\n<p>  <\/p>\n<p>\u041e\u0434\u0438\u043d \u0438\u0437 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0432 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043c\u0438\u0440\u0435 \u0431\u044b\u043b \u043e\u043f\u0438\u0441\u0430\u043d \u0441\u0430\u043c\u0438\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u044d\u0442\u043e\u0439 \u0442\u0435\u043e\u0440\u0438\u0438 \u041a\u0443\u0440\u0442\u043e\u043c \u0413\u0435\u043d\u0437\u0435\u043b\u0435\u043c. \u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0435\u043b\u0430 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043a\u043e\u043b\u044c\u0446\u0430 \u0432\u044b\u0447\u0435\u0442\u043e\u0432, \u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0448\u043b\u0430 \u0440\u0435\u0447\u044c \u0432 \u043f\u0435\u0440\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0441\u0442\u0430\u0442\u044c\u0438, \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c \u043a\u043e \u0432\u0441\u0435\u0439 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0440\u0430\u0437\u0443, \u0430 \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u0441\u0440\u0435\u0434\u043e\u0442\u043e\u0447\u0438\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0435\u0451 \u0447\u0430\u0441\u0442\u0438: \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430\u0445 \u043a\u043e\u0440\u043d\u0435\u0439 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u041e\u043d \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0434\u043b\u044f \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/389\/3fd\/2ab\/3893fd2ab5bbb8ad1f3156dc8d8ffd35.svg\" alt=\"$f(x) = 0$\" data-tex=\"inline\"\/>, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043e\u0447\u0435\u043d\u044c \u043b\u0435\u0433\u043a\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0432 \u0441\u0430\u043c\u043e\u043c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u043c \u043a\u043e\u043b\u044c\u0446\u0435 \u0432\u044b\u0447\u0435\u0442\u043e\u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/d9d\/da8\/b58d9dda84c47d4747dc257813f6ee96.svg\" alt=\"$\\mathbb{Z}\/p\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u043f\u043e\u0432\u044b\u0441\u0438\u0442\u044c \u044d\u0442\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u043e \u043b\u044e\u0431\u043e\u0433\u043e \u043a\u043e\u043b\u044c\u0446\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0442\u0430\u043a\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442.<\/p>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0434\u043d\u044f\u0442\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/389\/3fd\/2ab\/3893fd2ab5bbb8ad1f3156dc8d8ffd35.svg\" alt=\"$f(x) = 0$\" data-tex=\"inline\"\/> \u0441 \u0446\u0435\u043b\u044b\u043c\u0438 (\u0438\u043b\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0446\u0435\u043b\u044b\u043c\u0438) \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043b\u0435\u043c\u043c\u044b \u0413\u0435\u043d\u0437\u0435\u043b\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c:<\/p>\n<p>  <\/p>\n<p><em>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/827\/6a3\/55d\/8276a355d254a55b0c1ba5d9cba3ff61.svg\" alt=\"$x_1$\" data-tex=\"inline\"\/> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/d9d\/da8\/b58d9dda84c47d4747dc257813f6ee96.svg\" alt=\"$\\mathbb{Z}\/p\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c, \u0435\u0441\u043b\u0438 \u043a\u043e\u043b\u044c\u0446\u043e \u0438\u043c\u0435\u0435\u0442 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a. \u041d\u0430 \u044d\u0442\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u043d\u0430\u0434\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u044d\u0442\u043e\u043c \u043a\u043e\u043b\u044c\u0446\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/261\/884\/715\/26188471511c09ca392f8b6c3ef08d6f.svg\" alt=\"$f'(x_1) \\neq 0$\" data-tex=\"inline\"\/>. \u0414\u043b\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1b0\/1c9\/86a\/1b01c986a85b3dc8fdccfa58555e2f58.svg\" alt=\"$0 &lt; m \\leq k$\" data-tex=\"inline\"\/>, \u0438\u043c\u0435\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fc3\/442\/9f4\/fc34429f4afcc17ec4b731cbe19ec1a8.svg\" alt=\"$x_k$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/> \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/994\/09f\/137\/99409f1376098b24d6052fadbd936801.svg\" alt=\"$x_{k+m}$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/af6\/7b2\/995\/af67b299570b4a87c227cb5f772fda33.svg\" alt=\"$\\mathbb{Z}\/p^{k+m}\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aa2\/258\/3cc\/aa22583cc5aa13b66cb01aa64523a57f.svg\" alt=\"$x_{k+m} = x_k - a\\cdot f(x_k)$\" data-tex=\"inline\"\/>, \u0433\u0434\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c03\/adc\/5a9\/c03adc5a91d52a6dc3390287adf3af44.svg\" alt=\"$a = f'(x_k) \\mod p^m$\" data-tex=\"inline\"\/>.<\/em><\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u043f\u043e\u0434\u043d\u044f\u0442\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<p>\u0420\u0435\u0448\u0438\u043c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9a1\/7a2\/2d2\/9a17a22d2b20f9161c5c9bd06e4a36d6.svg\" alt=\"$f(x) = x^2+1 = 0$\" data-tex=\"inline\"\/> \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5a5\/02d\/a5c\/5a502da5cff3a059a38106865af97b2f.svg\" alt=\"$\\mathbb{Z}_5$\" data-tex=\"inline\"\/> \u0441 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0434\u043e 10 \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0441\u0442\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u0432\u0430\u0435\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0438\u043c\u0435\u0435\u0442 \u0434\u0432\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c03\/8eb\/592\/c038eb592cb5dedf2082289e1ae77657.svg\" alt=\"$x_1 = \\pm 2$\" data-tex=\"inline\"\/> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7d5\/b57\/c58\/7d5b57c58a8409e69d5e810d5021f66e.svg\" alt=\"$\\mathbb{Z}\/5\\mathbb{Z}$\" data-tex=\"inline\"\/>. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u0434\u043d\u044f\u0442\u044c \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d42\/940\/67a\/d4294067ae90b6bb8f929d6c7a06b82c.svg\" alt=\"$\\mathbb{Z}\/5^{10}\\mathbb{Z}$\" data-tex=\"inline\"\/> \u0437\u0430 \u0447\u0435\u0442\u044b\u0440\u0435 \u0448\u0430\u0433\u0430: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/007\/398\/b1b\/007398b1b7dc42f6d2e6e5ab988a5577.svg\" alt=\"$5 \\to 5^2 \\to 5^3 \\to 5^5 \\to 5^{10}$\" data-tex=\"inline\"\/>.<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/634\/f76\/deb\/634f76deb3b7af2e9b68564525a6a15d.svg\" alt=\"$ \\begin{array} {} &amp; k=1 &amp; m = 1 &amp; f'(x_1)^{-1} = 4 \\mod 5 &amp; x_2 = x_1 - 4 f(x_1) = 7 \\mod 5^2\\\\ {} &amp; k=2 &amp; m = 1 &amp; f'(x_2)^{-1} = 4 \\mod 5 &amp; x_3 = x_2 - 4 f(x_2) = 57 \\mod 5^3\\\\ {} &amp; k=3 &amp; m = 2 &amp; f'(x_3)^{-1} = 9 \\mod 5^2 &amp; x_5 = x_3 - 9 f(x_3) = 2057 \\mod 5^5\\\\ {} &amp; k=5 &amp; m = 5 &amp; f'(x_5)^{-1} = 534 \\mod 5^5 &amp; x_{10} = x_5 - 534 f(x_5) = 6139557 \\mod 5^{10}\\\\ \\end{array} $\" data-tex=\"display\"\/><\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0435\u0432\u0435\u0441\u0442\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0434\u0435\u0441\u044f\u0442\u044c \u0446\u0438\u0444\u0440 \u0440\u0435\u0448\u0435\u043d\u0438\u044f:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/625\/b1a\/135\/625b1a1352a52f757f549a8be8b05b7b.svg\" alt=\"$x_{10} = ...3032431212_5$\" data-tex=\"display\"\/><\/p>\n<\/div><\/div>\n<p>  <\/p>\n<p>\u041f\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443, \u044d\u0442\u043e \u043c\u0435\u0442\u043e\u0434 \u041d\u044c\u044e\u0442\u043e\u043d\u0430, \u0445\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u0432 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u043c \u043c\u0438\u0440\u0435. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435, \u0435\u0441\u043b\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b, \u043a\u0430\u043a \u043a\u043e\u043b\u044c\u0446\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d1\/3a8\/3fa\/9d13a83fa1aa5220c320c680248681e5.svg\" alt=\"$\\mathbb{Z}\/p^k\\mathbb{Z}$\" data-tex=\"inline\"\/>, \u043f\u0440\u043e\u0449\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u043a\u043e\u0440\u043d\u0438 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u0432 \u044d\u0442\u043e\u043c \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u043a\u043e\u043b\u044c\u0446\u0435, \u0431\u0435\u0437 \u0432\u043e\u0437\u043d\u0438 \u0441 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u043c\u0438 \u043a\u043e\u043b\u044c\u0446\u0430\u043c\u0438. \u0413\u043b\u0430\u0432\u043d\u043e\u0435 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c, \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0441 \u043a\u043e\u0440\u043d\u0435\u0439, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0432 \u0431\u0430\u0437\u043e\u0432\u043e\u043c \u043a\u043e\u043b\u044c\u0446\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/d9d\/da8\/b58d9dda84c47d4747dc257813f6ee96.svg\" alt=\"$\\mathbb{Z}\/p\\mathbb{Z}$\" data-tex=\"inline\"\/>. <\/p>\n<p>  <\/p>\n<p>\u0421\u0430\u043c\u043e\u0435 \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u043c\u0435\u0442\u043e\u0434\u0430 \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0442\u0430\u043a\u0438\u043c \u0436\u0435, \u043a\u0430\u043a \u0438 \u043f\u0440\u0438 \u0440\u0443\u0447\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u043b\u0435\u043c\u043c\u044b \u0413\u0435\u043d\u0437\u0435\u043b\u044f, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043a\u043e\u0440\u044f\u0432\u0430\u044f \u0444\u0440\u0430\u043a\u0442\u0430\u043b\u044c\u043d\u0430\u044f p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u044f \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0442\u043e\u0442\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u0430 \u041d\u044c\u044e\u0442\u043e\u043d\u0430, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0432\u043e \u0432\u0441\u0435\u0445 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f\u0445 \u043f\u0440\u0438\u044f\u0442\u043d\u043e\u0439 \u0442\u043e\u043f\u043e\u043b\u043e\u0433\u0438\u0438 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0439 \u043f\u0440\u044f\u043c\u043e\u0439, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043f\u0440\u0438\u0442\u044f\u0436\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430 \u041d\u044c\u044e\u0442\u043e\u043d\u0430 \u0434\u0430\u0436\u0435 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0438\u043b\u0438 \u0442\u0440\u0435\u0442\u044c\u0435\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0443\u0436\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%91%D0%B0%D1%81%D1%81%D0%B5%D0%B9%D0%BD%D1%8B_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0\" rel=\"nofollow noopener noreferrer\">\u0444\u0440\u0430\u043a\u0442\u0430\u043b\u044c\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e<\/a>. \u0412\u043e\u0442 \u0442\u0430\u043a\u043e\u0439 \u0434\u0443\u0430\u043b\u0438\u0437\u043c.<\/p>\n<p>  <\/p>\n<h3 id=\"vychislenie-kvadratnyh-korney\">\u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0445 \u043a\u043e\u0440\u043d\u0435\u0439<\/h3>\n<p>  <\/p>\n<p>\u041a\u043e\u043b\u044c \u0441\u043a\u043e\u0440\u043e \u0432 \u043d\u0430\u0448\u0435\u043c \u0430\u0440\u0441\u0435\u043d\u0430\u043b\u0435 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u043c\u0435\u0442\u043e\u0434 \u041d\u044c\u044e\u0442\u043e\u043d\u0430, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0435 \u043a\u043e\u0440\u043d\u0438 (\u0435\u0441\u043b\u0438 \u043e\u043d\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442), \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0448\u0430\u0433 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u043e\u0433\u043e <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d7f\/904\/983\/d7f904983f79491abe2e85bf294fac84.svg\" alt=\"$x \\to (x + a\/x)\/2$\" data-tex=\"inline\"\/>. \u041e\u0434\u043d\u0430\u043a\u043e, \u043e\u043d \u0442\u043e\u0447\u043d\u043e \u043d\u0435 \u0441\u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/407\/e92\/e48\/407e92e488f21201b50212e9a5dbac0e.svg\" alt=\"$\\mathbb{Z}_2$\" data-tex=\"inline\"\/>, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u043d\u0430\u044f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1ad\/115\/b8a\/1ad115b8a46030fe2ad5e0f96fc4b96c.svg\" alt=\"$f(x) = x ^2 - a$\" data-tex=\"inline\"\/> \u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0440\u0430\u0432\u043d\u0430 \u043d\u0443\u043b\u044e \u043d\u0430 \u0432\u0441\u0451\u043c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8d2\/baa\/2ae\/8d2baa2aefa5468ae58477ab2e093dd5.svg\" alt=\"$\\mathbb{Z}\/2\\mathbb{Z}$\" data-tex=\"inline\"\/>. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434:<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0a4\/889\/702\/0a4889702c8f66d0fa4f3a4e9cee2729.svg\" alt=\"$\\sqrt{a} = g\\left(\\frac{a-1}{8}\\right),\\\\ g(x) = (1 + 4x) \\cdot g\\left[-2\\left(\\frac{x}{1 + 4x}\\right)^2\\right].$\" data-tex=\"display\"\/><\/p>\n<p>  <\/p>\n<p>\u041a\u0430\u0436\u0434\u044b\u0439 \u043d\u043e\u0432\u044b\u0439 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442 \u0434\u0432\u0435 \u043d\u043e\u0432\u044b\u0445 \u0432\u0435\u0440\u043d\u044b\u0435 \u0446\u0438\u0444\u0440\u044b \u0432 \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430.<\/p>\n<p>  <\/p>\n<p>\u0418\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0435\u0441\u0442\u044c \u0432\u043e \u043c\u043d\u043e\u0433\u0438\u0445 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u0430\u043a\u0435\u0442\u0430\u0445, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a Sage, Maple, Magma \u0438 \u0438\u043c \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445, \u043d\u0430 GitHub \u0432\u044b\u043b\u043e\u0436\u0435\u043d\u044b \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u0438\u0445 \u044f\u0437\u044b\u043a\u043e\u0432, \u0430 \u0442\u0435\u043f\u0435\u0440\u044c \u0442\u0430\u043a\u0430\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0435\u0441\u0442\u044c \u0438 \u0432 <a href=\"https:\/\/hackage.haskell.org\/package\/padic-0.1.0.0\/candidate\" rel=\"nofollow noopener noreferrer\">Hackage<\/a>. <\/p>\n<p>  <\/p>\n<h2 id=\"para-slov-o-biblioteke\">\u041f\u0430\u0440\u0430 \u0441\u043b\u043e\u0432 \u043e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0435<\/h2>\n<p>  <\/p>\n<p>\u0414\u043b\u044f Haskell \u0410\u043d\u0434\u0440\u0435\u0435\u043c \u041b\u0435\u043b\u0435\u0447\u0435\u043d\u043a\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u043e\u0442\u043b\u0438\u0447\u043d\u044b\u0439 \u043f\u0430\u043a\u0435\u0442 \u043c\u043e\u0434\u0443\u043b\u044f\u0440\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 <a href=\"https:\/\/hackage.haskell.org\/package\/mod\" rel=\"nofollow noopener noreferrer\">mod<\/a>, \u0441 \u043e\u0447\u0435\u043d\u044c \u0443\u0434\u043e\u0431\u043d\u044b\u043c \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u043e\u043c \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439. \u041e\u043d \u0438 \u043f\u043e\u0441\u043b\u0443\u0436\u0438\u043b \u043e\u0441\u043d\u043e\u0432\u043e\u0439 \u0434\u043b\u044f \u043c\u043e\u0435\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438. \u041a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u0446\u0438\u0444\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u043e\u0432\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u0435\u043b, \u0430 \u0432\u0441\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u043c\u043e\u0434\u0443\u043b\u044f\u0440\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0435.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u043e\u0439 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> :set -XDataKinds > 45 :: Z 5 -- \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0432 \u043f\u044f\u0442\u0438\u0440\u0438\u0447\u043d\u0443\u044e \u0437\u0430\u043f\u0438\u0441\u044c 140 > -45 :: Z 5 -- \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0432 \u0441\u043a\u043e\u0431\u043a\u0430\u0445 -- \u043f\u0435\u0440\u0438\u043e\u0434\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c (4)310 > toInteger it -- \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043b\u043e\u0435 \u0438\u0437 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 -45 > 13 \/ 7 :: Q 10 -- \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e (714285)9.0 > toRational it  13 % 7 > sqrt 11 :: Q 5 -- \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u2026231012244200433234102330200211.0 > sqrt 11 :: Z' 5 40 -- \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0441\u0442\u044c \u202600104441102231221020231012244200433234102330200211.0 > toRational (it ^ 2) -- \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u043a\u043e\u0440\u0435\u043d\u044c \u043d\u0430\u0439\u0434\u0435\u043d \u0432\u0435\u0440\u043d\u043e 11 % 1 > sin 49 :: Q 7 -- \u043f\u0440\u0438\u043c\u0435\u0440 \u0442\u0440\u0430\u043d\u0441\u0446\u0435\u043d\u0434\u0435\u043d\u0442\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u2026013021253020521111000100.0 > fromDigits [1,2,3,0,3,2,1] :: Z 4 -- \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0438\u0437 \u0446\u0438\u0444\u0440 1230321<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412\u0441\u0451 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0443\u0434\u043e\u0431\u043d\u043e \u0438 \u0438\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0438\u0440\u0443\u0435\u043c \u043d\u0430\u043a\u043e\u043f\u043b\u0435\u043d\u0438\u0435 \u043e\u0448\u0438\u0431\u043a\u0438 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 IEEE \u0438 \u0435\u0451 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0435 \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 10-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> iterate (1 \/ 3 + ) 0 !! 300000 :: Double 99999.99999968921 > iterate (1 `div` 3 + ) 0 !! 300000 :: Z 10 100000<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u043f\u0430\u043a\u0435\u0442\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0439, \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0438 \u0442\u0440\u0430\u043d\u0441\u0446\u0435\u043d\u0434\u0435\u043d\u0442\u043d\u044b\u0445, \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d \u043c\u0435\u0442\u043e\u0434 \u041d\u044c\u044e\u0442\u043e\u043d\u0430. \u0422\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f: <\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> henselLifting (\\x -> x^3 - 2*x +3) (\\x -> 3*x^2 -2) :: [Z 7] [\u2026106254154414566525205522]<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u043d\u0443\u044e \u043d\u0430\u0434\u043e \u0437\u0430\u0434\u0430\u0432\u0430\u0442\u044c \u044f\u0432\u043d\u043e, \u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0434\u0438\u0444\u0444\u0435\u0440\u0435\u043d\u0446\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u044f \u043d\u0435 \u0437\u0430\u0445\u043e\u0442\u0435\u043b \u0442\u0430\u0449\u0438\u0442\u044c \u0432 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0443\u0442\u044f\u0436\u0435\u043b\u044f\u0442\u044c \u0435\u0451 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438.<\/p>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 10-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u043e\u0440\u0444\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0438 \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u043a\u0430\u043a\u0443\u044e \u0431\u044b \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043c\u044b \u0438\u0445 \u043d\u0435 \u0432\u043e\u0437\u0432\u0435\u043b\u0438, \u043e\u043d\u0438 \u043e\u0441\u0442\u0430\u043d\u0443\u0442\u0441\u044f \u043d\u0435\u0438\u0437\u043c\u0435\u043d\u043d\u044b\u043c\u0438:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> aut = henselLifting (\\x -> x^2 - x) (\\x -> 2*x - 1) :: [Z 10] > aut [0,1,\u2026392256259918212890625,\u2026607743740081787109376] > and [ x == x^i | x &lt;- aut, i &lt;- [2..200] ] True<\/code><\/pre>\n<p>  <\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0435\u0449\u0451 \u0447\u0438\u0441\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u0448\u044c \u0432 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u043c \u043c\u0438\u0440\u0435: <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35b\/a56\/5f3\/35ba565f36734f3a55aa01ac67868762.svg\" alt=\"$n$\" data-tex=\"inline\"\/> \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043a\u043e\u0440\u043d\u0435\u0439 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35b\/a56\/5f3\/35ba565f36734f3a55aa01ac67868762.svg\" alt=\"$n$\" data-tex=\"inline\"\/>-\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0438\u0437 \u0435\u0434\u0438\u043d\u0438\u0446\u044b, \u043a\u0430\u043a \u0432 \u043a\u043e\u043c\u043f\u043b\u0435\u043a\u0441\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430\u0445 (\u043f\u0440\u0430\u0432\u0434\u0430, \u043e\u043d\u0438 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043d\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35b\/a56\/5f3\/35ba565f36734f3a55aa01ac67868762.svg\" alt=\"$n$\" data-tex=\"inline\"\/>).<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> unityRoots 3 :: [Q 7] [1.0,\u2026053116412125443426203642.0,\u2026613550254541223240463024.0] > (^3) &lt;$> it [1.0,1.0,1.0] > unityRoots 6 :: [Q 7] [1.0,\u2026053116412125443426203642.0,\u2026053116412125443426203643.0, \u2026613550254541223240463024.0,\u2026613550254541223240463025.0,(6).0] > (^6) &lt;$> it [1.0,1.0,1.0,1.0,1.0,1.0]<\/code><\/pre>\n<p>  <\/p>\n<p>\u041c\u0435\u0442\u043e\u0434\u043e\u043c \u0413\u0435\u043d\u0437\u0435\u043b\u044f \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u0438 \u0442\u0440\u0430\u043d\u0441\u0446\u0435\u043d\u0434\u0435\u043d\u0442\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0442\u043e\u0436\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432\u043e\u0442 7-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0441\u0438\u043d\u0443\u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0440\u0430\u0432\u0435\u043d <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c71\/10b\/1c6\/c7110b1c6d854dfac745f913869564d1.svg\" alt=\"$7^2$\" data-tex=\"inline\"\/>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> x = head $ henselLifting (\\x -> sin x - 7^2) cos :: Q 7 > x \u2026313125366542105556000100.0 > sin x 100.0 -- \u044d\u0442\u043e 49 \u0432 7-\u0440\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438.<\/code><\/pre>\n<p>  <\/p>\n<p>\u0418\u0437-\u0437\u0430 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f \u0432 \u0440-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u043b\u0430\u0445 \u0432 \u043d\u0438\u0445 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u043d\u0435\u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438, \u043f\u0440\u0430\u0432\u0434\u0430, \u0442\u043e\u043b\u044c\u043a\u043e \u0441 \u043c\u043b\u0430\u0434\u0448\u0438\u043c\u0438 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u043c\u0438, \u043d\u0430\u0438\u043c\u0435\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0430\u0449\u0438\u043c\u0438 \u0432 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u043c \u043c\u0438\u0440\u0435, \u043d\u043e \u0432 \u043c\u043e\u0434\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430\u0445 \u0438 \u043e\u043d\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b \u043d\u0435\u0441\u0442\u0438 \u043f\u043e\u043b\u0435\u0437\u043d\u0443\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0430\u043c \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u043e\u0441\u043e\u0431\u043e\u0433\u043e \u0442\u0440\u0443\u0434\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0437\u043d\u0430\u043c\u0435\u043d\u0438\u0442\u043e\u0433\u043e <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%93%D1%80%D1%8D%D0%BC%D0%B0\" rel=\"nofollow noopener noreferrer\">\u0447\u0438\u0441\u043b\u0430 \u0413\u0440\u044d\u043c\u0430<\/a>. \u041e\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u0442.\u043d. \u0433\u0438\u043f\u0435\u0440\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u2014 \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043e\u0434\u043d\u0443 \u0438\u0437 \u043d\u0438\u0445 \u2014 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D0%B5%D1%82%D1%80%D0%B0%D1%86%D0%B8%D1%8F\" rel=\"nofollow noopener noreferrer\">\u0442\u0435\u0442\u0440\u0430\u0446\u0438\u044e<\/a>, \u0442\u043e \u0435\u0441\u0442\u044c \u0431\u0430\u0448\u043d\u044e \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0439 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c <code>a ^^^ b = a ^ (a ^ (a ... a ^ a))<\/code> \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0443\u044e \u0438\u0437 <code>b<\/code> \u044d\u0442\u0430\u0436\u0435\u0439.<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">(^^^) :: Radix p prec => Z' p prec -> Z' p prec -> Z' p prec  a ^^^ 0 = 1 a ^^^ 1 = a a ^^^ b = a `zPow` (a ^^^ (b - 1))<\/code><\/pre>\n<p>  <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044f <code>zPow<\/code> \u2014 \u044d\u0442\u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u043b\u044f \u043a\u043e\u043b\u044c\u0446\u0430 \u0446\u0435\u043b\u044b\u0445 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b. \u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0431\u044b\u0441\u0442\u0440\u043e \u0441\u0442\u0430\u043d\u043e\u0432\u044f\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u043c\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438, \u0447\u0442\u043e \u0432 \u043e\u0431\u044b\u0447\u043d\u044b\u0445 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430\u0445 \u0441 \u043d\u0438\u043c\u0438 \u0443\u0436\u0435 \u043d\u0435 \u043f\u043e\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0448\u044c, \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u043a \u0432 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u0437\u0430\u043d\u0438\u043c\u0430\u044e\u0442 \u0441\u043a\u043e\u043b\u044c-\u043d\u0438\u0431\u0443\u0434\u044c \u0437\u0430\u043c\u0435\u0442\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438. <\/p>\n<p>  <\/p>\n<p>\u0427\u0438\u0441\u043b\u043e \u0413\u0440\u044d\u043c\u0430 \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0442\u0435\u0442\u0440\u0430\u0446\u0438\u0438 \u0442\u0440\u043e\u0439\u043a\u0438. \u041d\u0435\u0442\u0440\u0443\u0434\u043d\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/db4\/4c6\/562\/db44c65623b39f79dafb11efe0bc85d0.svg\" alt=\"$a _i = 3 \\text{^^^} i$\" data-tex=\"inline\"\/> \u0441\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/81e\/8f1\/681\/81e8f1681a949695cd7beae7b4a663ce.svg\" alt=\"$\\mathbb{Z}_{10}$\" data-tex=\"inline\"\/> \u043a \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u0435\u043b\u044c\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2c0\/15d\/be9\/2c015dbe906482458db9dcca823671e0.svg\" alt=\"$\\mathscr{G}$\" data-tex=\"inline\"\/>, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0435\u0448\u0430\u0435\u0442 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cdb\/ae3\/411\/cdbae34119b6ef9345e8f896a2b863fb.svg\" alt=\"$3^\\mathscr{G} = \\mathscr{G}$\" data-tex=\"inline\"\/>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> \u03bb> 3 ^^^ 2 :: Z 10 27 \u03bb> 3 ^^^ 3 :: Z 10 7625597484987 \u03bb> 3 ^^^ 4 :: Z 10 \u2026206738945776100739387 \u03bb> 3 ^^^ 5 :: Z 10 \u2026315006939489660355387 \u03bb> 3 ^^^ 6 :: Z 10 \u2026913333445425126595387 \u03bb> 3 ^^^ 10 :: Z 10 \u2026254100942846464195387 \u03bb> 3 ^^^ 100 :: Z 10 \u2026104575627262464195387 \u03bb> g = 3 ^^^ 1000 :: Z 10 \u2026104575627262464195387<\/code><\/pre>\n<p>  <\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0435\u043b\u0430 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043a\u0430\u043a\u0443\u044e \u0431\u044b \u043e\u0433\u0440\u043e\u043c\u043d\u0443\u044e \u0431\u0430\u0448\u043d\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439 \u0442\u0440\u043e\u0439\u043a\u0438 \u043c\u044b \u0431\u044b \u043d\u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043b\u0438 (\u0430 \u0434\u043b\u044f \u0447\u0438\u0441\u043b\u0430 \u0413\u0440\u044d\u043c\u0430 \u043e\u043d\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0447\u0438\u0441\u043b\u043e \u043f\u043b\u0430\u043d\u043a\u043e\u0432\u0441\u043a\u0438\u0445 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0439, \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u0432 \u0434\u0438\u0430\u043c\u0435\u0442\u0440 \u0432\u0438\u0434\u0438\u043c\u043e\u0439 \u0412\u0441\u0435\u043b\u0435\u043d\u043d\u043e\u0439), \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2c0\/15d\/be9\/2c015dbe906482458db9dcca823671e0.svg\" alt=\"$\\mathscr{G}$\" data-tex=\"inline\"\/>! \u0412 \u0440\u0443\u0441\u0441\u043a\u043e\u044f\u0437\u044b\u0447\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0438\u0437 \u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u0441\u044f 50 \u043c\u043b\u0430\u0434\u0448\u0438\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432 \u0447\u0438\u0441\u043b\u0430 \u0413\u0440\u044d\u043c\u0430. \u0420\u0430\u0431\u043e\u0442\u0430\u044f \u0432 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0435, \u043c\u044b \u043b\u0435\u0433\u043a\u043e \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0445\u043e\u0442\u044c 50, \u0445\u043e\u0442\u044c 100 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u0446\u0438\u0444\u0440 \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u043d\u0441\u0442\u0440\u0430:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> g = 3 ^^^ 1000 :: Z' 10 100 > g \u20269404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387 > 3 `zPow` g == g True<\/code><\/pre>\n<p>  <\/p>\n<h2 id=\"nekotorye-detali-realizacii\">\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0435\u0442\u0430\u043b\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438<\/h2>\n<p>  <\/p>\n<p>\u0420\u0430\u0431\u043e\u0442\u0430 \u043d\u0430\u0434 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u043e\u0439 <code>padic<\/code> \u0434\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0430 \u043c\u043d\u0435 \u043c\u0430\u0441\u0441\u0443 \u0443\u0434\u043e\u0432\u043e\u043b\u044c\u0441\u0442\u0432\u0438\u044f! <\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043f\u0440\u0438\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u044d\u0442\u043e\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u0437\u0430\u0434\u0435\u0439\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 \u0442\u0438\u043f\u043e\u0432, \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432 \u0442\u0438\u043f\u043e\u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u044c \u0438 \u043d\u0435\u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c\u043e\u0441\u0442\u044c \u043d\u0435\u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u0435\u0440\u0435\u0432\u0435\u0434\u044f \u0447\u0430\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u043d\u0430 \u044d\u0442\u0430\u043f \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0446\u0438\u0438. \u041d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0442\u0438\u043f\u043e\u0432 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u043c\u043e\u0434\u0443\u043b\u044c \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043c\u044b \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u043c, \u0442\u0430\u043a \u0438 \u0437\u0430\u0434\u0430\u0432\u0430\u0435\u043c\u0430\u044f \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c. \u0415\u0441\u043b\u0438 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u0443\u043a\u0430\u0437\u0430\u043d\u0430, \u043e\u043d\u0430 \u043f\u043e\u0434\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e\u0431\u044b \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e \u0440\u0435\u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 \u0441 \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044f\u043c\u0438 \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u044f\u043c\u0438 \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u0442\u0438\u043f\u0430 <code>Int32<\/code> \u0438\u0437 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f. \u041d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0442\u0438\u043f\u043e\u0432 \u0442\u0430\u043a \u0436\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0438 \u0441\u043e\u0433\u043b\u0430\u0441\u043e\u0432\u0430\u043d\u0438\u0435 \u043c\u043e\u0434\u0443\u043b\u044f p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a7d\/f0b\/0cf\/a7df0b0cf52583a7326d63832fe3d4ed.svg\" alt=\"$p$\" data-tex=\"inline\"\/> \u0438 \u043c\u043e\u0434\u0443\u043b\u044f \u0435\u0433\u043e \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e39\/bc9\/382\/e39bc938278ff24fa2bb42551eaf2e55.svg\" alt=\"$p^k$\" data-tex=\"inline\"\/> c \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u043e\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0435 \u0442\u0438\u043f\u044b, \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c\u044b\u0435 \u0442\u0438\u043f\u0430\u043c\u0438-\u043b\u0438\u0442\u0435\u0440\u0430\u043b\u0430\u043c\u0438 (type literals) \u0438 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u0442\u0438\u043f\u043e\u0432 (type families).<\/p>\n<p>  <\/p>\n<p>\u0422\u0438\u043f\u044b-\u043b\u0438\u0442\u0435\u0440\u0430\u043b\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u043e\u0439 <a href=\"https:\/\/hackage.haskell.org\/package\/base-4.16.0.0\/docs\/GHC-TypeLits.html\" rel=\"nofollow noopener noreferrer\">GHC.TypeLits<\/a> \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u043e\u043f\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0438 \u0441\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438, \u043a\u0430\u043a \u0441 \u0444\u0430\u043d\u0442\u043e\u043c\u043d\u044b\u043c\u0438 \u0442\u0438\u043f\u0430\u043c\u0438, \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u0443\u044e\u0449\u0438\u043c\u0438 \u043e\u0431\u044b\u0447\u043d\u044b\u0435 \u0442\u0438\u043f\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u0438 \u043a \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0435\u0441\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u0432 \u0440\u0430\u043d\u0442\u0430\u0439\u043c\u0435 (\u043b\u0438\u0448\u044c \u043d\u0430 \u0447\u0442\u0435\u043d\u0438\u0435, \u0438\u0437\u043c\u0435\u043d\u044f\u0442\u044c \u0444\u0430\u043d\u0442\u043e\u043c\u044b \u043c\u043e\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0442\u0438\u043f\u043e\u0432). \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0438\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u043f\u0440\u043e\u0442\u043e\u0442\u0438\u043f \u0434\u043b\u044f \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438.<\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u0447\u043d\u0451\u043c \u0441 \u0442\u0438\u043f\u0430 <code>Mod p<\/code>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442 \u043a \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0442\u043e\u043c, \u043a \u043a\u0430\u043a\u043e\u043c\u0443 \u043a\u043e\u043b\u044c\u0446\u0443 \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u043e\u043d\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">{-# LANGUAGE DataKinds #-} {-# LANGUAGE KindSignatures #-}  import GHC.TypeLits hiding (Mod)  newtype Mod (p :: Nat) = Mod Integer<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0438\u043f-\u0444\u0430\u043d\u0442\u043e\u043c <code>p<\/code> \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043b\u0435\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u0430-\u043e\u0431\u0451\u0440\u0442\u043a\u0438 \u043d\u0430\u0434 \u0442\u0438\u043f\u043e\u043c <code>Integer<\/code>. \u0415\u0433\u043e \u0440\u043e\u043b\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u043c\u0435\u0447\u0430\u0442\u044c \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0442\u0438\u043f\u043e\u0432 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u043a\u043e\u043b\u044c\u0446\u0430 \u0432\u044b\u0447\u0435\u0442\u043e\u0432. \u0414\u043e\u0441\u0442\u0443\u043f \u043a \u0442\u0438\u043f\u0443-\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>natVal<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> :t natVal > natVal (Mod 5 :: Mod 10) 10 > :t it Natural<\/code><\/pre>\n<p>  <\/p>\n<p>\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c &#171;\u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e\u0435&#187; \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u0442\u044c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0442\u043e\u043b\u043a\u043e\u0432\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0432\u044b\u0432\u043e\u0434\u0430 \u0447\u0438\u0441\u0435\u043b \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u043d\u0430 \u043f\u0435\u0447\u0430\u0442\u044c:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">instance KnownNat p => Show (Mod p) where   show n@(Mod x) = show (x `mod` p) ++ \" mod \" ++ show p     where p = natVal n<\/code><\/pre>\n<p>  <\/p>\n<p>\u041a\u043b\u0430\u0441\u0441 <code>KnownNat<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>natVal<\/code>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0435\u0433\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f (constraint).<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> Mod 5 :: Mod 10 5 mod 10 > Mod 17 :: Mod  10 7 mod 10<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0444\u0430\u043d\u0442\u043e\u043c\u043d\u043e\u043c\u0443 \u0442\u0438\u043f\u0443-\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0443 \u043c\u043e\u0436\u043d\u043e \u0438 \u0443 \u0435\u0449\u0451 \u043d\u0435 \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u0430. \u0412\u043e\u0442, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u0430\u0437\u043e\u0432\u044b\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">instance KnownNat p => Num (Mod p) where   fromInteger n = let res = Mod $ n `mod` natVal res in res   Mod a + Mod b = let res = Mod $ (a + b) `mod` natVal res in res   Mod a - Mod b = let res = Mod $ (a - b) `mod` natVal res in res   Mod a * Mod b = let res = Mod $ (a * b) `mod` natVal res in res   negate (Mod a) = let res = Mod (natVal res - a) in res   abs = id   signum _ = 1<\/code><\/pre>\n<p>  <\/p>\n<p>\u042d\u0442\u043e\u0442 \u043d\u0435\u0445\u0438\u0442\u0440\u044b\u0439 \u043f\u0440\u0438\u0451\u043c \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u0442\u0438\u043f\u044b \u0438\u0437 \u0447\u0438\u0441\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 &#171;\u0443\u0437\u043d\u0430\u044e\u0442&#187; \u043e \u0442\u043e\u043c, \u0432 \u043a\u0430\u043a\u0443\u044e \u043c\u043e\u0434\u0443\u043b\u044f\u0440\u043d\u0443\u044e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u0438\u0445 \u043f\u043e\u0433\u0440\u0443\u0437\u0438\u043b\u0438 \u043e\u0442 \u0432\u044b\u0437\u044b\u0432\u0430\u044e\u0449\u0435\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b.<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">> 5 :: Mod 3 2 mod 3 > 5 + (14 :: Mod 10) 9 mod 10<\/code><\/pre>\n<p>  <\/p>\n<p>\u041a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442 \u0440\u044f\u0434 \u0443\u0441\u043b\u043e\u0432\u0438\u0439. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a7d\/f0b\/0cf\/a7df0b0cf52583a7326d63832fe3d4ed.svg\" alt=\"$p$\" data-tex=\"inline\"\/> \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0447\u0438\u0441\u043b\u043e\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b. \u0412\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432 \u0432\u0438\u0434\u0435 \u043a\u043e\u043b\u044c\u0446\u0430 \u0432\u044b\u0447\u0435\u0442\u043e\u0432 \u0434\u043e\u043b\u0436\u043d\u043e \u0438\u043c\u0435\u0442\u044c \u043c\u043e\u0434\u0443\u043b\u044c <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e39\/bc9\/382\/e39bc938278ff24fa2bb42551eaf2e55.svg\" alt=\"$p^k$\" data-tex=\"inline\"\/>, \u0433\u0434\u0435 <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fce\/525\/2bd\/fce5252bde946816c2cf744d932890f7.svg\" alt=\"$k$\" data-tex=\"inline\"\/> \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c\u0441\u044f \u0438\u0441\u0445\u043e\u0434\u044f \u0438 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0439 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u044f p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b. \u0412\u0441\u0451 \u044d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0430 \u0443\u0440\u043e\u0432\u043d\u0435 \u0442\u0438\u043f\u043e\u0432, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430 \u0442\u0438\u043f\u043e\u0432. <\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">-- \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043a \u043f\u0440\u0435\u0430\u043c\u0431\u0443\u043b\u0435 {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE NoStarIsType #-} {-# LANGUAGE UndecidableInstances #-}  -- \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u043a \u0441\u043f\u0438\u0441\u043a\u0443 \u0438\u043c\u043f\u043e\u0440\u0442\u043e\u0432 import Data.Constraint (Constraint) import Data.Word  -- \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f type family ValidRadix (m :: Nat) :: Constraint where   ValidRadix 0 = TypeError ('Text \"Zero radix!\")   ValidRadix 1 = TypeError ('Text \"Radix should be more then 1!\")   ValidRadix m = ()  -- \u041e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 type family LiftedRadix p prec where   LiftedRadix p prec = p ^ (2*prec + 1)  -- \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0441 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e prec type family Radix p prec :: Constraint where   Radix p prec =     ( KnownNat prec     , KnownNat p, ValidRadix p     , KnownNat (LiftedRadix p prec), ValidRadix (LiftedRadix p prec) )  -- \u0422\u043e\u0447\u043d\u043e\u0441\u0442\u044c, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430\u044f \u0434\u043b\u044f \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b  -- \u0441 \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u0435\u043c \u0438 \u0437\u043d\u0430\u043c\u0435\u043d\u0430\u0442\u0435\u043b\u0435\u043c, \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0438\u043c  \u0442\u0438\u043f\u0443 num type family SufficientPrecision num (p :: Nat) :: Nat where   SufficientPrecision Word32 2 = 64   SufficientPrecision Word32 3 = 43   SufficientPrecision Word32 5 = 30   SufficientPrecision Word32 6 = 26   SufficientPrecision Word32 7 = 24   SufficientPrecision t p = Div (SufficientPrecision t 2) (Log2 p)<\/code><\/pre>\n<p>  <\/p>\n<p>\u042d\u0442\u0438 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u043d\u0430\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0442\u0438\u043f \u0434\u043b\u044f \u0446\u0435\u043b\u044b\u0445 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">-- \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043f\u0440\u0435\u0430\u043c\u0431\u0443\u043b\u0443 {-# LANGUAGE DerivingVia #-} {-# LANGUAGE StandaloneDeriving #-}  newtype Z' (p :: Nat) (prec :: Nat) = Z' (R prec p) newtype R (prec :: Nat ) (p :: Nat) = R (Mod (LiftedRadix p prec)) type Z p = Z' p (SufficientPrecision Word32 p)  deriving via (Mod p) instance Radix p prec => Num (R p prec) deriving via (Mod (LiftedRadix p prec)) instance Radix p prec => Num (R p prec)<\/code><\/pre>\n<p>  <\/p>\n<p>\u0427\u0435\u0445\u0430\u0440\u0434\u0430 \u0441 \u0434\u0432\u0443\u043c\u044f \u0432\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u0438\u043f\u0430\u043c\u0438 <code>Z<\/code> \u0438 <code>R<\/code> \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u043b\u0430\u0441\u044c \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u043e\u0431\u043e\u0438\u043c \u0444\u0430\u043d\u0442\u043e\u043c\u043d\u044b\u043c \u0442\u0438\u043f\u0430\u043c, \u043f\u0440\u0438 \u0442\u043e\u043c, \u0447\u0442\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u044f <code>natVal<\/code> \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u0430 &#171;\u0441\u0447\u0438\u0442\u0430\u0442\u044c&#187; \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u043d\u0435\u0448\u043d\u0438\u0439 \u0442\u0438\u043f-\u0444\u0430\u043d\u0442\u043e\u043c.<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">precision :: (Radix p prec, Z' p prec, Integral i) => Z' p prec -> i precision z = fromIntegral (natVal z)  radix :: (Radix p prec, Z' p prec, Integral i) => Z' p prec -> i radix (Z' r) = fromIntegral (natVal r)<\/code><\/pre>\n<p>  <\/p>\n<p>\u041d\u0430 \u044d\u0442\u0430\u043f\u0435 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0446\u0438\u0438 \u0432\u0441\u0435 \u044d\u0442\u0438 \u0442\u0438\u043f\u044b-\u043e\u0431\u0435\u0440\u0442\u043a\u0438 \u0438\u0441\u0447\u0435\u0437\u043d\u0443\u0442 \u0442\u0430\u043a \u0447\u0442\u043e \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u043c \u043a\u043e\u0434\u0435 \u043e\u0441\u0442\u0430\u043d\u0443\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0430\u0434 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0442\u0438\u043f\u0430 <code>Integer<\/code> \u0437\u0430\u0442\u043e\u0447\u0435\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438.<br \/>  \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u0432\u044b\u0432\u043e\u0434\u0438\u043b\u0438\u0441\u044c \u0432 \u0441\u0432\u043e\u0435\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u043c\u0435\u0442\u043e\u0434\u0430 <code>show<\/code>:<\/p>\n<p>  <\/p>\n<pre><code class=\"haskell\">instance Radix p prec => Show (Z' p prec) where   show n@(Z' (R (Mod x))) =    foldMap show $ reverse $ take (precision n) $ toRadix (radix n) x  toRadix :: Integer -> Integer -> [Int] toRadix _ 0 = [0] toRadix p n = unfoldr go n   where     go 0 = Nothing     go x = let (q, r) = quotRem x p in Just (fromIntegral r, q)<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"haskell\">> 42 :: Z 5 132  -- \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 > Z' (R x) = 42 :: Z' 5 10 > x 42 mod 476837158203125 -- \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u043c \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c > Z' (R x) = 42 :: Z' 5 5 > x 42 mod 48828125  -- \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438: > -42 :: Z 5 444444444444444444444444444313 > -42 :: Z' 5 5 44313 > (-42 :: Z 5) + 52 20  -- \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u0441\u0445\u043e\u0434\u044f\u0449\u0443\u044e\u0441\u044f \u043a \u0430\u0432\u0442\u043e\u043c\u043e\u0440\u0444\u043d\u043e\u043c\u0443 \u0447\u0438\u0441\u043b\u0443 > mapM_ print $ take 10 $ iterate (^2) (5 :: Z' 10 10) 5 25 625 390625 2587890625 6962890625 5712890625 3212890625 8212890625 8212890625<\/code><\/pre>\n<p>  <\/p>\n<p>\u041f\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u043c\u0443 \u0441\u0447\u0451\u0442\u0443, \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043c\u044b \u0441\u0434\u0435\u043b\u0430\u043b\u0438, \u0443\u0436\u0435 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0435\u0439 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438. \u0414\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0446\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0443\u0436\u043d\u043e \u0435\u0449\u0451 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u043e\u0442 \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u043a p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0438 \u043e\u0431\u0440\u0430\u0442\u043d\u043e, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0440\u0443\u0433\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u0422\u0435, \u043a\u043e\u043c\u0443 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b, \u044d\u0442\u0438 \u0434\u0435\u0442\u0430\u043b\u0438, \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043a\u043e\u0434 <a href=\"https:\/\/github.com\/samsergey\/padic.html\" rel=\"nofollow noopener noreferrer\">\u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438<\/a> \u043d\u0430 GitHub.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"v-portal\" style=\"display:none;\"><\/div>\n<\/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\/post\/646143\/\"> https:\/\/habr.com\/ru\/post\/646143\/<\/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_version-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p><img decoding=\"async\" src=\"\/img\/image-loader.svg\" data-src=\"https:\/\/habrastorage.org\/webt\/7z\/6t\/mb\/7z6tmbsyyurtyn8g_bcx8mmmtxk.png\"\/><\/p>\n<p>  <\/p>\n<p>\u042d\u0442\u0430 \u0447\u0430\u0441\u0442\u044c \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442 \u043d\u0435\u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0441\u0441\u043a\u0430\u0437 \u043e p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u043b\u0430\u0445 \u0438 \u043e\u043d\u0430 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0430\u0441\u043f\u0435\u043a\u0442\u0430\u043c \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u044d\u0442\u043e\u0439 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u0438, \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0434\u0435\u0442\u0430\u043b\u044f\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0430\u043b\u0433\u0435\u0431\u0440\u044b \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Haskell. \u041e \u0442\u043e\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u0437\u0430 \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0438 \u0437\u0430\u0447\u0435\u043c \u043e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f, \u0447\u0438\u0442\u0430\u0439\u0442\u0435 \u0432 <a href=\"https:\/\/habr.com\/ru\/post\/645939\/\">\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u0438<\/a>.<\/p>\n<p>  <\/p>\n<p>\u041c\u044b \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e\u0431 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u043c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 p-\u0430\u0434\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b, \u043e \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0438 \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043d\u0438\u043c\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043e \u0434\u0432\u0443\u0445 \u043a\u043b\u0430\u0441\u0441\u043d\u044b\u0445 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u0445 \u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0442\u0438\u043f\u043e\u0432 \u044f\u0437\u044b\u043a\u0430 Haskell: \u043e \u0442\u0438\u043f\u0430\u0445-\u043b\u0438\u0442\u0435\u0440\u0430\u043b\u0430\u0445 (type literals) \u0438 \u0441\u0435\u043c\u0435\u0439\u0441\u0442\u0432\u0430\u0445 \u0442\u0438\u043f\u043e\u0432 (type families).<\/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-328531","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/328531","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=328531"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/328531\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=328531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=328531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=328531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}