{"id":311410,"date":"2020-10-13T15:01:35","date_gmt":"2020-10-13T15:01:35","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=311410"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=311410","title":{"rendered":"\u0424\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u0442\u0430. \u0427\u0430\u0441\u0442\u044c II"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/522194\/\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/up\/k9\/cv\/upk9cvor1otijonyhk4-tab7ohm.jpeg\"><\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u043e\u0447\u0438\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u0446\u0438\u043a\u043b\u0430<\/b>                         <\/p>\n<div class=\"spoiler_text\"><a href=\"https:\/\/habr.com\/ru\/post\/521876\/\">\u0424\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u0442\u0430. \u0427\u0430\u0441\u0442\u044c I<\/a><br \/>  \u0424\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u0442\u0430. \u0427\u0430\u0441\u0442\u044c II  <\/div>\n<\/p><\/div>\n<p>  \u0417\u0430\u0434\u0430\u0435\u0442\u0441\u044f N \u2014 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u043e\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e (\u0421\u041d\u041d\u0427), \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0442\u0435\u043e\u0440\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430 \u0440\u0435\u0448\u0435\u0442\u0430 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u043b\u044f (NFS) \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0442\u0435\u043e\u0440\u0438\u0438 \u0434\u0435\u043b\u0438\u043c\u043e\u0441\u0442\u0438 \u0432 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u043f\u043e\u043b\u044f\u0445. \u041f\u0435\u0440\u0435\u0434 \u043b\u044e\u0431\u044b\u043c \u0430\u0432\u0442\u043e\u0440\u043e\u043c, \u043a\u0430\u043a \u0438 \u043f\u0435\u0440\u0435\u0434\u043e \u043c\u043d\u043e\u0439, \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u044c \u0441\u0436\u0430\u0442\u043e\u0433\u043e \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0432\u0435\u0441\u044c\u043c\u0430 \u043e\u0431\u0448\u0438\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430, \u043a\u0430\u0441\u0430\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u0432 SNFS \u0438 GNFS. \u0422\u0430\u043a \u043a\u0430\u043a 2-\u0439 \u0432\u043e\u0437\u043d\u0438\u043a \u0438\u0437 1-\u0433\u043e \u044f \u043d\u0435 \u043f\u0440\u0438\u0432\u043e\u0436\u0443 \u0438\u0445 \u043e\u0442\u043b\u0438\u0447\u0438\u0439, \u0445\u043e\u0442\u044f \u043e\u0431 \u044d\u0442\u043e\u043c \u043c\u043d\u043e\u0433\u043e \u0441\u043a\u0430\u0437\u0430\u043d\u043e.<\/p>\n<p>  \u041e \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u0446\u0435\u043b\u044b\u0435 \u043a\u043d\u0438\u0433\u0438. \u041d\u043e, \u043f\u043e\u043c\u043d\u044f \u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0437\u0430\u0442\u0440\u0443\u0434\u043d\u0435\u043d\u0438\u044f\u0445 \u0432 \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0438 \u043f\u0440\u0435\u043e\u0434\u043e\u043b\u0435\u043d\u0438\u0438 \u0438\u0445, \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0434\u0430\u0436\u0435 \u00ab\u043a\u0443\u0446\u0435\u0435\u00bb \u0443\u0440\u0435\u0437\u0430\u043d\u043d\u043e\u0435 \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043f\u043e\u0441\u043e\u0431\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u043b\u0435\u043d\u0438\u044e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0441 \u043c\u0435\u0442\u043e\u0434\u0430\u043c\u0438 \u0438 \u0438\u0434\u0435\u044f\u043c\u0438, \u043b\u0435\u0436\u0430\u0449\u0438\u043c\u0438 \u0432 \u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0435. \u041d\u0430\u0434\u0435\u044e\u0441\u044c, \u0447\u0442\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u044d\u0442\u0438\u0445 \u0438\u0434\u0435\u0439 \u0438\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u0438 (\u0447\u0442\u043e \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0430 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442 \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e), \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u0431\u043e\u043b\u0435\u0435 \u0442\u0440\u0435\u0437\u0432\u043e \u043f\u043e\u0434\u043e\u0439\u0442\u0438 \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0439 \u0432 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438. <\/p>\n<p>  \u041c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0438 \u043f\u0440\u0438\u043d\u0443\u0434\u0438\u043b\u0438 \u043c\u0435\u043d\u044f \u0434\u043e\u043d\u043e\u0441\u0438\u0442\u044c \u0434\u043e \u043d\u0438\u0445 \u0447\u0443\u0436\u0438\u0435 \u0438\u0434\u0435\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u043d\u0435 \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u044e, \u0442\u0430\u043a \u043a\u0430\u043a \u0441\u0432\u043e\u0438 \u0441\u0447\u0438\u0442\u0430\u044e \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u0438 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u0432\u043d\u044b\u043c\u0438, \u0431\u043e\u043b\u0435\u0435 \u0437\u0434\u0440\u0430\u0432\u044b\u043c\u0438. \u041e\u043d\u0438 \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430, \u043d\u043e \u0432\u0440\u0435\u043c\u044f \u0435\u0449\u0435 \u0435\u0441\u0442\u044c. \u0425\u043e\u0447\u0443 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0443 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u043a \u0441\u0432\u043e\u0438\u043c \u0438\u0434\u0435\u044f\u043c \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u043a\u0443, \u0430 \u043d\u0435 \u043c\u0438\u043d\u0443\u0441\u044b \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445, \u043d\u0435 \u043f\u043e\u0434\u043a\u0440\u0435\u043f\u043b\u044f\u0435\u043c\u044b\u0435 \u0434\u043e\u0432\u043e\u0434\u0430\u043c\u0438. \u041b\u0438\u0447\u043d\u0443\u044e \u043d\u0435\u043f\u0440\u0438\u044f\u0437\u043d\u044c \u0438\u043b\u0438 \u00ab\u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u043e\u043d\u044f\u043b\u00bb \u0434\u043e\u0432\u043e\u0434\u043e\u043c \u0434\u043b\u044f \u043c\u0438\u043d\u0443\u0441\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043d\u0435 \u043c\u043e\u0433\u0443.<\/p>\n<p>  \u041d\u0435\u043e\u043f\u0440\u0430\u0432\u0434\u0430\u043d\u043d\u043e\u0435 \u0443\u0441\u043b\u043e\u0436\u043d\u0435\u043d\u0438\u0435 (\u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0421\u041b\u0410\u0423 \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b0f\/626\/d58\/b0f626d58290961fcb56170b469cc50d.svg\" alt=\"$N=2^{512} +1$\" data-tex=\"inline\"><\/math> \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 6000000\u00d76000000) \u0437\u0430\u0434\u0430\u0447\u0438 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b (\u0417\u0424\u0411\u0427) \u043f\u043e\u0434\u0432\u0438\u0433\u043b\u043e \u043c\u0435\u043d\u044f \u0441\u0435\u0440\u044c\u0435\u0437\u043d\u043e \u0437\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439. \u0423\u0436\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c <a href=\"https:\/\/habr.com\/ru\/post\/229601\/\">\u0432\u0441\u043a\u0440\u044b\u0442\u044c \u0437\u0430\u043a\u043e\u043d \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u0439 \u0421\u041d\u041d\u0427 \u0432 \u041d\u0420\u0427<\/a>, \u0442.\u0435. \u043f\u043e\u043d\u044f\u0442\u044c \u0433\u0434\u0435 \u0438 \u043a\u0430\u043a \u043f\u0440\u044f\u0447\u0443\u0442\u0441\u044f \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438 \u0432 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u043c \u0440\u044f\u0434\u0435 \u0447\u0438\u0441\u0435\u043b, \u0447\u0442\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0436\u0435 \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442 \u0438\u0445 \u043f\u043e\u0438\u0441\u043a \u0438 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0435\u043d\u0438\u0435.<br \/>  <a name=\"habracut\"><\/a>  <\/p>\n<h2>\u041c\u0435\u0442\u043e\u0434 \u0440\u0435\u0448\u0435\u0442\u0430 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u043b\u044f<\/h2>\n<p>  \u0421\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439 \u043d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0438\u0439 \u0434\u0435\u043d\u044c \u043c\u0435\u0442\u043e\u0434 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (10 \u043b\u0435\u0442 \u2014 \u043e\u0434\u043d\u043e \u0447\u0438\u0441\u043b\u043e). \u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u0440\u0435\u0448\u0435\u0442\u0430 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u043b\u044f (\u043a\u0430\u043a \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e Special Number Field Sieve SNFS) \u0442\u0430\u043a \u0438 \u043e\u0431\u0449\u0435\u0433\u043e (General Number Field Sieve \u2014 GNFS)) \u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 QS \u2014 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u0442\u0430, \u043f\u0440\u0435\u0436\u0434\u0435 \u0432\u0441\u0435\u0433\u043e, \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430\u0445 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 GNFS \u043d\u0435 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b Z, \u0430 \u0432 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u043c \u043f\u043e\u043b\u0435, \u0447\u0442\u043e \u043e\u0442\u0440\u0430\u0437\u0438\u043b\u043e\u0441\u044c \u0432 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0438 \u043c\u0435\u0442\u043e\u0434\u0430.<\/p>\n<p>  \u041a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 <a href=\"https:\/\/habr.com\/ru\/post\/521876\/\">\u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u0442\u0430<\/a> \u0432 \u043e\u0441\u043d\u043e\u0432\u0443 \u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0447\u0438\u0441\u0435\u043b \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u043b\u043e\u0436\u0435\u043d \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/611\/b2d\/ab3\/611b2dab3de8a69738be4c20c9be5164.svg\" alt=\"$P_d(x)$\" data-tex=\"inline\"><\/math> \u043d\u0435 2-\u0439, \u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 d&gt;2, \u0432 \u0442\u043e\u0447\u043a\u0435 x=m \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0439 \u0443\u0441\u043b\u043e\u0432\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2f1\/68b\/4fb\/2f168b4fb563cb04a5de05c500f7f6a6.svg\" alt=\"$P_d(m)=N$\" data-tex=\"inline\"><\/math>. \u0424\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430 \u043f\u0440\u0438\u043e\u0431\u0440\u0435\u043b\u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u0432\u0438\u0434 \u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043d\u0435\u0440\u0430\u0437\u043b\u043e\u0436\u0438\u043c\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043a\u043e\u043b\u044c\u0446\u0430 \u0446\u0435\u043b\u044b\u0445 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b. \u0418 \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u2014 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u0441\u043e\u043f\u0440\u043e\u0432\u043e\u0436\u0434\u0430\u044e\u0449\u0438\u0435 \u0442\u0435\u043a\u0441\u0442 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b.<\/p>\n<p>  <i>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435. <\/i>\u041f\u0443\u0441\u0442\u044c \u041a \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0435 \u043f\u043e\u043b\u0435. \u042d\u043b\u0435\u043c\u0435\u043d\u0442 \u03b8 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043d\u0430\u0434 \u043f\u043e\u043b\u0435\u043c \u041a, \u0435\u0441\u043b\u0438 \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u043d\u0435\u043c \u043a\u0430\u043a\u043e\u0433\u043e-\u043d\u0438\u0431\u0443\u0434\u044c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 f(x) \u0441 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 \u0438\u0437 \u043f\u043e\u043b\u044f \u041a.<br \/>  <i>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435. <\/i>\u041c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0441\u043e \u0441\u0442\u0430\u0440\u0448\u0438\u043c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u043e\u043c 1, \u0438\u043c\u0435\u044e\u0449\u0438\u0439 \u03b8 \u0441\u0432\u043e\u0438\u043c \u043a\u043e\u0440\u043d\u0435\u043c, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u043c \u0434\u043b\u044f \u03b8.\u0421\u0442\u0435\u043f\u0435\u043d\u044c\u044e \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u03b8 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0435\u0433\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430. \u0427\u0438\u0441\u043b\u0430\u043c\u0438, \u0441\u043e\u043f\u0440\u044f\u0436\u0435\u043d\u043d\u044b\u043c\u0438 \u0441 \u03b8, \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u0440\u043d\u0438 \u044d\u0442\u043e\u0433\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430.<\/p>\n<p>  \u041f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u0434\u0435\u043b\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u0440\u0438 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043d\u043e\u0440\u043c\u044b \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430. \u041a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 QS \u044d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u043e\u0442\u044b\u0441\u043a\u0438\u0432\u0430\u0435\u0442 \u0433\u043b\u0430\u0434\u043a\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u043a\u043e\u0440\u043d\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0433\u043e \u0438\u0437 N. \u0420\u0430\u0437\u043c\u0435\u0440 \u0447\u0438\u0441\u0435\u043b \u0441 \u0440\u043e\u0441\u0442\u043e\u043c N \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0442\u0435\u0442. \u0420\u043e\u0441\u0442 \u0436\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u043c\u0435\u0442\u043e\u0434\u0430 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0442\u0435\u043c, \u0447\u0442\u043e \u0441\u0430\u043c\u0438 \u0447\u0438\u0441\u043b\u0430 \u0432 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u043c \u043f\u043e\u043b\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u043a\u043e\u043b\u044c\u0446\u0435, \u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0434\u043b\u044f \u043d\u0438\u0445 \u0441\u0442\u0430\u0442\u044c \u0433\u043b\u0430\u0434\u043a\u0438\u043c\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0432\u044b\u0448\u0435 \u0447\u0435\u043c \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 QS, \u043d\u043e \u0441\u0430\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432 NFS \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u0435\u0435. <\/p>\n<p>  \u0422\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0430\u0432\u0442\u043e\u0440 [3] \u0441\u0447\u0438\u0442\u0430\u0435\u0442 \u043d\u0435\u043f\u0440\u0430\u0432\u043e\u043c\u0435\u0440\u043d\u044b\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u0432 \u043d\u0435\u043c \u043d\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u044d\u0442\u0430\u043f\u0430\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432. \u0414\u0440\u0443\u0433\u0438\u0435 \u0430\u0432\u0442\u043e\u0440\u044b \u043d\u0435 \u0432\u043f\u043e\u043b\u043d\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u044e\u0442 \u0442\u0430\u043a\u0443\u044e \u043f\u043e\u0437\u0438\u0446\u0438\u044e.<\/p>\n<p>  \u041c\u0435\u0442\u043e\u0434 GNFS \u0432\u043a\u043b\u044e\u0447\u0430\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0442\u043f\u0440\u0430\u0432\u043d\u044b\u0445 \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0439, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u044f\u0435\u043c\u044b\u0435 \u043d\u0438\u0436\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f \u043f\u043e \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440.<\/p>\n<p>  <u>\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u0432 GNFS<\/u><br \/>  1. \u041f\u0443\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u043d\u043e N \u2013 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u043e\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c.<br \/>  \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d, \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e d&gt;3 (\u043f\u0440\u0438 d=2 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430 \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u0442\u0430).<\/p>\n<p>  2. \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u0446\u0435\u043b\u043e\u0435 m \u0442\u0430\u043a\u043e\u0435, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/508\/b68\/a2b\/508b68a2b07ca7c626d60938bdeb67b6.svg\" alt=\"$[N^{1\/(d+1)}] &lt;m&lt;[N^{1\/d}]$\" data-tex=\"inline\"><\/math>, \u0438 \u0440\u0430\u0437\u043b\u043e\u0436\u0438\u043c N \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044e m: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c5f\/260\/ddc\/c5f260ddc6382bcb69c05a6a18a6416f.svg\" alt=\"$N = m^d+ a_{d-1}m^{d-1} +...+a_0$\" data-tex=\"inline\"><\/math>. (1)<\/p>\n<p>  3. \u0421\u0432\u044f\u0436\u0435\u043c \u0441 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435\u043c (1) \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u043e\u0442 \u0445 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Z[x] \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 \u0441 \u0446\u0435\u043b\u044b\u043c\u0438 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0430\u043c\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11d\/cdd\/c70\/11dcddc7000c01b6ed710f2b6e379a56.svg\" alt=\"$f_1(x)= x^d+ a_{d-1}x^{d-1} +...+a_0$\" data-tex=\"inline\"><\/math>. \u0412 \u0442\u043e\u0447\u043a\u0435 m <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f91\/6ba\/a7b\/f916baa7ba5af7c4be651473e61aa216.svg\" alt=\"$ f_1(m)=N$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  4. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6a6\/b49\/409\/6a6b4940972c24a7c72e2a00e7a527d0.svg\" alt=\"$F_1(a,b)$\" data-tex=\"inline\"><\/math> \u043a\u0430\u043a \u043e\u0434\u043d\u043e\u0440\u043e\u0434\u043d\u044b\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u043e\u0442 \u0434\u0432\u0443\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e53\/ca7\/21a\/e53ca721aebbc9d992c96f9a5f456a04.svg\" alt=\"$a, b $\" data-tex=\"inline\"><\/math>: <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0e4\/858\/b17\/0e4858b17d4bc99a8cb645c58966daf5.svg\" alt=\"$F_1(a,b) = b^d\u00b7f_1(a\/b) =a^d+ a_{d-1}a^{d-1}b +a_{d-2}a^{d-1}b^2 +...+a_0b^d$\" data-tex=\"inline\"><\/math>. (2)<\/p>\n<p>  5. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2dd\/11f\/c70\/2dd11fc70c52b59ad3e58fdecfaa0a2d.svg\" alt=\"$f_2(x) = x - m$\" data-tex=\"inline\"><\/math> \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043e\u0434\u043d\u043e\u0440\u043e\u0434\u043d\u044b\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u043f\u043e \u0434\u0440\u0443\u0433\u043e\u0439 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6da\/bf5\/683\/6dabf568343d00174716426961832ddc.svg\" alt=\"$F_2(a, b) = a - bm$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  6. \u0412\u044b\u0431\u0435\u0440\u0435\u043c \u0434\u0432\u0430 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/84e\/000\/72e\/84e00072e5de4da6eae3beb75be2636e.svg\" alt=\"$L_1, L_2 $\" data-tex=\"inline\"><\/math>, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0438\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f (\u0430\u043d\u0433\u043b. sieve region): SR = {<math>$inline$1\u2264b\u2264 L_1, &#8212; L_2 \u2264a\u2264 L_2$inline$<\/math>} \u0432 \u0444\u043e\u0440\u043c\u0435 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a\u0430.<\/p>\n<p>  <u>\u0424\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u044b\u0445 \u0431\u0430\u0437<\/u><br \/>  7. \u041f\u0443\u0441\u0442\u044c \u03b8 \u2014 \u043a\u043e\u0440\u0435\u043d\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dac\/1ae\/c3c\/dac1aec3c00257503ca6958ad045aa0f.svg\" alt=\"$f_1(x)$\" data-tex=\"inline\"><\/math>. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043a\u043e\u043b\u044c\u0446\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 Z[\u03b8]. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043a\u043e\u043b\u044c\u0446\u0430, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0435 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0439 <i>\u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u043e\u0439<\/i> FB1, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0438\u0437 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0432\u0438\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4ff\/5fd\/b41\/4ff5fdb41e22e115c0bf88972715e7a7.svg\" alt=\"$a - b\u03b8$\" data-tex=\"inline\"><\/math> \u0441 \u043d\u043e\u0440\u043c\u043e\u0439 (2), \u044f\u0432\u043b\u044f\u044e\u0449\u0435\u0439\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0447\u0438\u0441\u043b\u043e\u043c. \u042d\u0442\u0438 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u044b \u2014\u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043d\u0435\u0440\u0430\u0437\u043b\u043e\u0436\u0438\u043c\u044b\u0435 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0446\u0435\u043b\u044b\u0445 \u043f\u043e\u043b\u044f K= Q[\u03b8]. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u043c \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043d\u043e\u0440\u043c \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u0438\u0437 FB1 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439 B1.<\/p>\n<p>  8. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u0443\u044e \u0431\u0430\u0437\u0443 FB2, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0443\u044e \u0438\u0437 \u0432\u0441\u0435\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u044b\u0445 \u0441\u0432\u0435\u0440\u0445\u0443 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439 B2.<\/p>\n<p>  9. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e FB3, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u043e\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u043e\u0439 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0445 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u043e\u0432. \u042d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u043e\u0432 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/29f\/814\/e6e\/29f814e6e25b433f2207caef29ba5f8c.svg\" alt=\"$c - d\u03b8$\" data-tex=\"inline\"><\/math>, \u043d\u043e\u0440\u043c\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u0414\u043e\u043b\u0436\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c\u0441\u044f \u0443\u0441\u043b\u043e\u0432\u0438\u0435 FB1\u2229FB3 =\u2205.<\/p>\n<p>  <u>\u041f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430<\/u><br \/>  10. \u0412\u044b\u043f\u043e\u043b\u043d\u0438\u043c \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0435 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 <br \/>  {<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1f0\/8aa\/632\/1f08aa6326def50114d0bbc14cdf9434.svg\" alt=\"$a - b\u03b8 | (a,b) \u0454 SR$\" data-tex=\"inline\"><\/math>} \u043f\u043e \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u0435 FB1 \u0438 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <br \/>  {<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e7c\/7bf\/502\/e7c7bf50224c9fbbd753d4e141dbf72c.svg\" alt=\"$a - bm |(a,b) \u0454 SR$\" data-tex=\"inline\"><\/math>} \u043f\u043e \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u0435 FB2. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e M, (\u0442\u0430\u0431\u043b. \u0413) \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0435\u0435 \u0438\u0437 \u0433\u043b\u0430\u0434\u043a\u0438\u0445 \u043f\u0430\u0440 (a, b), \u0442\u043e \u0435\u0441\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u043f\u0430\u0440 (a, b), \u0447\u0442\u043e \u041d\u041e\u0414(a,b)= 1, \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u0438 \u0447\u0438\u0441\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4ff\/5fd\/b41\/4ff5fdb41e22e115c0bf88972715e7a7.svg\" alt=\"$a - b\u03b8$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f9a\/f62\/08c\/f9af6208ce77a85f221375afb9b7c660.svg\" alt=\"$a - bm$\" data-tex=\"inline\"><\/math> \u0440\u0430\u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u043e \u0431\u0430\u0437\u0430\u043c FB1 \u0438 FB2 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e.<\/p>\n<p>  11. \u041d\u0430\u0439\u0434\u0451\u043c (\u043a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 QS) \u0442\u0430\u043a\u043e\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e S \u2286M, \u0447\u0442\u043e <br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d5c\/75d\/792\/d5c75d7925a95b00dd9b53df27c42214.svg\" alt=\"$\u041f_{(a,b)\u0454 S}Nr(a - b\u03b8) = H^2, H\u0454Z$\" data-tex=\"inline\"><\/math>; \u0437\u0434\u0435\u0441\u044c Nr \u2014 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043d\u043e\u0440\u043c\u044b \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430;<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cdb\/c66\/965\/cdbc669650357ef7ba0f2a103fcae550.svg\" alt=\"$\u041f_{(a,b)\u0454 S}(a - bm) = B^2, B\u0454Z$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <u>\u0424\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u043b\u043d\u044b\u0445 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432 \u0438\u0437 \u043f\u0430\u0440 \u0433\u043b\u0430\u0434\u043a\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/u><br \/>  12. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a0c\/452\/1fe\/a0c4521fe81e2abf58cc50ba41fbeaa8.svg\" alt=\"$g(\u03b8) = f^{'2}_1(\u03b8)\u041f_{(a,b)\u0454 S}(a - b\u03b8)$\" data-tex=\"inline\"><\/math>, <br \/>  \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9d8\/43f\/8e1\/9d843f8e1eab52bb84bcf2fe5ac1800b.svg\" alt=\"$f^{'}_1(\u03b8)$\" data-tex=\"inline\"><\/math> \u2014 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u043d\u0430\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b40\/f14\/fca\/b40f14fca86695b5207a89bd2d4c3e7d.svg\" alt=\"$f_1(\u03b8)$\" data-tex=\"inline\"><\/math>.<br \/>  13. \u041c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d g(\u03b8) \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u044b\u043c \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u043c \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 Z(\u03b8). \u041f\u0443\u0441\u0442\u044c \u0442\u043e\u0433\u0434\u0430 \u03b1(\u03b8) \u0435\u0441\u0442\u044c \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 g(\u03b8) \u0438 B \u2014 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5ee\/71e\/dd1\/5ee71edd1e7eb1736d3069fa33dc3565.svg\" alt=\"$B^2$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  14. \u0421\u0442\u0440\u043e\u0438\u043c \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0444: \u03b8 \u2192 m, \u0437\u0430\u043c\u0435\u043d\u044f\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c \u03b1(\u03b8) \u0447\u0438\u0441\u043b\u043e\u043c \u03b1(m). \u042d\u0442\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u043b\u044c\u0446\u0435\u0432\u044b\u043c \u0433\u043e\u043c\u043e\u043c\u043e\u0440\u0444\u0438\u0437\u043c\u043e\u043c \u043a\u043e\u043b\u044c\u0446\u0430 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9c7\/554\/38e\/9c755438e4b81d4e4c62339142a769e6.svg\" alt=\"$Z_K$\" data-tex=\"inline\"><\/math> \u0432 \u043a\u043e\u043b\u044c\u0446\u043e Z, \u043e\u0442\u043a\u0443\u0434\u0430 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435: <br \/>  <math>$inline$A^2 =g(m)^2\u2261\u0444(g(\u03b1))^2\u2261\u0444(f^{&#8216;2}_1(\u03b8)\u00b7\u041f_{(a,b)\u0454 S}(a &#8212; b\u03b8))\u2261$inline$<\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2b3\/e20\/799\/2b3e20799862823c63c1262e0a1ddfb3.svg\" alt=\"$ \u2261f^{'2}_1(m)\u00b7\u041f_{(a,b)\u0454 S}(a - bm)\u2261f^{'2}_1(m)\u00b7C^2 (mod N)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <u>\u0417\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u0435 \u0417\u0424\u0411\u0427<\/u><br \/>  15. \u041f\u0443\u0441\u0442\u044c B=f &#8216;(m)\u00b7C. \u041d\u0430\u0439\u0434\u0451\u043c \u043f\u0430\u0440\u0443 \u0447\u0438\u0441\u0435\u043b (A, B) \u0442\u0430\u043a\u0438\u0445, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e9f\/62a\/ece\/e9f62aece9ac358c300249f54a5bd635.svg\" alt=\"$A^2\u2261B^2(mod N).$\" data-tex=\"inline\"><\/math> \u0422\u043e\u0433\u0434\u0430 \u043d\u0430\u0439\u0434\u0451\u043c \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u0447\u0438\u0441\u043b\u0430 N, \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044f \u041d\u041e\u0414(N, A \u00b1 B), \u043a\u0430\u043a \u044d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442\u0441\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u0442\u0430.<\/p>\n<p>  \u042d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043f\u0443\u043d\u043a\u0442\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u0443\u043a\u0440\u0443\u043f\u043d\u0438\u0442\u044c \u0434\u043e \u0442\u0440\u0435\u0445 \u044d\u0442\u0430\u043f\u043e\u0432 <br \/>  I. \u041a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 QS \u0432\u043d\u0430\u0447\u0430\u043b\u0435 \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0441\u0440\u0435\u0434\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u0436\u0438\u0434\u0430\u044e\u0442\u0441\u044f \u0433\u043b\u0430\u0434\u043a\u0438\u0435, \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430 \u0438\u0437 \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 Z\/nZ, \u0432\u043a\u043b\u044e\u0447\u0430\u044e\u0449\u0430\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8a9\/85f\/631\/8a985f6317335e6c85bc3271b223a9a1.svg\" alt=\"$a_p\u220aZ\/nZ, a_p\u22600$\" data-tex=\"inline\"><\/math>, \u0433\u0434\u0435 \u0440 \u043f\u0440\u043e\u0431\u0435\u0433\u0430\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a1f\/02e\/c92\/a1f02ec9233f200d61b1123e826f02c2.svg\" alt=\"$\u0420_0$\" data-tex=\"inline\"><\/math>. \u0421\u0438\u043c\u0432\u043e\u043b\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0ea\/a75\/c8c\/0eaa75c8c0efaae1b4171115d8ae1f8d.svg\" alt=\"$Z^{P_0}$\" data-tex=\"inline\"><\/math> \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0432\u0435\u043a\u0442\u043e\u0440\u044b |<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a1f\/02e\/c92\/a1f02ec9233f200d61b1123e826f02c2.svg\" alt=\"$\u0420_0$\" data-tex=\"inline\"><\/math>|; <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0ea\/a75\/c8c\/0eaa75c8c0efaae1b4171115d8ae1f8d.svg\" alt=\"$Z^{P_0}$\" data-tex=\"inline\"><\/math> = {<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/882\/874\/b33\/882874b33978fbbd7f7f496db4b67340.svg\" alt=\"$(v_p)_{p\u220aP_0}|v_p\u220aZ$\" data-tex=\"inline\"><\/math>}.<\/p>\n<p>  \u0414\u0430\u043b\u0435\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a4c\/4af\/5d1\/a4c4af5d1ca3d8d0a8cb87fb741feba7.svg\" alt=\"$f:Z^{P_0}\u2192(Z\/nZ)^*$\" data-tex=\"inline\"><\/math>; <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/849\/a21\/17b\/849a2117b0ab46edb6bb2192259f21e4.svg\" alt=\"$f((v_p)_{p\u220aP_0}) = \u041f_{p\u220aP_0}a^{v_p}_p(mod N)$\" data-tex=\"inline\"><\/math>.<br \/>  \u042d\u0442\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 <i>\u043d\u0430<\/i> \u2014 \u0441\u044e\u0440\u044a\u0435\u043a\u0446\u0438\u044f, \u0435\u0441\u043b\u0438 {<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/578\/745\/381\/578745381cda4730a5a2239bd1c3b821.svg\" alt=\"$a_p$\" data-tex=\"inline\"><\/math>} \u043f\u043e\u0440\u043e\u0436\u0434\u0430\u044e\u0442 (Z\/nZ)*; \u043e\u0431\u044b\u0447\u043d\u043e \u0442\u0430\u043a \u0438 \u0431\u044b\u0432\u0430\u0435\u0442.<\/p>\n<p>  II. \u041f\u043e\u0438\u0441\u043a \u0438 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0439. \u041e\u0442\u044b\u0441\u043a\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0432\u0435\u043a\u0442\u043e\u0440\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/009\/901\/d01\/009901d016265381d829b6d904d7c5c8.svg\" alt=\"$v \u220a Kerf$\" data-tex=\"inline\"><\/math>, \u0442.\u0435. \u0442\u0430\u043a\u0438\u0435<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1b0\/40c\/8b4\/1b040c8b43228f92323b5e38acd45e9d.svg\" alt=\"$v=(v_p)_{p\u220aP_0}$\" data-tex=\"inline\"><\/math>, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0f5\/17d\/1d3\/0f517d1d37884066aa88d63df168ac1f.svg\" alt=\"$\u041f_{p\u220aP_0}a^{v_p}_p\u22611(mod N)$\" data-tex=\"inline\"><\/math>.\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 V ={<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/009\/901\/d01\/009901d016265381d829b6d904d7c5c8.svg\" alt=\"$v \u220a Kerf$\" data-tex=\"inline\"><\/math>} \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435 |<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a1f\/02e\/c92\/a1f02ec9233f200d61b1123e826f02c2.svg\" alt=\"$\u0420_0$\" data-tex=\"inline\"><\/math>|<\/p>\n<p>  III \u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u0435 \u0417\u0424\u0411\u0427.<br \/>  \u041e\u0442\u044b\u0441\u043a\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043d\u0435\u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0434\u0432\u0430, \u043f\u043e\u0434\u043e\u0431\u043d\u043e \u043c\u0435\u0442\u043e\u0434\u0443 QS, \u0434\u043b\u044f \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u03d1 \u220aV; \u0438\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0438\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c, \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u0442\u0430\u043a\u0430\u044f \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442. \u041e\u043d\u0430 \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. <\/p>\n<p>  \u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u043d\u0430\u0434 \u043f\u043e\u043b\u0435\u043c Z\/2Z. \u0415\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e W \u2286 V. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043f\u0440\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/902\/674\/354\/90267435491190fda1a008355cbd7769.svg\" alt=\"$\u0425 \u2261 f(W)(mod N) $\" data-tex=\"inline\"><\/math>\u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 <br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1f6\/9fe\/bea\/1f69febeaf0e64a985aab21b822ef7ba.svg\" alt=\"$X^2 \u2261 f(2W )\u22611(mod N). $\" data-tex=\"inline\"><\/math><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u043c\u043e\u0441\u0442\u044c \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/827\/34b\/47f\/82734b47f1d03a07ef86747f7a96d7b8.svg\" alt=\"$X&lt; \u041d\u041e\u0414(X \u2213 1, N) &lt;N$\" data-tex=\"inline\"><\/math>. \u0415\u0441\u043b\u0438 \u043e\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e, \u0442\u043e \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c N \u043d\u0430\u0439\u0434\u0435\u043d \u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f. \u0418\u043d\u0430\u0447\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u0441\u044f \u043b\u0438\u0431\u043e \u043d\u0430 2-\u0439 \u044d\u0442\u0430\u043f, \u043b\u0438\u0431\u043e \u043d\u0430 1-\u0439, \u0433\u0434\u0435 \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043d\u043e\u0432\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430.<\/p>\n<h3>\u041c\u0435\u0442\u043e\u0434 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0447\u0438\u0441\u0435\u043b GNFS \u043a\u0440\u0443\u043f\u043d\u044b\u043c\u0438 \u043c\u0430\u0437\u043a\u0430\u043c\u0438 (\u0441 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u043e\u043c \u0434\u0435\u0442\u0430\u043b\u0435\u0439)<\/h3>\n<p>  \u0414\u0430\u043b\u0435\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430 GNFS. \u0412 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u0438\u0435 \u0432\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a\u043e\u043b\u044c\u0446\u043e Z [\u03b1], \u0433\u0434\u0435 \u03b1 \u2013 \u043a\u043e\u0440\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d93\/13f\/8d0\/d9313f8d06735d6988074f717265c2ac.svg\" alt=\"$f(x)$\" data-tex=\"inline\"><\/math>, \u0430 \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043f\u0440\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b41\/cdf\/134\/b41cdf134ceb2fa85056c51384127e42.svg\" alt=\"$x=m, f(m)\u22610(mod N)$\" data-tex=\"inline\"><\/math>, \u043b\u0435\u0433\u043a\u043e \u043c\u043e\u0436\u043d\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u043c\u043e\u0440\u0444\u0438\u0437\u043c\u0435 \u03c6 \u043a\u043e\u043b\u0435\u0446, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/703\/3c6\/c09\/7033c6c09a6200c56363b22cde9ec265.svg\" alt=\"$\u03c6: Z [\u03b1] \u2192 Zn$\" data-tex=\"inline\"><\/math>, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c\u043e\u043c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/27e\/fcc\/a73\/27efcca73e9d18a5faed0719996b6699.svg\" alt=\"$\u03c6(\u03b1) = m.$\" data-tex=\"inline\"><\/math>\u041f\u043e\u044f\u0441\u043d\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0443\u0442 \u0434\u0430\u043d\u044b \u0447\u0443\u0442\u044c \u043d\u0438\u0436\u0435, \u043f\u043e\u0441\u043b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u0430.<\/p>\n<p>  \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u0430\u043a\u0438\u043c-\u0442\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c \u0443\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u043f\u0430\u0440\u0443 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18c\/f7c\/6c8\/18cf7c6c837875a0e32362521debb8ac.svg\" alt=\"$(a, b)$\" data-tex=\"inline\"><\/math> \u0442\u0430\u043a\u0438\u0445, \u0447\u0442\u043e \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u0432\u0438\u0434\u0430 (\u044d\u0442\u043e \u043e\u0434\u043d\u043e \u0438\u0437 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0421\u041b\u0410\u0423) <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e02\/b22\/da1\/e02b22da147f22be123bd0f32934f60e.svg\" alt=\"$a +bm =x^2$\" data-tex=\"inline\"><\/math> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1b5\/eb9\/7f9\/1b5eb97f92745c5c1a5b19127fd2ce01.svg\" alt=\"$Z_n$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/879\/e2e\/d65\/879e2ed65348fa6847d2f56326f9f173.svg\" alt=\"$a +b\u03b1 = \u03b2^2$\" data-tex=\"inline\"><\/math> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Z[\u03b1]<\/p>\n<p>  \u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u043c\u043e\u0440\u0444\u0438\u0437\u043c\u0430 \u03c6 \u043a\u043e \u0432\u0442\u043e\u0440\u043e\u043c\u0443 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0443 \u0434\u0430\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/259\/392\/8f3\/2593928f37e48b51025f6deb4b1c18eb.svg\" alt=\"$a+bm =\u03c6(\u03b2^2)= y^2$\" data-tex=\"inline\"><\/math> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Zn, \u0442.\u0435. \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/997\/78d\/baf\/99778dbaf66587327dc6a5f3470a0944.svg\" alt=\"$x^2 \u2261y^2modN$\" data-tex=\"inline\"><\/math>, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442, \u0445\u043e\u0442\u044f \u0431\u044b \u0432 \u043e\u0434\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0438\u0437 \u0434\u0432\u0443\u0445 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043d\u0435\u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0447\u0438\u0441\u043b\u0430 N. <\/p>\n<p>  \u0414\u0435\u043b\u043e \u0437\u0434\u0435\u0441\u044c \u043d\u0435 \u0432 \u043a\u0430\u0436\u0443\u0449\u0435\u043c\u0441\u044f \u0443\u0441\u043b\u043e\u0436\u043d\u0435\u043d\u0438\u0438 \u0437\u0430\u0434\u0430\u0447\u0438, \u043a\u043e\u0433\u0434\u0430 \u043f\u0430\u0440\u044b \u0447\u0438\u0441\u0435\u043b \u043e\u0442\u044b\u0441\u043a\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e \u0432 \u0438\u0442\u043e\u0433\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044e \u0434\u0432\u0443\u0445 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432, \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u044b\u0445 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e N \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0432 \u0434\u0432\u0443\u0445 \u043a\u043e\u043b\u044c\u0446\u0430\u0445 \u0440\u0430\u0437\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 m \u0431\u0435\u0440\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u044b\u043c \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 N, \u0442\u043e \u0438 \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18c\/f7c\/6c8\/18cf7c6c837875a0e32362521debb8ac.svg\" alt=\"$(a, b)$\" data-tex=\"inline\"><\/math> \u043e\u0442\u044b\u0441\u043a\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u0440\u0435\u0434\u0438 \u043c\u0430\u043b\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. <\/p>\n<p>  \u0422\u0435\u0440\u044f\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438 \u0432\u044b\u0431\u043e\u0440\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043d\u0430 \u0434\u0432\u0430 \u043a\u043e\u043b\u044c\u0446\u0430, \u043c\u0435\u0442\u043e\u0434 \u0432 \u0446\u0435\u043b\u043e\u043c \u0432\u044b\u0438\u0433\u0440\u044b\u0432\u0430\u0435\u0442 \u0437\u0430 \u0441\u0447\u0435\u0442 \u043c\u0430\u043d\u0438\u043f\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u043f\u043e \u043d\u043e\u0440\u043c\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c\u0438 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0430\u043c\u0438, \u0447\u0442\u043e \u0441\u043a\u043e\u0440\u0435\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044e \u043f\u043e\u043b\u043d\u044b\u0445 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432.<\/p>\n<p>  <b>\u041f\u0420\u0418\u041c\u0415\u0420<\/b><br \/>  \u041f\u0443\u0441\u0442\u044c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/83d\/7bc\/4cc\/83d7bc4cc367c76e59ae37774fd9acfd.svg\" alt=\"$N = 322525537.$\" data-tex=\"inline\"><\/math> <br \/>  \u0417\u0430\u0434\u0430\u0434\u0438\u043c d = 4 \u0438 \u043d\u0430\u0439\u0434\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/275\/7a2\/e65\/2757a2e65b8f8041d6ef811f1ea1ca38.svg\" alt=\"$N^{1\/4}\u2245134,0111$\" data-tex=\"inline\"><\/math>. \u041f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ba4\/01d\/c09\/ba401dc096a833f8cb6623e01c152d55.svg\" alt=\"$m = 134$\" data-tex=\"inline\"><\/math>. \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u043b\u0430 N \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ba4\/01d\/c09\/ba401dc096a833f8cb6623e01c152d55.svg\" alt=\"$m = 134$\" data-tex=\"inline\"><\/math>:<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/838\/ded\/ad9\/838dedad91acc133760f14165ac4c56f.svg\" alt=\"$N = 134^4 + 6\u00b7134^2 \u2013 134 - 1 = 322417936 + 107736 -134 - 1 = 322525537.$\" data-tex=\"inline\"><\/math><\/p>\n<p>  \u0414\u0430\u043b\u0435\u0435 \u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/912\/819\/fc1\/912819fc1aa5c04db31c47a41a7efd85.svg\" alt=\"$f(x) = x^4 + 6x^2 \u2013 x \u2013 1$\" data-tex=\"inline\"><\/math>. \u041f\u0443\u0441\u0442\u044c \u03b1 \u2013 \u043a\u043e\u0440\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d93\/13f\/8d0\/d9313f8d06735d6988074f717265c2ac.svg\" alt=\"$ f(x)$\" data-tex=\"inline\"><\/math>. \u041f\u0430\u0440\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d64\/dc8\/cf8\/d64dc8cf88bbe65653552ef97ed0afb9.svg\" alt=\"$(a, b) = (10, 1) $\" data-tex=\"inline\"><\/math>-\u0442\u0430 \u0441\u0430\u043c\u0430\u044f \u00ab\u0447\u0443\u0434\u0435\u0441\u043d\u0430\u044f\u00bb \u043f\u0430\u0440\u0430. \u0414\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0441 \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Zn, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c77\/32f\/8ed\/c7732f8ed3156228a504b4381a08d5a5.svg\" alt=\"$10+m=10+134=12^2,$\" data-tex=\"inline\"><\/math> \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b <math>$inline$10+\u03b1 =\u03b1^ 4+6\u03b1^2+9(\u03b1^2+3)^2$inline$<\/math>\u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Z[\u03b1]. <\/p>\n<p>  \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u0430\u043a\u0438\u043c-\u0442\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c \u0443\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u043f\u0430\u0440\u0443 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18c\/f7c\/6c8\/18cf7c6c837875a0e32362521debb8ac.svg\" alt=\"$(a, b)$\" data-tex=\"inline\"><\/math> \u0442\u0430\u043a\u0438\u0445, \u0447\u0442\u043e \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u0432\u0438\u0434\u0430<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e02\/b22\/da1\/e02b22da147f22be123bd0f32934f60e.svg\" alt=\"$ a + bm = x^2$\" data-tex=\"inline\"><\/math> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Zn \u0438<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/879\/e2e\/d65\/879e2ed65348fa6847d2f56326f9f173.svg\" alt=\"$ a + b\u03b1 = \u03b2^2$\" data-tex=\"inline\"><\/math> \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Z [\u03b1].<\/p>\n<p>  \u041f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u043c\u043e\u0440\u0444\u0438\u0437\u043c \u03c6 \u043a \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/23d\/806\/aa9\/23d806aa94fb64b1943f58ef31e34e63.svg\" alt=\"$(\u03b1^2 + 3)^2$\" data-tex=\"inline\"><\/math>. \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2b0\/4f4\/d0c\/2b04f4d0cc16d489bf113200bea4b2a9.svg\" alt=\"$(m^2 + 3)^2$\" data-tex=\"inline\"><\/math>, \u0442.\u0435. <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/904\/18c\/a78\/90418ca78c1e589cd3a60866d0eaa952.svg\" alt=\"$17959^2$\" data-tex=\"inline\"><\/math>. <br \/>  \u0412 \u0438\u0442\u043e\u0433\u0435 \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ac9\/4dc\/b0b\/ac94dcb0b050aa36cade4b1caaba245c.svg\" alt=\"$12^2\u2261 17959^2(mod N)$\" data-tex=\"inline\"><\/math>, \u0438\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/163\/23c\/2a1\/16323c2a1156383e587d6e9ad4c10a21.svg\" alt=\"$(17959 \u2013 12)(17959 + 12) \u2261 0(mod N).$\" data-tex=\"inline\"><\/math> <br \/>  \u0420\u0435\u0448\u0430\u044f \u0435\u0433\u043e, \u0441 \u043f\u0440\u0438\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u041d\u041e\u0414 \u0415\u0432\u043a\u043b\u0438\u0434\u0430, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/273\/f25\/1d1\/273f251d1ab5354687058233cd158ddb.svg\" alt=\"$d = 17959+12=17971,$\" data-tex=\"inline\"><\/math> \u0442.\u0435. \u043d\u0435\u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044f \u0447\u0438\u0441\u043b\u0430 N, \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0440\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0438 2-\u0439.<br \/>  \u0414\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a8e\/958\/bfb\/a8e958bfb576b186836d4fcc639fecea.svg\" alt=\"$17971\u00d717947 = 322525537$\" data-tex=\"inline\"><\/math>, \u0442.\u0435. \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043e.<\/p>\n<p>  \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430\u044f \u043f\u0430\u0440\u0430 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18c\/f7c\/6c8\/18cf7c6c837875a0e32362521debb8ac.svg\" alt=\"$(a, b)$\" data-tex=\"inline\"><\/math> \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u0439\u0434\u0435\u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c. <\/p>\n<p>  \u041c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0431\u0430\u0437\u0438\u0441\u043d\u044b\u043c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435\u043c \u043d\u0430 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438. \u0412\u043d\u0430\u0447\u0430\u043b\u0435 \u0438\u0449\u0435\u043c \u0442\u0430\u043a\u0438\u0435 \u043f\u0430\u0440\u044b \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/18c\/f7c\/6c8\/18cf7c6c837875a0e32362521debb8ac.svg\" alt=\"$(a, b)$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e\u0431\u044b \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u043a\u043e\u043b\u044c\u0446\u0430\u0445 \u0441\u0443\u043c\u043c\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/32d\/029\/67f\/32d02967f9b3c48dadf89fd0bc617ca5.svg\" alt=\"$a = bm$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/07b\/0fb\/058\/07b0fb05837819f51545ce0a6bd5cbf8.svg\" alt=\"$a = b\u03b1$\" data-tex=\"inline\"><\/math> \u0438\u043c\u0435\u043b\u0438 \u0432 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f\u0445 \u043c\u0430\u043b\u044b\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430 (\u0438\u043b\u0438 \u0438\u0445 \u0441\u0442\u0435\u043f\u0435\u043d\u0438).<\/p>\n<p>  \u0424\u043e\u0440\u043c\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0434\u0432\u0430 \u0431\u0430\u0437\u0438\u0441\u0430: \u0431\u0430\u0437\u0438\u0441 F\u04121 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u041c (\u041c-\u0433\u043b\u0430\u0434\u043a\u043e\u0435 \u0447\u0438\u0441\u043b\u043e), \u0438 \u0434\u0440\u0443\u0433\u043e\u0439 \u0431\u0430\u0437\u0438\u0441 FB2, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u043a\u043e\u043b\u044c\u0446\u0430 Z[\u03b1].<br \/>  \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043f\u0430\u0440\u0443 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2d3\/a5b\/8ea\/2d3a5b8ea073331c30c338f8896a5648.svg\" alt=\"$a + bm = \u041f_{p\u0454FB1}p^{\u03bc_p} $\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0bc\/082\/f68\/0bc082f682ce583fbe9a5d8df34bc5b2.svg\" alt=\"$a + b\u03b1 = \u041f_{g\u0454FB2}g^{\u03c5_g}$\" data-tex=\"inline\"><\/math>\u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u043c\u043e\u0440\u0444\u0438\u0437\u043c \u03c6 \u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043a\u043e\u043b\u0435\u0446 \u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2e1\/146\/fd5\/2e1146fd530b0825101c866beba042dc.svg\" alt=\"$\u041f_{p\u0454FB1}p^{\u03bc_p}=\u041f_{g\u0454B2}\u03c6(g)^{\u03c5_g}.$\" data-tex=\"inline\"><\/math><\/p>\n<p>  \u041a\u043e\u0433\u0434\u0430 \u043d\u0430\u043a\u043e\u043f\u0438\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e #F\u04121 +#FB2 + 1 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432 \u0442\u0430\u043a\u043e\u0433\u043e \u0432\u0438\u0434\u0430, \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044f \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u044b \u043f\u043e mod2 \u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/80c\/cb9\/377\/80ccb9377eb7711a7c21aaff491ad8d8.svg\" alt=\"$x^2\u2261 y^2(mod N)$\" data-tex=\"inline\"><\/math>. \u0412 \u044d\u0442\u043e\u043c \u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430.<\/p>\n<p>  \u041e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0430\u0437\u0438\u0441\u0430 FB2 \u0441\u043a\u0430\u0436\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435. \u0412 FB2 \u043c\u043e\u0436\u043d\u043e \u0432\u043a\u043b\u044e\u0447\u0438\u0442\u044c \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043d\u0435\u0440\u0430\u0437\u043b\u043e\u0436\u0438\u043c\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043a\u043e\u043b\u044c\u0446\u0430 Z [\u03b1]. \u041f\u043e\u043d\u044f\u0442\u0438\u0435 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 Z [\u03b1] \u0441\u0432\u044f\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u043d\u043e\u0440\u043c\u043e\u0439, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0435\u0439 \u043f\u0440\u0438\u0434\u0430\u0442\u044c \u044d\u0442\u043e\u043c\u0443 \u0442\u0435\u0440\u043c\u0438\u043d\u0443 \u0442\u043e\u0447\u043d\u044b\u0439 \u0441\u043c\u044b\u0441\u043b. \u0412 \u043a\u043e\u043b\u044c\u0446\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0438 \u0435\u0434\u0438\u043d\u0438\u0446\u044b, \u0442.\u0435. \u043e\u0431\u0440\u0430\u0442\u0438\u043c\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043a\u043e\u043b\u044c\u0446\u0430. <\/p>\n<p>  \u0412\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441 \u043e\u0431 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u0442\u0430\u043a\u0438\u0445 \u0435\u0434\u0438\u043d\u0438\u0446 \u0438 \u043d\u0435\u0440\u0430\u0437\u043b\u043e\u0436\u0438\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043a\u043e\u043b\u044c\u0446\u0430. \u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0432 \u043a\u043e\u043b\u044c\u0446\u0430\u0445 Z [\u03b1] \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0435 \u043c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u0438 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c. \u041f\u0440\u0435\u043e\u0434\u043e\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u0438\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u0435\u0440\u044c\u0435\u0437\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u0434\u0430\u0436\u0435 \u0434\u043b\u044f \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0444\u0435\u0441\u0441\u0438\u043e\u043d\u0430\u043b\u0430. \u0418\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044e \u0447\u0438\u0441\u043b\u0430 N, \u043f\u043e \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u043c\u0435\u0440\u0435, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u043b\u0430\u0434\u0435\u0442\u044c \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u043e\u0439 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u043f\u043e\u043b\u0435\u0439 \u0438 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. <\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u0435\u0440\u043d\u0435\u043c\u0441\u044f \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a \u043c\u0435\u0442\u043e\u0434\u0443 GNFS \u0434\u043b\u044f \u0431\u043e\u043b\u0435\u0435 \u0434\u0435\u0442\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u044f\u0432\u043b\u0435\u043d\u0438\u0439.<\/p>\n<p>  <b>\u0424\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f <\/b><br \/>  \u041f\u0443\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u043d\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0fe\/bbe\/d68\/0febbed68a5a73165ac2f3cc207bc64c.svg\" alt=\"$N =45113$\" data-tex=\"inline\"><\/math>. \u0412\u044b\u0447\u0438\u0441\u043b\u0438\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/12e\/87d\/342\/12e87d342dca550b630bdceca63667f0.svg\" alt=\"$m = N^{\u2153}= 35,4 \u2245 35$\" data-tex=\"inline\"><\/math>. \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c N \u0432 m-\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/32b\/b35\/236\/32bb35236953f15fac35d698b99211d2.svg\" alt=\"$ N = m^3 + m^2 + 28m +33$\" data-tex=\"inline\"><\/math>. \u0411\u043e\u043b\u044c\u0448\u0438\u0435 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b (28 \u0438 33) \u0432\u043e\u043e\u0431\u0449\u0435 \u043d\u0435\u0436\u0435\u043b\u0430\u0442\u0435\u043b\u044c\u043d\u044b. <\/p>\n<p>  \u0412\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441 \u043d\u0435\u043b\u044c\u0437\u044f \u043b\u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b, \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u044f\u044f N? \u0418\u043c\u0435\u043d\u043d\u043e \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u044b ( \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u044f \u0432 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0436\u0435\u043b\u0430\u0442\u0435\u043b\u044c\u043d\u0430) \u044d\u0442\u043e\u0433\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 \u0432\u043b\u0438\u044f\u044e\u0442 \u043d\u0430 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0438 \u0437\u0430\u0434\u0430\u043d\u0438\u0438 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f. \u041f\u043e\u043a\u0430\u0436\u0435\u043c \u043a\u0430\u043a \u044d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c.<\/p>\n<p>  \u0412\u044b\u0447\u0442\u0435\u043c m=35 \u0438\u0437 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u0447\u043b\u0435\u043d\u0430 \u0438 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u043c 1 \u043a \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0443 \u043f\u0440\u0438 m \u0432 1-\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438. \u041f\u043e\u043b\u0443\u0447\u0438\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cdb\/6bd\/3c1\/cdb6bd3c18ffe3d53505e54a770d22b1.svg\" alt=\"$ N = m^3 + m^2 + 29m - 2$\" data-tex=\"inline\"><\/math>.<br \/>  \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u044b\u0447\u0442\u0435\u043c m=35 \u0438\u0437 \u043f\u0440\u0435\u0434\u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u0433\u043e \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044f 1 \u043a \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442\u0443 \u043f\u0440\u0438 m \u0432 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0435. \u041f\u043e\u043b\u0443\u0447\u0438\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b1c\/4de\/519\/b1c4de519932c1fcf66ea51c660f4839.svg\" alt=\"$ N = m^3 + 2m^2 - 6m - 2$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440.<\/b> \u0422\u0430\u043a\u043e\u0439 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u043b\u0443\u0447\u0448\u0435 \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u0440\u043e\u0441\u0442\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6a6\/b49\/409\/6a6b4940972c24a7c72e2a00e7a527d0.svg\" alt=\"$F_1(a, b)$\" data-tex=\"inline\"><\/math> \u0432 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f, \u0430 \u044d\u0442\u043e \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0442 \u043f\u043e\u0438\u0441\u043a \u0438 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0433\u043b\u0430\u0434\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u043f\u0440\u0438 \u0442\u043e\u0439 \u0436\u0435 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f. \u0412 \u0434\u0435\u043c\u043e\u043d\u0441\u0442\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u0432\u044b\u0431\u043e\u0440 \u043d\u0430 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0435<br \/>   <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b1c\/a6d\/681\/b1ca6d681b5d4ceaf138be9a27b61a7d.svg\" alt=\"$ N = m^3 +15m^2 - 29m + 8$\" data-tex=\"inline\"><\/math>. \u0427\u0442\u043e\u0431\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u043b\u043e\u0441\u044c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e m =31.<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a86\/dc4\/f01\/a86dc4f016366416adad11f4b95a902d.svg\" alt=\"$31^3 +15\u00b731^2 +29\u00b731 + 8 = 29791 +14415 + 899 + 8 = 45113 =N$\" data-tex=\"inline\"><\/math><\/p>\n<p>  <b>\u0424\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u044b\u0445 \u0431\u0430\u0437<\/b><br \/>  \u0424\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430 FBi \u2014 \u044d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0412i. \u0412 \u043c\u0435\u0442\u043e\u0434\u0435 GNFS \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0442\u0440\u0438 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u044b\u0445 \u0431\u0430\u0437\u044b \u0441 \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438.<\/p>\n<p>  \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435:FB1-\u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430. \u0415\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u0435\u0439 \u0433\u043b\u0430\u0434\u043a\u043e\u0441\u0442\u0438 \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u04121=103. \u0415\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6a1\/75d\/3b2\/6a175d3b28534c53e09e4103dc67843e.svg\" alt=\"$F_1$\" data-tex=\"inline\"><\/math>. \u041e\u043d\u0430 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c\u0438 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430\u043c\u0438 \u0432\u0438\u0434\u0430 (\u0441 \u2014 d\u03b8), \u043f\u043e\u0440\u043e\u0436\u0434\u0430\u044e\u0449\u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0438\u0434\u0435\u0430\u043b\u044b \u0432 \u043a\u043e\u043b\u044c\u0446\u0435 \u0446\u0435\u043b\u044b\u0445 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9c7\/554\/38e\/9c755438e4b81d4e4c62339142a769e6.svg\" alt=\"$Z_K$\" data-tex=\"inline\"><\/math>. \u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u0431\u0430\u0437\u044b \u0432 \u0442\u0430\u043a\u043e\u043c \u0432\u0438\u0434\u0435 \u2014 \u0442\u0440\u0443\u0434\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430, \u043d\u043e \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u041c. \u0411\u0440\u0438\u0433\u0433\u0441\u0430 [2] \u0443\u0434\u0430\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u043e\u0442 \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u044b\u0445 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 \u0438 \u043f\u043e\u0440\u043e\u0436\u0434\u0430\u0435\u043c\u044b\u0445 \u0438\u043c\u0438 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0438\u0434\u0435\u0430\u043b\u043e\u0432 \u043a \u043f\u0430\u0440\u0430\u043c \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (\u0440, r).<\/p>\n<p>  <b>\u0422\u0435\u043e\u0440\u0435\u043c\u0430.<\/b> \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0438\u0434\u0435\u0430\u043b\u043e\u0432 \u043a\u043e\u043b\u044c\u0446\u0430 Zk \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0432\u043e \u0432\u0437\u0430\u0438\u043c\u043d\u043e-\u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u043f\u0430\u0440 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b (p, r) \u0442\u0430\u043a\u0438\u0445, \u0447\u0442\u043e \u0440 \u2014 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2ad\/043\/742\/2ad043742e4746875cc740b5574672bb.svg\" alt=\"$0\u2264r&lt;p, \u0438 f_1(r)\u22610(mod p).$\" data-tex=\"inline\"><\/math><\/p>\n<p>  \u0422\u0430\u0431\u043b\u0438\u0446\u0430 A \u2014 \u0410\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430 FB1  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ny\/pk\/wa\/nypkwar8hrld7sqrcrc8vw_tapq.png\"><\/div>\n<p>  FB2 -\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0430\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430. \u041e\u043d\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0432\u0438\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7df\/44a\/03c\/7df44a03c5ef5ad15479e7046f9376f1.svg\" alt=\"$(a - bm) $\" data-tex=\"inline\"><\/math> \u0438\u0437 Z. \u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0435\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0430\u0432\u043d\u044b\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0443 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u044b\u0445 \u0441\u0432\u0435\u0440\u0445\u0443 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043e\u0439 \u04122 (\u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9e2\/668\/1ae\/9e26681aee425288fe00623c7fcf38f2.svg\" alt=\"$|B2|=10^6-10^7$\" data-tex=\"inline\"><\/math>). \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 FB2 ={2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, \u0433\u0440\u0430\u043d\u0438\u0446\u0435\u0439 \u0434\u043b\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 FB2 \u0441\u043b\u0443\u0436\u0438\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 B2 =30. <br \/>  \u0415\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d90\/c0a\/c32\/d90c0ac3287bf4d96e950240648a5cb2.svg\" alt=\"$F_2$\" data-tex=\"inline\"><\/math><br \/>  FB3 \u2014 \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u043c\u0438 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0430\u043c\u0438 (\u044d\u0442\u043e \u0442\u0430\u043a\u0436\u0435 \u043f\u0430\u0440\u044b \u0447\u0438\u0441\u0435\u043b (p, r))<\/p>\n<p>  \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0425 \u2014 \u0424\u0430\u043a\u0442\u043e\u0440\u043d\u0430\u044f \u0431\u0430\u0437\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0445 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u043e\u0432 FB3  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ay\/bu\/hf\/aybuhfy70sd6p1wvjtrlg8kak7g.png\"><\/div>\n<p>  \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e \u043a\u0430\u043a \u0441\u043e\u0437\u0434\u0430\u043d\u044b \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u0438 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u044b\u0435 \u0431\u0430\u0437\u044b \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0442 \u0441\u0430\u043c\u043e \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0435 (2 \u044d\u0442\u0430\u043f\u0430: \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u044e\u0449\u0435\u0435).<\/p>\n<p>  <b>\u041e\u0446\u0435\u043d\u0438\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0433\u043b\u0430\u0434\u043a\u0438\u0445 \u043f\u0430\u0440<\/b><br \/>  \u0421\u0443\u043c\u043c\u0430\u0440\u043d\u044b\u0439 \u043e\u0431\u044a\u0435\u043c \u0442\u0440\u0435\u0445 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u044b\u0445 \u0431\u0430\u0437 s = 23+10 + 5 = 38, \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u0434\u043e\u043b\u0436\u0435\u043d \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 38 + 2 =40 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043e\u0434\u0438\u043d \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u043a\u0430 \u0447\u0438\u0441\u043b\u0430 (\u0430 \u2014 bm) \u0438 \u0435\u0449\u0435 \u043e\u0434\u0438\u043d \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0421\u041b\u0410\u0423 \u0438\u043c\u0435\u043b\u0430 \u043d\u0435\u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p>  \u041e\u0431\u043b\u0430\u0441\u0442\u044c \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u0432 \u0440\u0435\u0448\u0435\u0442\u0435 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u0432\u0438\u0434\u0430<br \/>  SR ={<math>$inline$(a, b)| 1\u2264b\u2264L_2; -L_1\u2264a\u2264L_1$inline$<\/math>}. \u0412 \u044d\u0442\u043e\u0439 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0448\u0435\u0442\u043e\u0447\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u0435 \u0432\u0434\u043e\u043b\u044c \u043f\u0440\u044f\u043c\u044b\u0445 \u0432\u0438\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3ac\/d63\/981\/3acd63981d7e2ba1afe81dea675c599d.svg\" alt=\"$L_{pr}$\" data-tex=\"inline\"><\/math> ={<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/89c\/8dd\/0a9\/89c8dd0a944d226eebc5cb2cb1107d72.svg\" alt=\"$(a, b)\u0454SR|a - br\u22610(mod p)$\" data-tex=\"inline\"><\/math>}. <br \/>  \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u043d\u0438\u0436\u0435 (\u0442\u0430\u0431\u043b. \u0413).<\/p>\n<p>  \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0413 \u2014 \u0413\u043b\u0430\u0434\u043a\u0438\u0435 \u043f\u0430\u0440\u044b \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d90\/c0a\/c32\/d90c0ac3287bf4d96e950240648a5cb2.svg\" alt=\"$F_2$\" data-tex=\"inline\"><\/math>, \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0435 \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/c-\/ks\/yn\/c-ksynakzaovlhx6iviskxqpoay.png\"><\/div>\n<p>  \u0420\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044f, \u043a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 QS, \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c \u0433\u043b\u0430\u0434\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0421\u041b\u0410\u0423 \u0438 \u043e\u0442\u044b\u0441\u043a\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f (\u0442\u0430\u0431\u043b. \u0421), \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0435 \u0432 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044f\u0445 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0435 \u0441\u0440\u0430\u0432\u043d\u0438\u043c\u044b\u0445 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432. \u0412\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u044e\u0449\u0435\u0433\u043e \u043f\u0440\u043e\u0441\u0435\u0438\u0432\u0430\u043d\u0438\u044f \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0433\u043b\u0430\u0434\u043a\u0438\u0445 \u043f\u0430\u0440 \u041c (\u0422\u0430\u0431\u043b.\u0421).<\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440.<\/b> \u041e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0413. \u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0432\u0437\u044f\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0442\u043e\u043b\u0431\u0446\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/84b\/48b\/aab\/84b48baabdfaed1f93367073f7bd5669.svg\" alt=\"$F_2(8, 3) =8 - 3m=8-3\u00b731=-85 =- 2^0\u00b73^0\u00b75^1\u00b77^0\u00b711^0\u00b713^0\u00b717^1\u00b719^0\u00b723^0\u00b729^0,$\" data-tex=\"inline\"><\/math> \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0435\u0439 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0438\u0437 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442 \u0432\u0438\u0434 <br \/>  \u03d1(8, 3) =(1,0,0,1,0,0,0,1,0,0,0). \u041f\u0435\u0440\u0432\u0430\u044f \u0435\u0434\u0438\u043d\u0438\u0446\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0437\u043d\u0430\u043a\u0443 \u043c\u0438\u043d\u0443\u0441 \u0443 \u0447\u0438\u0441\u043b\u0430 85.<br \/>  \u0414\u043b\u044f \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0444\u0430\u043a\u0442\u043e\u0440\u043d\u043e\u0439 \u0431\u0430\u0437\u044b \u0438\u043c\u0435\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e47\/544\/057\/e475440573ed27fb7d7e0d1e0a52c97b.svg\" alt=\"$Nr(a, b) = F_1(8, 3) =5696 = 2^6\u00b789^1, $\" data-tex=\"inline\"><\/math> \u0432\u0435\u043a\u0442\u043e\u0440 \u0438\u043c\u0435\u0435\u0442 \u0434\u043b\u0438\u043d\u0443 24 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430.<\/p>\n<p>  \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0421 \u2014 \u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u041c, \u0434\u0430\u044e\u0449\u0438\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0421\u041b\u0410\u0423  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/pj\/en\/mc\/pjenmclbh_fxuyl7v7coocpwthy.png\"><\/div>\n<h3>\u0421\u0438\u0441\u0442\u0435\u043c\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0438 \u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/h3>\n<p>  \u0421\u0430\u043c\u0430 \u0421\u041b\u0410\u0423 \u0438 \u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0438\u0447\u0435\u043c \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u044b\u043c \u043d\u0435 \u043e\u0442\u043b\u0438\u0447\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 \u043c\u0435\u0442\u043e\u0434\u043e\u043c QS. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u0430\u044f \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0413\u0430\u0443\u0441\u0441\u0430, \u043b\u0438\u0431\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u041b\u0430\u043d\u0446\u043e\u0448\u0430. \u0411\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u043b\u044f N = 45113 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0421\u041b\u0410\u0423 \u0443\u0436\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u043e (\u044d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e <b>S<\/b> \u043f\u0430\u0440 \u0447\u0438\u0441\u0435\u043b (<i>\u0430,b<\/i>) \u0438 \u043e\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043e \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u0435:<\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/bo\/s6\/ks\/bos6ksudntvmnyrqbvug9osowsw.png\"><\/div>\n<p>  \u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0447\u0435\u0440\u0435\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/af8\/b89\/fcd\/af8b89fcde55cb7473d55d8e39551378.svg\" alt=\"$\u03b3(x)$\" data-tex=\"inline\"><\/math> \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d \u0440\u0430\u0432\u043d\u044b\u0439, \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044e \u0432\u0441\u0435\u0445 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u043e\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/87a\/1f9\/813\/87a1f98133bfee9de511c13fc460b1ef.svg\" alt=\"$(a - bx)$\" data-tex=\"inline\"><\/math>, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u0430\u044f \u043f\u0430\u0440\u0430 (<i>a, b<\/i>) \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u043e\u043c\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0443 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b73\/78d\/ef8\/b7378def81fc74f8aae6bdead08d4a17.svg\" alt=\"$S: \u03b3(x) = \u041f_{x\u0454S}(a - bx) =$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b68\/25b\/835\/b6825b835b85af7940308d1a696857ab.svg\" alt=\"$=2051543129764485x^2 +15388377355799440x + 65692886531904247$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432\u0430\u0436\u043d\u0430\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0430.<\/p>\n<p>  <b>\u0422\u0435\u043e\u0440\u0435\u043c\u0430.<\/b> \u041f\u0443\u0441\u0442\u044c \u041a =Q[\u03b8] \u2014 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0435 \u043f\u043e\u043b\u0435, \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u043e\u0435 \u043f\u0440\u0438\u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0435\u043c \u043a Q \u043a\u043e\u0440\u043d\u044f \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u043e\u0433\u043e \u0432 Q \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 f(x). \u0422\u043e\u0433\u0434\u0430 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 \u03b1(x), \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0430\u0449\u0435\u0433\u043e \u043a\u043e\u043b\u044c\u0446\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9c7\/554\/38e\/9c755438e4b81d4e4c62339142a769e6.svg\" alt=\"$Z_K$\" data-tex=\"inline\"><\/math>, \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/efe\/268\/3b3\/efe2683b3caa8bdf54747532eb3ad0fc.svg\" alt=\"$h(x)=\u03b1(x)\u00b7f '(x)$\" data-tex=\"inline\"><\/math> \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u043a\u043e\u043b\u044c\u0446\u0443 Z[\u03b1], \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/02b\/330\/880\/02b33088043b6b4107f35ed002aed75b.svg\" alt=\"$f'(x)=3x^2 +30x +29$\" data-tex=\"inline\"><\/math> \u2014 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u043d\u0430\u044f \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/674\/025\/992\/6740259923c1dc5337910b373aea4a6d.svg\" alt=\"$f(x)=x^3 +15x^2 +29x + 8$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  \u0414\u043b\u044f \u0443\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u0435\u043f\u043e\u043b\u043d\u043e\u0442\u044b \u043a\u043e\u043b\u044c\u0446\u0430 Z[\u03b8] \u0432 NFS \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0434\u043e\u043c\u043d\u043e\u0436\u0438\u0442\u044c \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11b\/16c\/585\/11b16c585cbad0bbb9cda63771de4f03.svg\" alt=\"$ \u03b3(x) = \u041f_{x\u0454S}(a - bx) $\" data-tex=\"inline\"><\/math> \u043d\u0430 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u043d\u043e\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/77e\/66a\/2b5\/77e66a2b530bcfe28b7cd81d16bb9984.svg\" alt=\"$f_1(x):$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/256\/615\/8a6\/2566158a6d68164badc7c5939b916ac6.svg\" alt=\"$g(x)=(f '_1(x))^2\u00b7\u03b3(x)$\" data-tex=\"inline\"><\/math><\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440.<\/b> \u0412\u044b\u0447\u0438\u0441\u043b\u0438\u043c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0421\u041b\u0410\u0423 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430 g(x) \u043d\u0430\u0448\u0435\u0433\u043e \u0431\u0430\u0437\u043e\u0432\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 c <br \/>  N =45113 (\u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0434\u0443\u043a\u0446\u0438\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u043d\u0435\u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c\u043e\u0433\u043e \u043c\u043d\u043e\u0433\u043e\u0447\u043b\u0435\u043d\u0430)<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/83f\/f64\/428\/83ff6442821123cb91a351b965389dad.svg\" alt=\"$g(x) \u2261(f'_1(x))^2\u00b7\u03b3(x) = (3x^2 +30x +29)^2\u00b7\u041f_{x\u0454S}(a - bx) =$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4e5\/475\/a5f\/4e5475a5fd09ae047f7dbca20ef36213.svg\" alt=\"$=2245598394971045412x^2+54100105785512562427x+22939402657683071224 (mod f_1(x)),$\" data-tex=\"inline\"><\/math> \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ba8\/8a7\/2f8\/ba88a72f8828409f9bd9a14f2afe7b0e.svg\" alt=\"$f_1(x) = x^3 + 15x^2 +29x +8$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0430\u0434\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043f\u043e\u043b\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u0440\u043d\u044f \u0438\u0437 g(m)(modN), \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f g(m) \u043f\u043e \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u043c \u043c\u043e\u0434\u0443\u043b\u044f\u043c 9851,9907 \u0438 9929 \u0438\u043b\u0438, \u0434\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u043d\u0430\u0434\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439<br \/>  \u0445 \u22615694 (mod 9851);<br \/>  \u0445 \u22614152 (mod 9907);<br \/>  \u0445 \u22613077 (mod 9929).<\/p>\n<p>  \u0414\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043a\u0438\u0442\u0430\u0439\u0441\u043a\u0430\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0430 \u043e\u0431 \u043e\u0441\u0442\u0430\u0442\u043a\u0430\u0445 (\u041a\u0422\u041e). \u041d\u0430\u0445\u043e\u0434\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/32e\/639\/374\/32e639374686c3efcfc3c9cc9d931e40.svg\" alt=\"$x \u2261 g(m)(mod N)\u2261694983807559(mod 45113) =43992$\" data-tex=\"inline\"><\/math>, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0435 \u0432 \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u044e\u0449\u0435\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/80c\/cb9\/377\/80ccb9377eb7711a7c21aaff491ad8d8.svg\" alt=\"$x^2\u2261y^2(mod N)$\" data-tex=\"inline\"><\/math><\/p>\n<h3>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0415\u0432\u043a\u043b\u0438\u0434\u0430<\/h3>\n<p>  \u041c\u044b \u043f\u043e\u0434\u043e\u0448\u043b\u0438 \u043a \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u044e \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 N = 45113.<\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440. \u0417\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u0435.<\/b> \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 (\u0432\u0441\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u043c, \u0447\u0442\u043e m = 31): <br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7c8\/abc\/1c5\/7c8abc1c5798297bd2188a993ee82755.svg\" alt=\"$y^2 =(f_1'(m))^2\u00b7\u041f_{x\u220aS}(a - bm)=(3\u00b731+30\u00b731 +29)^2\u00b7(-1+31)(3+31)\u00b7$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/610\/516\/dbc\/610516dbc3015fc35fef35fd27d44d47.svg\" alt=\"$(13+31)(104+31)(3+2\u00b731)(-8+3\u00b731)(48+5\u00b731)(54 +5\u00b731)(-43 +6\u00b731)$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/be0\/e26\/77c\/be0e2677c1f81e9a34e9b4b4794dceaf.svg\" alt=\"$(-8+6\u00b731)\u00b7(-8+7\u00b731)(11+7\u00b731)(856+11\u00b731)=3842^2\u00b731746503388600^2 (mod N)$\" data-tex=\"inline\"><\/math><br \/>  \u041e\u0442\u043a\u0443\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/27a\/9fa\/bbe\/27a9fabbe7fae4140d7e144d03a8f298.svg\" alt=\"$y = 3842\u00b731746503388600(mod 45113) = 15160.$\" data-tex=\"inline\"><\/math> <\/p>\n<p>  \u041f\u0430\u0440\u0430 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fdb\/bba\/82f\/fdbbba82f748a2f31f81ee3ed5008536.svg\" alt=\"$(x, y) = (43992,15160)$\" data-tex=\"inline\"><\/math> \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/80c\/cb9\/377\/80ccb9377eb7711a7c21aaff491ad8d8.svg\" alt=\"$x^2\u2261y^2(mod N)$\" data-tex=\"inline\"><\/math>, \u043e\u0442\u043a\u0443\u0434\u0430<br \/>   <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d59\/dbb\/17b\/d59dbb17b9e7fb95b7c63159fb275960.svg\" alt=\"$x^2-y^2=(x-\u0443)(x + y) = (43992+15160)(43992-15160) = 59152\u00b728832$\" data-tex=\"inline\"><\/math>. \u0414\u0430\u043b\u044c\u0448\u0435 \u0443\u0436\u0435 \u0441\u043e\u0432\u0441\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e \u2014 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0415\u0432\u043a\u043b\u0438\u0434\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043e\u0431\u0449\u0435\u0433\u043e \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044f \u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d1f\/d74\/124\/d1fd74124298f39506e7b1c935849c5d.svg\" alt=\"$N = 45113.$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/131\/418\/440\/131418440f83e51f6a12236f5f3e6b7f.svg\" alt=\"$\u041d\u041e\u0414(N, x + y) = \u041d\u041e\u0414(45113, 59152) = 229,$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/cc5\/2c6\/3e0\/cc52c63e03cd70b6a704e80ec848e6f2.svg\" alt=\"$\u041d\u041e\u0414(N, x - y) = \u041d\u041e\u0414(45113, 59152) = 197.$\" data-tex=\"inline\"><\/math><\/p>\n<p>  \u041f\u0440\u043e\u0432\u0435\u0440\u043a\u0430: 197\u00b7229 = 45113 = N.<\/p>\n<h3>\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h3>\n<p>  \u0418\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u043f\u043e \u043e\u0431\u044a\u0435\u043c\u0443 \u0440\u0430\u0431\u043e\u0442\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0440\u0435\u0448\u0435\u0442\u0430 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u044b\u0445 \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0445 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u2014 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043d\u0435\u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430. \u041d\u043e \u0430\u0432\u0442\u043e\u0440 \u043a\u0430\u043a \u043c\u043e\u0433 \u0435\u0435 \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u043b. \u041a\u043e\u043d\u0435\u0447\u043d\u043e, \u043c\u043e\u0436\u043d\u043e \u043a\u0440\u0438\u0442\u0438\u043a\u043e\u0432\u0430\u0442\u044c \u0438 \u0440\u0430\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0441\u043e\u0432\u0435\u0442\u044b \u2014 \u044d\u0442\u043e \u043f\u0440\u0430\u0432\u043e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f.<br \/>  \u041f\u0440\u043e\u0441\u0442\u043e, \u0430\u0432\u0442\u043e\u0440 \u0441\u043e\u0436\u0430\u043b\u0435\u0435\u0442, \u0447\u0442\u043e \u0432 \u0441\u0432\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0435\u043c\u0443 \u0441\u0430\u043c\u043e\u043c\u0443 \u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f \u0441 \u0447\u0435\u043c-\u0442\u043e \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c. \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044d\u0442\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u043b\u043e \u0431\u044b \u0432\u043e\u0441\u043f\u0440\u0438\u044f\u0442\u0438\u0435 \u0438 \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0438\u0434\u0435\u0439 \u043c\u0435\u0442\u043e\u0434\u0430 \u0440\u0435\u0448\u0435\u0442\u0430.<\/p>\n<p>  \u0425\u043e\u0447\u0443 \u043e\u0442\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u0435\u0440\u0432\u043e\u0435 \u0432\u043f\u0435\u0447\u0430\u0442\u043b\u0435\u043d\u0438\u0435 (\u0430 \u043e\u043d\u043e \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u0438\u043b\u043e\u0441\u044c) \u2014 \u0437\u0430\u043d\u044f\u0442\u043d\u044b\u0439 \u043e\u0433\u043e\u0440\u043e\u0434 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043d\u0430\u0433\u043e\u0440\u043e\u0434\u0438\u0442\u044c. \u041e\u0442\u043f\u0440\u0430\u0432\u043d\u0430\u044f \u0442\u043e\u0447\u043a\u0430 \u0430\u0432\u0442\u043e\u0440\u0430\u043c\u0438 \u043d\u0435 \u043a\u0440\u0438\u0442\u0438\u043a\u043e\u0432\u0430\u043b\u0430\u0441\u044c, \u043d\u0435 \u043e\u0441\u043c\u044b\u0441\u043b\u0438\u0432\u0430\u043b\u0430\u0441\u044c, \u0434\u0440\u0443\u0433\u0438\u0435 \u043f\u0443\u0442\u0438 \u043d\u0435 \u0440\u0430\u0437\u044b\u0441\u043a\u0438\u0432\u0430\u043b\u0438\u0441\u044c. \u041f\u0440\u0438\u0432\u043b\u0435\u0447\u0435\u043d\u0438\u0435 \u0442\u0435\u043e\u0440\u0438\u0438 \u044d\u043b\u043b\u0438\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043a\u0440\u0438\u0432\u044b\u0445 \u2014 \u0431\u043e\u043a\u043e\u0432\u043e\u0435 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435. \u0414\u0430\u043b\u044c\u0448\u0435, \u0447\u0442\u043e \u043e\u0436\u0438\u0434\u0430\u0442\u044c? \u0422\u043e\u043f\u043e\u0441\u044b, \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0438? \u0414\u0435\u043b\u0438\u0442\u0435\u043b\u0438 \u0421\u041d\u041d\u0427 \u0440\u0430\u0437\u044b\u0441\u043a\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0441\u043e\u0432\u0441\u0435\u043c \u043d\u0435 \u0442\u0430\u043c, <a href=\"https:\/\/habr.com\/ru\/post\/507400\/\">\u0433\u0434\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b<\/a> \u0438\u0445 \u041d\u0420\u0427. <a href=\"https:\/\/habr.com\/ru\/post\/507924\/\">\u041c\u043e\u0434\u0435\u043b\u0438 \u0447\u0438\u0441\u043b\u0430<\/a> \u0438 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u044f\u0434\u0430 \u043d\u0430\u043f\u0440\u043e\u0447\u044c \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u044e\u0442\u0441\u044f. \u041d\u0435 \u0443\u0434\u0435\u0440\u0436\u0430\u043b\u0441\u044f. \u041e\u043f\u044f\u0442\u044c \u0441\u043a\u0430\u0442\u044b\u0432\u0430\u044e\u0441\u044c \u0432 \u043a\u0440\u0438\u0442\u0438\u043a\u0443.<\/p>\n<p>  \u0414\u0430, \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u043b\u043e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0430\u043c \u0445\u0443\u0434\u043e-\u0431\u0435\u0434\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043a\u043e\u0435-\u043a\u0430\u043a\u0438\u0435 \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u043d\u043e \u043e\u043d\u043e \u0436\u0435 \u0438 \u0437\u0430\u043a\u0440\u044b\u043b\u043e \u0438\u043c \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442, \u0448\u0430\u0431\u043b\u043e\u043d\u044b, \u043e\u0431\u0440\u0430\u0437\u0446\u044b \u043d\u0435 \u0434\u0430\u044e\u0442 \u043e\u0442\u043e\u0440\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0442 \u0443\u0436\u0435 \u043f\u0440\u043e\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u0438\u0441\u0442\u0438\u043d.<br \/>  \u0412 \u043e\u0431\u0449\u0435\u043c, \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0432\u0441\u0435\u043c, \u043a\u0442\u043e \u043f\u0440\u043e\u0447\u0435\u043b \u0438 \u0434\u0432\u043e\u0439\u043d\u043e\u0435 \u0442\u0435\u043c, \u043a\u0442\u043e \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0442\u043d\u0435\u0441\u0441\u044f \u043a \u044d\u0442\u0438\u043c \u0441\u043a\u0440\u043e\u043c\u043d\u044b\u043c \u0442\u0435\u043a\u0441\u0442\u0430\u043c. <\/p>\n<h3>\u0421\u043f\u0438\u0441\u043e\u043a \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u043e\u0439 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b<\/h3>\n<p>  1. \u0411\u0440\u0430\u0441\u0441\u0430\u0440 \u0416. \u0421\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u043a\u0440\u0438\u043f\u0442\u043e\u043b\u043e\u0433\u0438\u044f. \u041c.: \u041f\u041e\u041b\u0418\u041c\u0415\u0414, 1999.<br \/>  2. Briggs M. An Introduction to theGeneral Number Field Sieve, M.Briggs Master&#8217;s Thesis, Virginia Polytechnic Institute and State University, Blacksburg,Virginia, 1998, p. 1-84.<br \/>  3. \u0412\u0430\u0441\u0438\u043b\u0435\u043d\u043a\u043e \u041e. \u041d. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u043a\u043e-\u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438. \u041c.: \u041c\u0426\u041d\u041c\u041e, 2003<br \/>  4. \u0414.\u042d. \u041a\u043d\u0443\u0442. \u0418\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0422.2. \u0422\u0440\u0435\u0442\u044c\u0435 \u0438\u0437\u0434\u0430\u043d\u0438\u0435. \u041c\u043e\u0441\u043a\u0432\u0430-\u0421\u0430\u043d\u043a\u0442-\u041f\u0435\u0442\u0435\u0440\u0431\u0443\u0440\u0433-\u041a\u0438\u0435\u0432: \u0418\u0437\u0434-\u0432\u043e \u041c\u0438\u0440, 2000.<br \/>  5. \u0415.\u0411. \u041c\u0430\u0445\u043e\u0432\u0435\u043d\u043a\u043e. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u043a\u043e-\u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438. \u041c.: \u0418\u0437\u0434-\u0432\u043e \u0413\u0435\u043b\u0438\u043e\u0441 \u0410\u0420\u0412, 2006<br \/>  6. \u041d\u0435\u0441\u0442\u0435\u0440\u0435\u043d\u043a\u043e \u0410.\u042e. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u043a\u043e-\u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438. \u041c\u043e\u0441\u043a\u0432\u0430 2012<br \/>  7 \u041d\u043e\u0434\u0435\u043d \u041f., \u041a\u0438\u0442\u0442\u0435 \u041a. \u0410\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u043a\u0430. \u041c.: \u041c\u0438\u0440, 1999.<br \/>  8. \u0427\u0435\u0440\u0435\u043c\u0443\u0448\u043a\u0438\u043d \u0410. \u0412. \u041b\u0435\u043a\u0446\u0438\u0438 \u043f\u043e \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438. \u041c.: \u041c\u0426\u041d\u041c\u041e, 2002.<br \/>  9. Rivest R. L., Shamir A., Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems \/\/ Communications of the ACM. 1978. V. 21, P. 120\u2013126.<br \/>  10. The RSA Challenge Numbers \/\/ RSA Laboratories. <a href=\"http:\/\/www.rsasecurity.com\/rsalabs\/node.asp?id=2093\" rel=\"nofollow\">www.rsasecurity.com\/rsalabs\/node.asp?id=2093<\/a><br \/>  11. \u0421\u0442\u0440\u0435\u043d\u0433 \u0413. \u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0430\u043b\u0433\u0435\u0431\u0440\u0430 \u0438 \u0435\u0451 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f. \u041c.: \u041c\u0438\u0440, 1980.<br \/>  12. \u0421\u043c\u0430\u0440\u0442 \u041d. \u041a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u044f. \u041c.: \u0422\u0435\u0445\u043d\u043e\u0441\u0444\u0435\u0440\u0430, 2005.<br \/>  13. Shanks D. Five number-theoretic algorithms \/\/ Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), Utilitas Math. 1973. P. 51\u201370. Congressus Numerantium, No. VII.<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/522194\/\"> https:\/\/habr.com\/ru\/post\/522194\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/522194\/\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/up\/k9\/cv\/upk9cvor1otijonyhk4-tab7ohm.jpeg\"><\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u043e\u0447\u0438\u0435 \u0441\u0442\u0430\u0442\u044c\u0438 \u0446\u0438\u043a\u043b\u0430<\/b>                         <\/p>\n<div class=\"spoiler_text\"><a href=\"https:\/\/habr.com\/ru\/post\/521876\/\">\u0424\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u0442\u0430. \u0427\u0430\u0441\u0442\u044c I<\/a><br \/>  \u0424\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0447\u0438\u0441\u0435\u043b \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u0442\u0430. \u0427\u0430\u0441\u0442\u044c II  <\/div>\n<\/p><\/div>\n<p>  \u0417\u0430\u0434\u0430\u0435\u0442\u0441\u044f N \u2014 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043d\u043e\u0435 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e (\u0421\u041d\u041d\u0427), \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c. \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0442\u0435\u043e\u0440\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430 \u0440\u0435\u0448\u0435\u0442\u0430 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u043b\u044f (NFS) \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0442\u0435\u043e\u0440\u0438\u0438 \u0434\u0435\u043b\u0438\u043c\u043e\u0441\u0442\u0438 \u0432 \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0447\u0438\u0441\u043b\u043e\u0432\u044b\u0445 \u043f\u043e\u043b\u044f\u0445. \u041f\u0435\u0440\u0435\u0434 \u043b\u044e\u0431\u044b\u043c \u0430\u0432\u0442\u043e\u0440\u043e\u043c, \u043a\u0430\u043a \u0438 \u043f\u0435\u0440\u0435\u0434\u043e \u043c\u043d\u043e\u0439, \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u044c \u0441\u0436\u0430\u0442\u043e\u0433\u043e \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0432\u0435\u0441\u044c\u043c\u0430 \u043e\u0431\u0448\u0438\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430, \u043a\u0430\u0441\u0430\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u043c\u0435\u0442\u043e\u0434\u043e\u0432 SNFS \u0438 GNFS. \u0422\u0430\u043a \u043a\u0430\u043a 2-\u0439 \u0432\u043e\u0437\u043d\u0438\u043a \u0438\u0437 1-\u0433\u043e \u044f \u043d\u0435 \u043f\u0440\u0438\u0432\u043e\u0436\u0443 \u0438\u0445 \u043e\u0442\u043b\u0438\u0447\u0438\u0439, \u0445\u043e\u0442\u044f \u043e\u0431 \u044d\u0442\u043e\u043c \u043c\u043d\u043e\u0433\u043e \u0441\u043a\u0430\u0437\u0430\u043d\u043e.<\/p>\n<p>  \u041e \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u0446\u0435\u043b\u044b\u0435 \u043a\u043d\u0438\u0433\u0438. \u041d\u043e, \u043f\u043e\u043c\u043d\u044f \u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0437\u0430\u0442\u0440\u0443\u0434\u043d\u0435\u043d\u0438\u044f\u0445 \u0432 \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u0438 \u043f\u0440\u0435\u043e\u0434\u043e\u043b\u0435\u043d\u0438\u0438 \u0438\u0445, \u0441\u0447\u0438\u0442\u0430\u044e, \u0447\u0442\u043e \u0434\u0430\u0436\u0435 \u00ab\u043a\u0443\u0446\u0435\u0435\u00bb \u0443\u0440\u0435\u0437\u0430\u043d\u043d\u043e\u0435 \u0438\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u043f\u043e\u0441\u043e\u0431\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u043b\u0435\u043d\u0438\u044e \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0441 \u043c\u0435\u0442\u043e\u0434\u0430\u043c\u0438 \u0438 \u0438\u0434\u0435\u044f\u043c\u0438, \u043b\u0435\u0436\u0430\u0449\u0438\u043c\u0438 \u0432 \u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0435. \u041d\u0430\u0434\u0435\u044e\u0441\u044c, \u0447\u0442\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u044d\u0442\u0438\u0445 \u0438\u0434\u0435\u0439 \u0438\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u0438 (\u0447\u0442\u043e \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0430 \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442 \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e), \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u0431\u043e\u043b\u0435\u0435 \u0442\u0440\u0435\u0437\u0432\u043e \u043f\u043e\u0434\u043e\u0439\u0442\u0438 \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0439 \u0432 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0435 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438. <\/p>\n<p>  \u041c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0438 \u043f\u0440\u0438\u043d\u0443\u0434\u0438\u043b\u0438 \u043c\u0435\u043d\u044f \u0434\u043e\u043d\u043e\u0441\u0438\u0442\u044c \u0434\u043e \u043d\u0438\u0445 \u0447\u0443\u0436\u0438\u0435 \u0438\u0434\u0435\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u043d\u0435 \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u044e, \u0442\u0430\u043a \u043a\u0430\u043a \u0441\u0432\u043e\u0438 \u0441\u0447\u0438\u0442\u0430\u044e \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u0438 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u0432\u043d\u044b\u043c\u0438, \u0431\u043e\u043b\u0435\u0435 \u0437\u0434\u0440\u0430\u0432\u044b\u043c\u0438. \u041e\u043d\u0438 \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e\u0433\u043e \u0432\u0438\u0434\u0430, \u043d\u043e \u0432\u0440\u0435\u043c\u044f \u0435\u0449\u0435 \u0435\u0441\u0442\u044c. \u0425\u043e\u0447\u0443 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0443 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u043a \u0441\u0432\u043e\u0438\u043c \u0438\u0434\u0435\u044f\u043c \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u043a\u0443, \u0430 \u043d\u0435 \u043c\u0438\u043d\u0443\u0441\u044b \u0432 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445, \u043d\u0435 \u043f\u043e\u0434\u043a\u0440\u0435\u043f\u043b\u044f\u0435\u043c\u044b\u0435 \u0434\u043e\u0432\u043e\u0434\u0430\u043c\u0438. \u041b\u0438\u0447\u043d\u0443\u044e \u043d\u0435\u043f\u0440\u0438\u044f\u0437\u043d\u044c \u0438\u043b\u0438 \u00ab\u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u043e\u043d\u044f\u043b\u00bb \u0434\u043e\u0432\u043e\u0434\u043e\u043c \u0434\u043b\u044f \u043c\u0438\u043d\u0443\u0441\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043d\u0435 \u043c\u043e\u0433\u0443.<\/p>\n<p>  \u041d\u0435\u043e\u043f\u0440\u0430\u0432\u0434\u0430\u043d\u043d\u043e\u0435 \u0443\u0441\u043b\u043e\u0436\u043d\u0435\u043d\u0438\u0435 (\u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0421\u041b\u0410\u0423 \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b0f\/626\/d58\/b0f626d58290961fcb56170b469cc50d.svg\" alt=\"$N=2^{512} +1$\" data-tex=\"inline\"><\/math> \u0438\u043c\u0435\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 6000000\u00d76000000) \u0437\u0430\u0434\u0430\u0447\u0438 \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b (\u0417\u0424\u0411\u0427) \u043f\u043e\u0434\u0432\u0438\u0433\u043b\u043e \u043c\u0435\u043d\u044f \u0441\u0435\u0440\u044c\u0435\u0437\u043d\u043e \u0437\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439. \u0423\u0436\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c <a href=\"https:\/\/habr.com\/ru\/post\/229601\/\">\u0432\u0441\u043a\u0440\u044b\u0442\u044c \u0437\u0430\u043a\u043e\u043d \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0435\u0439 \u0421\u041d\u041d\u0427 \u0432 \u041d\u0420\u0427<\/a>, \u0442.\u0435. \u043f\u043e\u043d\u044f\u0442\u044c \u0433\u0434\u0435 \u0438 \u043a\u0430\u043a \u043f\u0440\u044f\u0447\u0443\u0442\u0441\u044f \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u0438 \u0432 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e\u043c \u0440\u044f\u0434\u0435 \u0447\u0438\u0441\u0435\u043b, \u0447\u0442\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u0436\u0435 \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442 \u0438\u0445 \u043f\u043e\u0438\u0441\u043a \u0438 \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0435\u043d\u0438\u0435.  <\/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-311410","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/311410","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=311410"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/311410\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=311410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=311410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=311410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}