{"id":413554,"date":"2024-06-29T23:12:03","date_gmt":"2024-06-29T23:12:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=413554"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-06-29T23:12:03","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=413554","title":{"rendered":"<span>\u0411\u044b\u0441\u0442\u0440\u043e\u0435 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438e \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043b\u044f \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u0439 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430<\/span>"},"content":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e\u0431 \u043e\u0434\u043d\u043e\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f x mod p, \u0434\u043b\u044f p \u0432\u0438\u0434\u0430 (2 ** n &#8212; omega), \u043f\u0440\u0438\u0447\u0451\u043c omega \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 2 ** n. \u041d\u0430\u043f\u0438\u0448\u0443 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442 \u043d\u0430 Python. \u041f\u0440\u0438\u0432\u0435\u0434\u0443 \u043f\u0430\u0440\u0443 \u0438\u0433\u0440\u0443\u0448\u0435\u0447\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043d\u0430 \u0421++, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u0438\u0441\u0447\u0435\u0440\u043f\u044b\u0432\u0430\u044e\u0449\u0435\u0435 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432. \u0410 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 &#8212; \u0432\u044b\u0447\u0438\u0441\u043b\u044e 97! mod (2 ** 256 &#8212; 2 ** 32 &#8212; 977).<\/p>\n<h2>\u0417\u0430\u0447\u0435\u043c \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u043e?<\/h2>\n<ul>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0443 \u0432\u0430\u0441 \u043f\u043e\u0434 \u0440\u0443\u043a\u043e\u0439 \u043d\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0435\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0434\u043b\u044f \u0434\u043b\u0438\u043d\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 (\u0438\u043b\u0438 \u0447\u0443\u0434\u0435\u0441\u043d\u043e\u0433\u043e Python&#8217;\u0430);<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0431\u0438\u0442\u043e\u0432\u044b\u0435 \u0441\u0434\u0432\u0438\u0433\u0438, \u0430 \u043d\u0443\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f;<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0434 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438, \u0435\u0441\u043b\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u044b \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u044b\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u043d\u0435 \u0443\u0441\u0442\u0440\u0430\u0438\u0432\u0430\u0435\u0442.<\/p>\n<\/li>\n<\/ul>\n<h2>\u0422\u0435\u043e\u0440\u0438\u044f<\/h2>\n<p>\u0414\u0430\u043d\u043e:<\/p>\n<ul>\n<li>\n<p>\u0414\u0435\u043b\u0438\u0442\u0435\u043b\u044c p \u0432\u0438\u0434\u0430 (2 ** n &#8212; omega), \u043f\u0440\u0438\u0447\u0451\u043c omega \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 (2 ** n);<\/p>\n<\/li>\n<li>\n<p>\u0414\u0435\u043b\u0438\u043c\u043e\u0435 x, \u0440\u0430\u0437\u043c\u0435\u0440\u0430 m \u0431\u0438\u0442, \u043f\u0440\u0438\u0447\u0451\u043c m > n;<\/p>\n<\/li>\n<li>\n<p>\u0420\u0430\u0437\u043c\u0435\u0440 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 s, s &lt;= n, n \u0438 m \u043d\u0430\u0446\u0435\u043b\u043e \u0434\u0435\u043b\u044f\u0442\u0441\u044f \u043d\u0430 s.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430, \u0437\u0430\u043c\u0435\u0442\u0438\u043c \u0447\u0442\u043e (2 ** n) mod p = (2 ** n) mod (2 ** n &#8212; omega) == omega.<\/p>\n<p>\u041f\u0443\u0441\u0442\u044c x_low &#8212; \u043c\u043b\u0430\u0434\u0448\u0438\u0435 n \u0431\u0438\u0442 \u0447\u0438\u0441\u043b\u0430 x, \u0430 x_high &#8212; \u0441\u0442\u0430\u0440\u0448\u0438\u0435 (m &#8212; n) \u0431\u0438\u0442 \u0447\u0438\u0441\u043b\u0430 x, \u0442.\u0435. x \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 x_low + x_high * (2 ** n).<\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 x mod p = (x_low + x_high * (2 ** n)) mod p == x_low + x_high * omega (mod p). \u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u043d\u0435 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442, \u0447\u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0; p &#8212; 1], \u043e\u0434\u043d\u0430\u043a\u043e \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0; (2 ** n) &#8212; 1]. \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e omega \/ (2 ** n) \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u0447\u0435\u0441\u0442\u044c p \u0438\u0437 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430, \u0447\u0442\u043e\u0431\u044b \u043e\u043d \u043e\u043a\u0430\u0437\u0430\u043b\u0441\u044f \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0; p &#8212; 1].<\/p>\n<p>\u0420\u0430\u0437\u043e\u0431\u044c\u0435\u043c x \u043d\u0430 \u0441\u043b\u043e\u0432\u0430 w[i] \u0440\u0430\u0437\u043c\u0435\u0440\u0430 s \u0431\u0438\u0442: x = sum(i = 0 .. (m \/ s &#8212; 1); w[i] * 2 ** (i * s)). \u041a \u0442\u0430\u043a\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0434\u0435\u043b\u0438\u043c\u043e\u0433\u043e \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 x mod p == x_low + x_high * omega (mod p); \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0443 \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u0441\u043b\u043e\u0432 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u0441\u044f, \u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043f\u0440\u0438 \u0441\u043b\u043e\u0432\u0435 \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u043c\u043d\u043e\u0436\u0435\u043d \u043d\u0430 omega. \u041f\u0440\u0438\u043c\u0435\u043d\u0438\u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437 \u043c\u043e\u0436\u0435\u043c \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u0431\u0438\u0442\u043e\u0432\u043e\u043c \u0441\u043b\u043e\u0432\u0435 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 (2 ** n). \u0422\u043e \u0435\u0441\u0442\u044c, \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 x mod p \u0432 \u0432\u0438\u0434\u0435 \u0441\u0443\u043c\u043c\u044b \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 w[i] \u0440\u0430\u0437\u043c\u0435\u0440\u0430 s \u0431\u0438\u0442, \u0434\u043e\u043c\u043d\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u043d\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 n \u0431\u0438\u0442.<\/p>\n<h2>\u0413\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 Python<\/h2>\n<pre><code class=\"python\">def build_reducer(input_bits, target_bits, limb_size_bits, omega):   num_input_limbs = input_bits \/\/ limb_size_bits   target_limit = 2 ** target_bits    def split_and_reduce(coeff):     low_part = coeff % target_limit     high_part = coeff \/\/ target_limit     return low_part + high_part * omega    coeffs = [2 ** (limb_size_bits * i) for i in range(num_input_limbs)]    while any([k >= target_limit for k in coeffs]):     coeffs = [split_and_reduce(k) for k in coeffs]    return coeffs  def print_reducer(coeffs, target_bits):   for k in coeffs:     print('%0*x' % (target_bits \/\/ 4, k))<\/code><\/pre>\n<p>\u0410\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b:<\/p>\n<ul>\n<li>\n<p>input_bits &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442 \u043d\u0430 \u0432\u0445\u043e\u0434\u0435 (m);<\/p>\n<\/li>\n<li>\n<p>target_bits &#8212; \u0436\u0435\u043b\u0430\u0435\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 (n);<\/p>\n<\/li>\n<li>\n<p>limb_size_bits &#8212; \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 (s);<\/p>\n<\/li>\n<li>\n<p>omega &#8212; \u043e\u0434\u043d\u0430 \u0438\u0437 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442, \u0437\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c (2 ** n &#8212; omega).<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b:<\/p>\n<ol>\n<li>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 s, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0438\u0437 m \u0431\u0438\u0442;<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u0432\u043e\u0439\u043a\u0438 (2 ** n), \u043f\u043e \u0433\u0440\u0430\u043d\u0438\u0446\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043d\u0430 &#171;\u043c\u043b\u0430\u0434\u0448\u0438\u0435&#187; (1..n) \u0438 &#171;\u0441\u0442\u0430\u0440\u0448\u0438\u0435&#187; (n+1..m) \u0431\u0438\u0442\u044b;<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438, \u044f\u0432\u043b\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 \u0432 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0434\u0435\u043b\u0438\u043c\u043e\u0433\u043e;<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043a\u0430 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 (2 ** n) &#8212; \u0434\u0440\u043e\u0431\u0438\u043c \u0442\u0430\u043a\u0438\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043d\u0430 &#171;\u043c\u043b\u0430\u0434\u0448\u0438\u0435&#187; \u0438 &#171;\u0441\u0442\u0430\u0440\u0448\u0438\u0435&#187; \u0431\u0438\u0442\u044b \u0438 \u043f\u0435\u0440\u0435\u0441\u043e\u0431\u0438\u0440\u0430\u0435\u043c \u0438\u0437 \u043d\u0438\u0445 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442: (&#171;\u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0431\u0438\u0442\u044b&#187; + &#171;\u0441\u0442\u0430\u0440\u0448\u0438\u0435 \u0431\u0438\u0442\u044b&#187; * omega).<\/p>\n<\/li>\n<\/ol>\n<p>\u041f\u0440\u0438\u043c\u0435\u0440\u044b \u0440\u0430\u0431\u043e\u0442\u044b \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<ol>\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 32-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 8-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 8 &#8212; 17) = 239; \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 8 \u0431\u0438\u0442:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(32, 8, 8, 17) >>> print_reducer(r, 8) 01 11 32 85<\/code><\/pre>\n<ol start=\"2\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 32-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 16-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 16 &#8212; 666) = 64870; \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 8 \u0431\u0438\u0442:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(32, 16, 8, 666) >>> print_reducer(r, 16) 0001 0100 029a 9f34<\/code><\/pre>\n<ol start=\"3\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 2 ** 32 &#8212; 977); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 32 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 32 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 32, 2 ** 32 + 977) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000000_00000000_00000000_00000001_000003d1 00000000_00000000_00000000_00000000_00000000_00000001_000003d1_00000000 00000000_00000000_00000000_00000000_00000001_000003d1_00000000_00000000 00000000_00000000_00000000_00000001_000003d1_00000000_00000000_00000000 00000000_00000000_00000001_000003d1_00000000_00000000_00000000_00000000 00000000_00000001_000003d1_00000000_00000000_00000000_00000000_00000000 00000001_000003d1_00000000_00000000_00000000_00000000_00000000_00000000 000003d1_00000000_00000000_00000000_00000000_00000000_00000001_000003d1<\/code><\/pre>\n<ol start=\"4\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 2 ** 32 &#8212; 977); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 64 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 64 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 64, 2 ** 32 + 977) >>> print_reducer(r, 256) 0000000000000000_0000000000000000_0000000000000000_0000000000000001 0000000000000000_0000000000000000_0000000000000001_0000000000000000 0000000000000000_0000000000000001_0000000000000000_0000000000000000 0000000000000001_0000000000000000_0000000000000000_0000000000000000 0000000000000000_0000000000000000_0000000000000000_00000001000003d1 0000000000000000_0000000000000000_00000001000003d1_0000000000000000 0000000000000000_00000001000003d1_0000000000000000_0000000000000000 00000001000003d1_0000000000000000_0000000000000000_0000000000000000<\/code><\/pre>\n<ol start=\"5\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 432420386565659656852420866394968145599); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 32 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 32 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 32, 432420386565659656852420866394968145599) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf 00000000_00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000 00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000_00000000 00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000_00000000_00000000 45512319_50b75fc4_402da173_2fc9bec0_45512319_50b75fc4_402da173_2fc9bebf 50b75fc4_402da173_2fc9bec0_9d671cd5_1b343a1b_66926b57_d2a4c1c6_1536bda7 402da173_2fc9bec0_9d671cd5_81c69bc5_9509b0b0_74ec0aea_8f564d66_7ec7eb3c 2fc9bec0_9d671cd5_81c69bc5_e697f5e4_1f12c33a_0a7b6f4e_3302b92e_a029cecd<\/code><\/pre>\n<ol start=\"6\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 432420386565659656852420866394968145599); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 64 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 64 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 64, 432420386565659656852420866394968145599) >>> print_reducer(r, 256) 0000000000000000_0000000000000000_0000000000000000_0000000000000001 0000000000000000_0000000000000000_0000000000000001_0000000000000000 0000000000000000_0000000000000001_0000000000000000_0000000000000000 0000000000000001_0000000000000000_0000000000000000_0000000000000000 0000000000000000_0000000000000001_4551231950b75fc4_402da1732fc9bebf 0000000000000001_4551231950b75fc4_402da1732fc9bebf_0000000000000000 4551231950b75fc4_402da1732fc9bec0_4551231950b75fc4_402da1732fc9bebf 402da1732fc9bec0_9d671cd581c69bc5_9509b0b074ec0aea_8f564d667ec7eb3c<\/code><\/pre>\n<p>p.s. (2 ** 256 &#8212; 2 ** 32 &#8212; 977) &#8212; \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 p \u044d\u043b\u043b\u0438\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043a\u0440\u0438\u0432\u043e\u0439 SECP256K1; (2 ** 256 &#8212; 432420386565659656852420866394968145599) &#8212; \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 N \u044d\u043b\u043b\u0438\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043a\u0440\u0438\u0432\u043e\u0439 SECP256K1. (\u0421\u043c. <a href=\"https:\/\/en.bitcoin.it\/wiki\/Secp256k1\" rel=\"noopener noreferrer nofollow\">https:\/\/en.bitcoin.it\/wiki\/Secp256k1<\/a>)<\/p>\n<p>\u0427\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0433\u043b\u044f\u0434\u044f \u043d\u0430 \u044d\u0442\u0438 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b:<\/p>\n<ol>\n<li>\n<p>\u0427\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u0445 \u0431\u0438\u0442 \u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0447\u0438\u0441\u043b\u0430 omega &#8212; \u0442\u0435\u043c \u043f\u0440\u043e\u0449\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u044f\u0442 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b;<\/p>\n<\/li>\n<li>\n<p>\u0427\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 &#8212; \u0442\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441 \u0432 \u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0438 \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043b\u0438\u043d\u0430 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f x mod p;<\/p>\n<\/li>\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043f\u0440\u0438 \u043c\u043b\u0430\u0434\u0448\u0438\u0445 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432\u0430\u0445 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e\u043c\u0443 \u0431\u0438\u0442\u0443 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c \u043d\u0430\u0447\u0430\u043b\u0430\u043c \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432. \u0422.\u0435. \u043f\u0435\u0440\u0432\u044b\u0435 n \u0431\u0438\u0442 \u0447\u0438\u0441\u043b\u0430 \u0431\u0435\u0440\u0443\u0442\u0441\u044f \u043a\u0430\u043a \u0435\u0441\u0442\u044c, \u0438 \u043a \u043d\u0438\u043c \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0433\u0440\u0443\u043f\u043f\u044b \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u0431\u0438\u0442\u043e\u0432, \u043f\u043e\u043c\u043d\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b.<\/p>\n<\/li>\n<\/ol>\n<h2>\u0418\u0433\u0440\u0443\u0448\u0435\u0447\u043d\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>\u0414\u043b\u044f \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<pre><code class=\"cpp\">const uint32_t modulus = (1 &lt;&lt; 8) - 17;  uint32_t mod_exact(uint32_t x) {     return x % modulus; }  uint32_t mod_manual(uint32_t x) {     while (x &amp; 0xFFFFFF00) {         uint32_t buffer = 0;          buffer += 0x01 * (x &amp; 0xFF); x >>= 8;         buffer += 0x11 * (x &amp; 0xFF); x >>= 8;         buffer += 0x32 * (x &amp; 0xFF); x >>= 8;         buffer += 0x85 * (x &amp; 0xFF); x >>= 8;          x = buffer;     }     return (x &lt; modulus) ? x : (x - modulus); }<\/code><\/pre>\n<p>\u0414\u043b\u044f \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<pre><code class=\"cpp\">const uint32_t modulus = (1 &lt;&lt; 16) - 666;  uint32_t mod_exact(uint32_t x) {     return x % modulus; }  uint32_t mod_manual(uint32_t x) {     while (x &amp; 0xFFFF0000) {         uint32_t buffer = (x &amp; 0xFFFF); x >>= 16;         buffer += 0x029a * (x &amp; 0xFF); x >>= 8;         buffer += 0x9f34 * (x &amp; 0xFF); x >>= 8;          x = buffer;     }     return (x &lt; modulus) ? x : (x - modulus); }<\/code><\/pre>\n<p>\u041f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u0434\u043b\u044f \u0438\u0441\u0447\u0435\u0440\u043f\u044b\u0432\u0430\u044e\u0449\u0435\u0433\u043e \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u0432\u0443\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u0432\u044b\u0448\u0435:<\/p>\n<pre><code class=\"cpp\">#include &lt;iostream>  \/\/ put some implementation of mod_exact() and mod_manual() here  int main() {     uint32_t number = 0, fails = 0;     do {         uint32_t exact = mod_exact(number);         uint32_t manual = mod_manual(number);          fails += ((exact == manual) ? 0 : 1);         if ((number &amp; 0x00FFFFFF) == 0) {             std::cout &lt;&lt; number &lt;&lt; \"; fails=\" &lt;&lt; fails &lt;&lt; std::endl;         }          number++;     } while (number != 0);      std::cout &lt;&lt; \"done; fails=\" &lt;&lt; fails &lt;&lt; std::endl;     return 0; }<\/code><\/pre>\n<h2>\u0421\u0435\u0440\u044c\u0451\u0437\u043d\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440: 97! mod (2 ** 256 &#8212; 2 ** 32 &#8212; 977) <\/h2>\n<p>\u0412\u043e\u0437\u044c\u043c\u0435\u043c \u0442\u0440\u0435\u0442\u0438\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0430\u0431\u043e\u0442\u044b \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<pre><code>3. \u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 - 2 ** 32 - 977); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 - 32 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 32 \u0431\u0438\u0442\u0430: >>> r = build_reducer(512, 256, 32, 2 ** 32 + 977) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000000_00000000_00000000_00000001_000003d1 00000000_00000000_00000000_00000000_00000000_00000001_000003d1_00000000 00000000_00000000_00000000_00000000_00000001_000003d1_00000000_00000000 00000000_00000000_00000000_00000001_000003d1_00000000_00000000_00000000 00000000_00000000_00000001_000003d1_00000000_00000000_00000000_00000000 00000000_00000001_000003d1_00000000_00000000_00000000_00000000_00000000 00000001_000003d1_00000000_00000000_00000000_00000000_00000000_00000000 000003d1_00000000_00000000_00000000_00000000_00000000_00000001_000003d1<\/code><\/pre>\n<p>\u0412\u0445\u043e\u0434\u043d\u043e\u0435 512-\u0431\u0438\u0442\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0440\u0430\u0437\u043e\u0431\u044c\u0451\u043c \u043d\u0430 16 \u0433\u0440\u0443\u043f\u043f \u043f\u043e 32 \u0431\u0438\u0442\u0430, \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0438\u0445 w[0..15]. \u0422\u043e\u0433\u0434\u0430 \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u044d\u0442\u0438\u0445 \u0433\u0440\u0443\u043f\u043f \u043d\u0430 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u044b\u0435 \u043a\u0443\u0441\u043e\u0447\u043a\u0438 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0442\u0430\u043a\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 x mod p:<\/p>\n<pre><code>    (2 ** 0) *   (w[0] +         977 * w[8] + 977 * w[15]) +     (2 ** 32) *  (w[1] + w[8] +  977 * w[9] +       w[15]) +     (2 ** 64) *  (w[2] + w[9] +  977 * w[10]) +     (2 ** 96) *  (w[3] + w[10] + 977 * w[11]) +     (2 ** 128) * (w[4] + w[11] + 977 * w[12]) +     (2 ** 160) * (w[5] + w[12] + 977 * w[13]) +     (2 ** 192) * (w[6] + w[13] + 977 * w[14]) +     (2 ** 224) * (w[7] + w[14] + 977 * w[15])<\/code><\/pre>\n<p>\u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438 (\u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0439 \u043e\u0434\u043d\u043e\u043c\u0443 \u0431\u0438\u0442\u043e\u0432\u043e\u043c\u0443 \u0441\u043b\u043e\u0432\u0443 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430) \u0441\u0442\u043e\u0438\u0442 \u0441\u0443\u043c\u043c\u0430 \u0447\u0438\u0441\u0435\u043b, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0432 64 \u0431\u0438\u0442\u0430, \u0441 \u0443\u0447\u0451\u0442\u043e\u043c \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0430 \u0432 \u0441\u0442\u0430\u0440\u0448\u0438\u0435 \u0440\u0430\u0437\u0440\u044f\u0434\u044b. \u0421\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438 (2 ** 256) \u0438 \u0432\u044b\u0448\u0435 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0442, \u0442.\u0435. \u0441 \u0443\u0447\u0451\u0442\u043e\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0438\u0437 9 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 \u043f\u043e 32 \u0431\u0438\u0442\u0430, \u0430 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0432\u043d\u044b \u043d\u0443\u043b\u044e. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f:<\/p>\n<pre><code>    (2 ** 0) *  (w[0] + 977 * w[8]) +     (2 ** 32) * (w[1] +       w[8]) +     (2 ** 64) *  w[2] +     (2 ** 96) *  w[3] +     (2 ** 128) * w[4] +     (2 ** 160) * w[5] +     (2 ** 192) * w[6] +     (2 ** 224) * w[7]<\/code><\/pre>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u044d\u0442\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 2 ** 32 &#8212; 977):<\/p>\n<pre><code class=\"cpp\">void reduce_512(const uint32_t x[16], uint32_t y[8]) {     \/\/ check if any of bits[257..512] is set     uint32_t mask = 0;     for (int i = 8; i &lt; 16; mask |= x[i++]);     if (mask == 0) return;      uint64_t buffer = 0;      \/\/ stage 1: reduce 16 limbs into 9     \/\/ (2 ** 0) *   (w[0] +         977 * w[8] + 977 * w[15]) +     buffer += (uint64_t)x[0] + 977 * (uint64_t)x[8] + 977 * (uint64_t)x[15];     y[0] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 32) *  (w[1] + w[8] +  977 * w[9] +       w[15]) +     buffer += (uint64_t)x[1] + (uint64_t)x[8] + 977 * (uint64_t)x[9] + (uint64_t)x[15];     y[1] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 64) *  (w[2] + w[9] +  977 * w[10]) +     buffer += (uint64_t)x[2] + (uint64_t)x[9] + 977 * (uint64_t)x[10];     y[2] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 96) *  (w[3] + w[10] + 977 * w[11]) +     buffer += (uint64_t)x[3] + (uint64_t)x[10] + 977 * (uint64_t)x[11];     y[3] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 128) * (w[4] + w[11] + 977 * w[12]) +     buffer += (uint64_t)x[4] + (uint64_t)x[11] + 977 * (uint64_t)x[12];     y[4] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 160) * (w[5] + w[12] + 977 * w[13]) +     buffer += (uint64_t)x[5] + (uint64_t)x[12] + 977 * (uint64_t)x[13];     y[5] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 192) * (w[6] + w[13] + 977 * w[14]) +     buffer += (uint64_t)x[6] + (uint64_t)x[13] + 977 * (uint64_t)x[14];     y[6] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     \/\/ (2 ** 224) * (w[7] + w[14] + 977 * w[15])     buffer += (uint64_t)x[7] + (uint64_t)x[14] + 977 * (uint64_t)x[15];     y[7] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;      \/\/ stage 2: reduce 9 limbs into 8     while (buffer != 0) {         \/\/ save 9th limb (10 bits max) and flush buffer         const uint64_t overflow256 = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         assert(buffer == 0);          \/\/ (2 ** 0) *  (w[0] + 977 * w[8]) +         buffer += (uint64_t)y[0] + 977 * overflow256;         y[0] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 32)*  (w[1] +       w[8]) +         buffer += (uint64_t)y[1] + overflow256;         y[1] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 64) *  w[2] +         buffer += (uint64_t)y[2];         y[2] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 96) *  w[3] +         buffer += (uint64_t)y[3];         y[3] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 128) * w[4] +         buffer += (uint64_t)y[4];         y[4] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 160) * w[5] +         buffer += (uint64_t)y[5];         y[5] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 192) * w[6] +         buffer += (uint64_t)y[6];         y[6] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;         \/\/ (2 ** 224) * w[7]         buffer += (uint64_t)y[7];         y[7] = buffer &amp; 0xFFFFFFFF; buffer >>= 32;     }          \/\/ 512 bits are now reduced to 256 bits, however the result may exceed     \/\/ (2^256 - 2^32 - 977) and an additional subtraction may be necessary }<\/code><\/pre>\n<p>\u0422\u0435\u0441\u0442\u043e\u0432\u0430\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0437\u0430\u0448\u0438\u0442\u0430 \u043f\u0430\u0440\u0430 \u0447\u0438\u0441\u0435\u043b &#8212; \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0430\u043b 97 (\u0447\u0438\u0441\u043b\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u043e\u043a\u043e\u043b\u043e 500 \u0431\u0438\u0442) \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f (97! mod (2 ** 256 &#8212; 2 ** 32 &#8212; 977)), \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0439 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u0432 \u0440\u0430\u0431\u043e\u0442\u044b \u0444\u0443\u043d\u043a\u0446\u0438\u0438:<\/p>\n<pre><code class=\"cpp\">#include &lt;iostream> #include &lt;cassert>  void reduce_512(const uint32_t x[16], uint32_t y[8]) {   \/\/ put function code here }  int main() {     \/\/ math.factorial(97), this is about 500 bits long     \/\/ least significant limbs go first     const uint32_t x[16] = {         0x00000000, 0x00000000, 0xc0000000, 0xc63bc975,         0xcb0e1818, 0xfe74c03b, 0x13559f1a, 0xca00bb56,         0xef9d44bc, 0xf57bf161, 0xf3e3d5c3, 0xab918234,         0xb69daa20, 0x4532ed8b, 0xafb0a77f, 0x01d62e2f     };     \/\/ math.factorial(97) % (2 ** 256 - 2 ** 32 - 977)     \/\/ least significant limbs go first     const uint32_t y_expected[8] = {         0x7999b163, 0xcf77a9bd, 0x7dfec23d, 0x80718b50,         0x6655e0fc, 0xcc6efc90, 0xd9b7c95d, 0x7c17a6d2     };      uint32_t y[8];     reduce_512(x, y); \/\/ stage 2 is ran once for this input      \/\/ print\/verify     bool ok = true;     for (int i = 0; i &lt; 8; ok &amp;= (y[i] == y_expected[i]), i++) {         std::cout &lt;&lt; std::hex &lt;&lt; y[i] &lt;&lt; std::endl;     }     std::cout &lt;&lt; (ok ? \"Ok\" : \"Failed\") &lt;&lt; std::endl;      return 0; }<\/code><\/pre>\n<p>p.s. \u0412\u0441\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0435\u043d\u044b \u0432 Microsoft Visual Studio 2022 (v17.5.4)<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/div>\n<p><!----><!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/articles\/731038\/\"> https:\/\/habr.com\/ru\/articles\/731038\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><!--[--><!--]--><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e\u0431 \u043e\u0434\u043d\u043e\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f x mod p, \u0434\u043b\u044f p \u0432\u0438\u0434\u0430 (2 ** n &#8212; omega), \u043f\u0440\u0438\u0447\u0451\u043c omega \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 2 ** n. \u041d\u0430\u043f\u0438\u0448\u0443 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442 \u043d\u0430 Python. \u041f\u0440\u0438\u0432\u0435\u0434\u0443 \u043f\u0430\u0440\u0443 \u0438\u0433\u0440\u0443\u0448\u0435\u0447\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043d\u0430 \u0421++, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u0438\u0441\u0447\u0435\u0440\u043f\u044b\u0432\u0430\u044e\u0449\u0435\u0435 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432. \u0410 \u0432 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 &#8212; \u0432\u044b\u0447\u0438\u0441\u043b\u044e 97! mod (2 ** 256 &#8212; 2 ** 32 &#8212; 977).<\/p>\n<h2>\u0417\u0430\u0447\u0435\u043c \u044d\u0442\u043e \u043d\u0443\u0436\u043d\u043e?<\/h2>\n<ul>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0443 \u0432\u0430\u0441 \u043f\u043e\u0434 \u0440\u0443\u043a\u043e\u0439 \u043d\u0435\u0442 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0435\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0434\u043b\u044f \u0434\u043b\u0438\u043d\u043d\u043e\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 (\u0438\u043b\u0438 \u0447\u0443\u0434\u0435\u0441\u043d\u043e\u0433\u043e Python&#8217;\u0430);<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0431\u0438\u0442\u043e\u0432\u044b\u0435 \u0441\u0434\u0432\u0438\u0433\u0438, \u0430 \u043d\u0443\u0436\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043e\u0441\u0442\u0430\u0442\u043a\u0430 \u043e\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f;<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0434 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0435 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438, \u0435\u0441\u043b\u0438 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u044b \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u044b\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u043d\u0435 \u0443\u0441\u0442\u0440\u0430\u0438\u0432\u0430\u0435\u0442.<\/p>\n<\/li>\n<\/ul>\n<h2>\u0422\u0435\u043e\u0440\u0438\u044f<\/h2>\n<p>\u0414\u0430\u043d\u043e:<\/p>\n<ul>\n<li>\n<p>\u0414\u0435\u043b\u0438\u0442\u0435\u043b\u044c p \u0432\u0438\u0434\u0430 (2 ** n &#8212; omega), \u043f\u0440\u0438\u0447\u0451\u043c omega \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 (2 ** n);<\/p>\n<\/li>\n<li>\n<p>\u0414\u0435\u043b\u0438\u043c\u043e\u0435 x, \u0440\u0430\u0437\u043c\u0435\u0440\u0430 m \u0431\u0438\u0442, \u043f\u0440\u0438\u0447\u0451\u043c m > n;<\/p>\n<\/li>\n<li>\n<p>\u0420\u0430\u0437\u043c\u0435\u0440 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 s, s &lt;= n, n \u0438 m \u043d\u0430\u0446\u0435\u043b\u043e \u0434\u0435\u043b\u044f\u0442\u0441\u044f \u043d\u0430 s.<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430, \u0437\u0430\u043c\u0435\u0442\u0438\u043c \u0447\u0442\u043e (2 ** n) mod p = (2 ** n) mod (2 ** n &#8212; omega) == omega.<\/p>\n<p>\u041f\u0443\u0441\u0442\u044c x_low &#8212; \u043c\u043b\u0430\u0434\u0448\u0438\u0435 n \u0431\u0438\u0442 \u0447\u0438\u0441\u043b\u0430 x, \u0430 x_high &#8212; \u0441\u0442\u0430\u0440\u0448\u0438\u0435 (m &#8212; n) \u0431\u0438\u0442 \u0447\u0438\u0441\u043b\u0430 x, \u0442.\u0435. x \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 x_low + x_high * (2 ** n).<\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 x mod p = (x_low + x_high * (2 ** n)) mod p == x_low + x_high * omega (mod p). \u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u043d\u0435 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442, \u0447\u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0; p &#8212; 1], \u043e\u0434\u043d\u0430\u043a\u043e \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0; (2 ** n) &#8212; 1]. \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e omega \/ (2 ** n) \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u0447\u0435\u0441\u0442\u044c p \u0438\u0437 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430, \u0447\u0442\u043e\u0431\u044b \u043e\u043d \u043e\u043a\u0430\u0437\u0430\u043b\u0441\u044f \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435 [0; p &#8212; 1].<\/p>\n<p>\u0420\u0430\u0437\u043e\u0431\u044c\u0435\u043c x \u043d\u0430 \u0441\u043b\u043e\u0432\u0430 w[i] \u0440\u0430\u0437\u043c\u0435\u0440\u0430 s \u0431\u0438\u0442: x = sum(i = 0 .. (m \/ s &#8212; 1); w[i] * 2 ** (i * s)). \u041a \u0442\u0430\u043a\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044e \u0434\u0435\u043b\u0438\u043c\u043e\u0433\u043e \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 x mod p == x_low + x_high * omega (mod p); \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0443 \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u0441\u043b\u043e\u0432 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u0441\u044f, \u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043f\u0440\u0438 \u0441\u043b\u043e\u0432\u0435 \u0431\u0443\u0434\u0435\u0442 \u0434\u043e\u043c\u043d\u043e\u0436\u0435\u043d \u043d\u0430 omega. \u041f\u0440\u0438\u043c\u0435\u043d\u0438\u0432 \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437 \u043c\u043e\u0436\u0435\u043c \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u0431\u0438\u0442\u043e\u0432\u043e\u043c \u0441\u043b\u043e\u0432\u0435 \u0431\u0443\u0434\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 (2 ** n). \u0422\u043e \u0435\u0441\u0442\u044c, \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 x mod p \u0432 \u0432\u0438\u0434\u0435 \u0441\u0443\u043c\u043c\u044b \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 w[i] \u0440\u0430\u0437\u043c\u0435\u0440\u0430 s \u0431\u0438\u0442, \u0434\u043e\u043c\u043d\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u043d\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 n \u0431\u0438\u0442.<\/p>\n<h2>\u0413\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 Python<\/h2>\n<pre><code class=\"python\">def build_reducer(input_bits, target_bits, limb_size_bits, omega):   num_input_limbs = input_bits \/\/ limb_size_bits   target_limit = 2 ** target_bits    def split_and_reduce(coeff):     low_part = coeff % target_limit     high_part = coeff \/\/ target_limit     return low_part + high_part * omega    coeffs = [2 ** (limb_size_bits * i) for i in range(num_input_limbs)]    while any([k >= target_limit for k in coeffs]):     coeffs = [split_and_reduce(k) for k in coeffs]    return coeffs  def print_reducer(coeffs, target_bits):   for k in coeffs:     print('%0*x' % (target_bits \/\/ 4, k))<\/code><\/pre>\n<p>\u0410\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u044b:<\/p>\n<ul>\n<li>\n<p>input_bits &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442 \u043d\u0430 \u0432\u0445\u043e\u0434\u0435 (m);<\/p>\n<\/li>\n<li>\n<p>target_bits &#8212; \u0436\u0435\u043b\u0430\u0435\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 (n);<\/p>\n<\/li>\n<li>\n<p>limb_size_bits &#8212; \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 (s);<\/p>\n<\/li>\n<li>\n<p>omega &#8212; \u043e\u0434\u043d\u0430 \u0438\u0437 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442, \u0437\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c (2 ** n &#8212; omega).<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b:<\/p>\n<ol>\n<li>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 s, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0438\u0437 m \u0431\u0438\u0442;<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u0432\u043e\u0439\u043a\u0438 (2 ** n), \u043f\u043e \u0433\u0440\u0430\u043d\u0438\u0446\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442 \u043d\u0430 &#171;\u043c\u043b\u0430\u0434\u0448\u0438\u0435&#187; (1..n) \u0438 &#171;\u0441\u0442\u0430\u0440\u0448\u0438\u0435&#187; (n+1..m) \u0431\u0438\u0442\u044b;<\/p>\n<\/li>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438, \u044f\u0432\u043b\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432 \u0432 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0434\u0435\u043b\u0438\u043c\u043e\u0433\u043e;<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043a\u0430 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 (2 ** n) &#8212; \u0434\u0440\u043e\u0431\u0438\u043c \u0442\u0430\u043a\u0438\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043d\u0430 &#171;\u043c\u043b\u0430\u0434\u0448\u0438\u0435&#187; \u0438 &#171;\u0441\u0442\u0430\u0440\u0448\u0438\u0435&#187; \u0431\u0438\u0442\u044b \u0438 \u043f\u0435\u0440\u0435\u0441\u043e\u0431\u0438\u0440\u0430\u0435\u043c \u0438\u0437 \u043d\u0438\u0445 \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442: (&#171;\u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0431\u0438\u0442\u044b&#187; + &#171;\u0441\u0442\u0430\u0440\u0448\u0438\u0435 \u0431\u0438\u0442\u044b&#187; * omega).<\/p>\n<\/li>\n<\/ol>\n<p>\u041f\u0440\u0438\u043c\u0435\u0440\u044b \u0440\u0430\u0431\u043e\u0442\u044b \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<ol>\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 32-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 8-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 8 &#8212; 17) = 239; \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 8 \u0431\u0438\u0442:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(32, 8, 8, 17) >>> print_reducer(r, 8) 01 11 32 85<\/code><\/pre>\n<ol start=\"2\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 32-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 16-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 16 &#8212; 666) = 64870; \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 8 \u0431\u0438\u0442:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(32, 16, 8, 666) >>> print_reducer(r, 16) 0001 0100 029a 9f34<\/code><\/pre>\n<ol start=\"3\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 2 ** 32 &#8212; 977); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 32 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 32 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 32, 2 ** 32 + 977) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000000_00000000_00000000_00000001_000003d1 00000000_00000000_00000000_00000000_00000000_00000001_000003d1_00000000 00000000_00000000_00000000_00000000_00000001_000003d1_00000000_00000000 00000000_00000000_00000000_00000001_000003d1_00000000_00000000_00000000 00000000_00000000_00000001_000003d1_00000000_00000000_00000000_00000000 00000000_00000001_000003d1_00000000_00000000_00000000_00000000_00000000 00000001_000003d1_00000000_00000000_00000000_00000000_00000000_00000000 000003d1_00000000_00000000_00000000_00000000_00000000_00000001_000003d1<\/code><\/pre>\n<ol start=\"4\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 2 ** 32 &#8212; 977); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 64 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 64 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 64, 2 ** 32 + 977) >>> print_reducer(r, 256) 0000000000000000_0000000000000000_0000000000000000_0000000000000001 0000000000000000_0000000000000000_0000000000000001_0000000000000000 0000000000000000_0000000000000001_0000000000000000_0000000000000000 0000000000000001_0000000000000000_0000000000000000_0000000000000000 0000000000000000_0000000000000000_0000000000000000_00000001000003d1 0000000000000000_0000000000000000_00000001000003d1_0000000000000000 0000000000000000_00000001000003d1_0000000000000000_0000000000000000 00000001000003d1_0000000000000000_0000000000000000_0000000000000000<\/code><\/pre>\n<ol start=\"5\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 432420386565659656852420866394968145599); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 32 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 32 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 32, 432420386565659656852420866394968145599) >>> print_reducer(r, 256) 00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001 00000000_00000000_00000000_00000000_00000000_00000000_00000001_00000000 00000000_00000000_00000000_00000000_00000000_00000001_00000000_00000000 00000000_00000000_00000000_00000000_00000001_00000000_00000000_00000000 00000000_00000000_00000000_00000001_00000000_00000000_00000000_00000000 00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000 00000000_00000001_00000000_00000000_00000000_00000000_00000000_00000000 00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000 00000000_00000000_00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf 00000000_00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000 00000000_00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000_00000000 00000001_45512319_50b75fc4_402da173_2fc9bebf_00000000_00000000_00000000 45512319_50b75fc4_402da173_2fc9bec0_45512319_50b75fc4_402da173_2fc9bebf 50b75fc4_402da173_2fc9bec0_9d671cd5_1b343a1b_66926b57_d2a4c1c6_1536bda7 402da173_2fc9bec0_9d671cd5_81c69bc5_9509b0b0_74ec0aea_8f564d66_7ec7eb3c 2fc9bec0_9d671cd5_81c69bc5_e697f5e4_1f12c33a_0a7b6f4e_3302b92e_a029cecd<\/code><\/pre>\n<ol start=\"6\">\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u0434\u043b\u044f \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f 512-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0434\u043e 256-\u0431\u0438\u0442\u043d\u043e\u0433\u043e \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e (2 ** 256 &#8212; 432420386565659656852420866394968145599); \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u043b\u043e\u0432\u0430 &#8212; 64 \u0431\u0438\u0442\u0430; \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0441\u0433\u0440\u0443\u043f\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e 64 \u0431\u0438\u0442\u0430:<\/p>\n<\/li>\n<\/ol>\n<pre><code>>>> r = build_reducer(512, 256, 64, 432420386565659656852420866394968145599) >>> print_reducer(r, 256) 0000000000000000_0000000000000000_0000000000000000_0000000000000001 0000000000000000_0000000000000000_0000000000000001_0000000000000000 0000000000000000_0000000000000001_0000000000000000_0000000000000000 0000000000000001_0000000000000000_0000000000000000_0000000000000000 0000000000000000_0000000000000001_4551231950b75fc4_402da1732fc9bebf 0000000000000001_4551231950b75fc4_402da1732fc9bebf_0000000000000000 4551231950b75fc4_402da1732fc9bec0_4551231950b75fc4_402da1732fc9bebf 402da1732fc9bec0_9d671cd581c69bc5_9509b0b074ec0aea_8f564d667ec7eb3c<\/code><\/pre>\n<p>p.s. (2 ** 256 &#8212; 2 ** 32 &#8212; 977) &#8212; \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 p \u044d\u043b\u043b\u0438\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043a\u0440\u0438\u0432\u043e\u0439 SECP256K1; (2 ** 256 &#8212; 432420386565659656852420866394968145599) &#8212; \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440 N \u044d\u043b\u043b\u0438\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043a\u0440\u0438\u0432\u043e\u0439 SECP256K1. (\u0421\u043c. <a href=\"https:\/\/en.bitcoin.it\/wiki\/Secp256k1\" rel=\"noopener noreferrer nofollow\">https:\/\/en.bitcoin.it\/wiki\/Secp256k1<\/a>)<\/p>\n<p>\u0427\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0433\u043b\u044f\u0434\u044f \u043d\u0430 \u044d\u0442\u0438 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b:<\/p>\n<ol>\n<li>\n<p>\u0427\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u044b\u0445 \u0431\u0438\u0442 \u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0447\u0438\u0441\u043b\u0430 omega &#8212; \u0442\u0435\u043c \u043f\u0440\u043e\u0449\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u044f\u0442 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b;<\/p>\n<\/li>\n<li>\n<p>\u0427\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 &#8212; \u0442\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441 \u0432 \u043c\u043b\u0430\u0434\u0448\u0438\u0435 \u0440\u0430\u0437\u0440\u044f\u0434\u044b \u0438 \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0434\u043b\u0438\u043d\u0430 \u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f x mod p;<\/p>\n<\/li>\n<li>\n<p>\u041a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b \u043f\u0440\u0438 \u043c\u043b\u0430\u0434\u0448\u0438\u0445 \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432\u0430\u0445 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e\u043c\u0443 \u0431\u0438\u0442\u0443 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c \u043d\u0430\u0447\u0430\u043b\u0430\u043c \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u0441\u043b\u043e\u0432. \u0422.\u0435. \u043f\u0435\u0440\u0432\u044b\u0435 n \u0431\u0438\u0442 \u0447\u0438\u0441\u043b\u0430 \u0431\u0435\u0440\u0443\u0442\u0441\u044f \u043a\u0430\u043a \u0435\u0441\u0442\u044c, \u0438 \u043a \u043d\u0438\u043c \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0433\u0440\u0443\u043f\u043f\u044b \u0441\u0442\u0430\u0440\u0448\u0438\u0445 \u0431\u0438\u0442\u043e\u0432, \u043f\u043e\u043c\u043d\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u043d\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b.<\/p>\n<\/li>\n<\/ol>\n<h2>\u0418\u0433\u0440\u0443\u0448\u0435\u0447\u043d\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>\u0414\u043b\u044f \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<pre><code class=\"cpp\">const uint32_t modulus = (1 &lt;&lt; 8) - 17;  uint32_t mod_exact(uint32_t x) {     return x % modulus; }  uint32_t mod_manual(uint32_t x) {     while (x &amp; 0xFFFFFF00) {         uint32_t buffer = 0;          buffer += 0x01 * (x &amp; 0xFF); x >>= 8;         buffer += 0x11 * (x &amp; 0xFF); x >>= 8;         buffer += 0x32 * (x &amp; 0xFF); x >>= 8;         buffer += 0x85 * (x &amp; 0xFF); x >>= 8;          x = buffer;     }     return (x &lt; modulus) ? x : (x - modulus); }<\/code><\/pre>\n<p>\u0414\u043b\u044f \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u0432:<\/p>\n<pre><code class=\"cpp\">const uint32_t modulus = (1 &lt;&lt; 16) - 666;  uint32_t mod_exact(uint32_t x) {     return x % modulus; }  uint32_t mod_manual(uint32_t x) {     while (x &amp; 0xFFFF0000) {         uint32_t buffer = (x &amp; 0xFFFF); x >>= 16;         buffer += 0x029a * (x &amp; 0xFF); x >>= 8;         buffer += 0x9f34 * (x &amp; 0xFF); x >>= 8;          x = buffer;     }     return (x &lt; modulus) ? <\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\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-413554","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/413554","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=413554"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/413554\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=413554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=413554"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=413554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}