Теория чисел: НОД, решето, быстрое возведение в степень — авторское изложение

ru · official · sha256:ba343659c24f8d149fe852003099d361c24cf835ff8d17428b322f5cc6033370RU

§1. Делимость, наибольший общий делитель и сравнения Целое d делит целое a, когда существует целое k, при котором a = k·d. Наибольший общий делитель двух целых, не равных нулю одновременно, есть наибольшее целое, делящее оба; обозначается НОД(a, b). По соглашению НОД(a, 0) = |a|, и это не частный случай, а часть определения: у нуля делителем является всякое целое. Ключевое свойство, на котором стоит алгоритм Евклида: при b, отличном от нуля, НОД(a, b) = НОД(b, a mod b), где a mod b есть остаток деления с остатком. Свойство доказывается так: всякий общий делитель пары (a, b) делит и a − q·b, то есть остаток; обратно, всякий общий делитель пары (b, r) делит b и r, а значит и a = q·b + r. Множества общих делителей у двух пар совпадают, следовательно совпадают и наибольшие. Соотношение Безу: для любых целых a и b, не равных нулю одновременно, существуют целые x и y, при которых a·x + b·y = НОД(a, b). Расширенный алгоритм Евклида не только утверждает существование такой пары, но и предъявляет её. Целое p, большее единицы, называется простым, когда его положительными делителями являются только единица и оно само. Составное число имеет делитель, не превосходящий квадратного корня из него: если n = u·v и оба множителя больше корня, их произведение больше n. Сравнение по модулю m: целые a и b сравнимы, когда m делит их разность. Умножение и сложение согласованы со сравнением, поэтому остаток произведения равен остатку произведения остатков — это и позволяет считать степень по модулю, не вычисляя саму степень. Взаимно простые числа — те, наибольший общий делитель которых равен единице.

Referencing norms: AnswersHere, f-0283a50a2102c4cea03fc24c, f-093e78533d934d404b426a22, f-0b5ed75b700c085dd5d43332, f-1f239c62423da5833e3c1db4, f-262146974ddba1bfea829c80, f-28617e4daed8caa7ec431843, f-2c480c3b07781b2d77f3b463, f-2cad7fb7c581b406061d94c3, f-3046d87281131d54ec22660c, f-331d103ec360ee5d7ea6edad, f-4231d1631a2636023c3e62f0, f-4c79c667b35c57d26d30d692, f-51a8a21bc6dc712cc1a5e199, f-51ae6b32111bd66a9144cf5a, f-583c473f45f293d0510e99f7, f-5d7a1307c97c6cc4cd3bf50e, f-6668d8aa2a4edfd2e6a92b53, f-668ad0888e6a83ca73f28ac3, f-68169c95df92f211d775efd0, f-69f86138460b704821842bd8, f-6e17e9a94b2afd0b1894fad7, f-72116f80e5ce3ed1e38283b7, f-734e0d161759559c80e3bc74, f-85d1c8fe08acd7e6bd62d414, f-8a82878673a29be61b4c3103, f-905e6273e752efb13a66ec08, f-911fc8256e5506699576659a, f-92a044f384aa33450c428062, f-93aacf5c07b62c3806649c43, f-947b8f740f9e3b55fa37b2c7, f-9b51d1a56fa15b8717fe8d97, f-9b68a01b08262649bdd36dc7, f-9f0d3e72a2920b7c1fedcfae, f-a110375b274f06c1e0ab2004, f-a8dcddeba9b815eb9284fc9c, f-b3e2b36b799d8b4580abcee5, f-ba88533b5150f578fa9f1096, f-bc8e8e059a2808ac74f7678a, f-c7cfa35520f04a6dd58247ae, f-cd788318e57e94df7aea3f18, f-cedde302b2cfed4cc5e00520, f-d4ca6ea9de75a4dc71b8a64d, f-d8fa480a0c1eaf0ce371b6d0, f-e2cb2f357229a345f7b7de17, f-e3574cb9209f0478eb4b2557, f-e52c557942b060aea732e336, f-e731bcd8447ec22803c5a7b8, f-edfa5bcb99001637f814da21, f-eea5e97945402208a2b6c4f4, f-efb14f59df3dd100eb0f7401, f-f2f2bbee9e7fb0b640214bd2, f-f3a5fe571f830776a730bed0, f-f68516af6bf7ca0818f16482, f-f920580da77992b7a279996a

ru · official · sha256:50a66817e5c2ee85c41909fd63e51938a1b8c1d5ff77a747b16cfba0fde75a6dRU

§2. Алгоритм Евклида Задача: по двум целым, не равным нулю одновременно, получить их наибольший общий делитель. Вариант — итеративный, с остатками: пара (a, b) заменяется парой (b, a mod b), пока второй элемент не станет нулём. Аргументы приводятся к неотрицательным взятием модуля: наибольший общий делитель от знака не зависит. Затем повторяется замена пары; когда второй элемент равен нулю, первый и есть искомый делитель. Основание каждого шага — равенство НОД(a, b) = НОД(b, a mod b) из §1. Инвариант цикла: наибольший общий делитель текущей пары равен наибольшему общему делителю исходной. Мера убывания — второй элемент пары: он строго убывает, оставаясь неотрицательным, потому что остаток строго меньше делителя. Крайние случаи: одно из чисел нулевое — цикл не выполняется либо выполняется однократно, и ответом служит модуль другого; оба нулевые — предусловие нарушено, наибольшего общего делителя не существует, и описание отвергает вход. Оценка: число повторений не превосходит удвоенного логарифма меньшего числа по основанию золотого сечения. Худший случай достигается на соседних числах Фибоначчи — это теорема Ламе 1844 года, и её доказательство остаётся в источнике. Вариант с вычитанием вместо взятия остатка описывает тот же метод другим устройством; он проще, но при большой разнице аргументов делает значительно больше повторений. Настоящее изложение фиксирует вариант с остатками.

Referencing norms: f-00ec572fb06c9082e8dd666b, f-0156e6eee92bbe0561b29404, f-0a08aa2c0f1a33e7d17c2281, f-0db404e21c7f54cb9bfc5aa2, f-0e130110449f633b1c722bc6, f-0ed9620da94f988ce2876876, f-0f1d4d7bc0695f87d4ccef3a, f-0fa69613d9c85edbb7c77ec6, f-11ce359cd00333d9b3979065, f-12231979fade060e8c18f34f, f-148b9666fea4227a1f14a107, f-191328ef9c5791fe46be8920, f-21dc7efa08c2c981008be2a2, f-249786ff583be9d71d943725, f-259157df035f64517d66aede, f-2759956c487c077d6cdf711c, f-28d4db2e35d28094b8045280, f-291679c676a6ebbe354f446c, f-2ad7aa4901fc04ab584e0313, f-2b738eca3e9aff8f6ce8a044, f-306e0fa97959b33023c4c24e, f-30e3e3529384a79e9bb4487e, f-332be74e96b30cf93f937419, f-3671a2dfc4ab49e2c10f5798, f-367ab9d146563949f6a9cd6b, f-36b12375dc44cdd316dbfc79, f-36f88e1c308fe8d238240fe4, f-38df197385a39a67d6fce9eb, f-3bab542d3200b4e6ec88806c, f-400a7f00b4fe251de8344147, f-4133df5186732740bf534dab, f-447a167493e6b4dd1b2e96a6, f-483677864bf8c7f7232981bc, f-4a46ce62b150b4aabb5b4775, f-4a595c65e8eb4b9e67e6407d, f-54f4294c04e942552402533f, f-551e4396185c5f08c39581e8, f-6390bf5a79d15fa8fae7ab2d, f-63ad0689337f5974661105ec, f-66e3fd69a05fa796b16cf74e, f-73b5e94e5d8bc58218192ff9, f-7590f54fb973e79878fc01f2, f-77900afd3091440330530a79, f-79e04a3fb9b110c51503ad88, f-7b6ac8e9abca5a2f5a866e57, f-7c400bbf1af15388b736dc61, f-7c79956961f4ba567597f603, f-82a6dd33515fda86bc0cc4ef, f-85cfdfc35e88bb19c0eb72ca, f-89ef1ac2347187387b36ab83, f-8c1dd4089e4b2b03d94e57da, f-8c261f63d4d8e062ef416dfc, f-8fbaa46acc1ab282e4bd00e5, f-93529b8c79c380282dc81f57, f-939f80757dbf2e4dc7f4f3f8, f-9523d59b8f82d10e9a4c0aae, f-97390982365c78fad605935d, f-9836afcb4256b46e58d95660, f-9f68ef44492f435a33aa1a65, f-ab882d8f7758b81cfe063dda, f-ac015811cdc3a465e6f94388, f-ada2f4f650dd48c9a13a4c75, f-ae80b17521f747c315a39055, f-aed1f23eb470bd6dba776625, f-b68667770cd27a141aed1d9d, f-b779baa7d43d0d207155666f, f-c305e7d3fcfeb8eef3fe0662, f-c48c0e974fa5e3b807d69492, f-c855efd24ce519abd3a3621c, f-c92ad4d5733ab5582ed2c7fc, f-caf3bb08f41432c91fbf428a, f-d27cba45f15962d27315f15f, f-d5db3414705acc34900733b5, f-d60f5dd859c1fd6ca71df9fa, f-d668b42b607120dd53043953, f-d73f2478be80a9a93cf7d986, f-d76fa3418c216ffea06d458b, f-d918e00434f91373203eda8e, f-deee36f1745dab19bd9f814d, f-def32ce76c52f8c87089ee3b, f-e1b0c0806cadf89e2efd8829, f-e29468a6a52b26dda50a63c3, f-eb3201cb31ccc15092f8512b, f-ec1f2e64f496a5efd9b4462e, f-f18ba4e7b983375ba3c14740, f-f59ad207ad72df314e454c40, f-fcd45593d4794f3a025a051d

ru · official · sha256:7275a406f3d4022d8d5ea923a820fa03bafe4779da49c10a31eec3ded72ba6a5RU

§3. Расширенный алгоритм Евклида Задача: по двум целым, не равным нулю одновременно, получить их наибольший общий делитель ВМЕСТЕ с парой коэффициентов Безу. Вариант — итеративный, с двумя тройками, обновляемыми одновременно с парой остатков. Хранятся две тройки: текущая (r, x, y) и следующая (r1, x1, y1), для которых выполнено a·x + b·y = r и a·x1 + b·y1 = r1. На каждом шаге вычисляется частное q = r / r1 нацело, и обе тройки заменяются: новая текущая есть прежняя следующая, новая следующая есть покомпонентная разность прежней текущей и прежней следующей, умноженной на q. Инвариант — именно эти два равенства: они сохраняются, потому что вычитание кратного одной тройки из другой сохраняет линейное выражение через a и b. По достижении нулевого r1 текущая тройка даёт и наибольший общий делитель, и коэффициенты. Крайний случай нулевого второго аргумента даёт тройку (|a|, знак a, 0), и её надо предъявлять отдельно: общий цикл её не строит. Коэффициенты Безу не единственны: к паре (x, y) можно прибавить (k·b/g, −k·a/g) при любом целом k. Алгоритм даёт ОДНУ пару, и она удовлетворяет оценке |x| ≤ b/(2g), |y| ≤ a/(2g) при a, b > 0; это утверждение источника, и доказательство остаётся в нём. Применение, ради которого расширенный вариант обычно и нужен: обратный элемент по модулю. Если НОД(a, m) = 1, то коэффициент x при a есть обратный к a по модулю m.

Referencing norms: f-07f244560b94397d279ee6fd, f-0970859d3832e9a9df010dc2, f-0d24726e2d3c1b86ccad15b4, f-0d4be80bafa79f4449b58eb4, f-147e46a34a3c28d31ab3f9d7, f-1a138f44e1d9c4cfe1bc8da9, f-1dc2fa2e5851dc02e7a60380, f-1fc514de52459cb95da69161, f-227e0db8de5bf681b6cbba42, f-2667dffcc119644ef76e64b8, f-26b98f63702c795809dc5489, f-26f7cf9d52161c89072d3e58, f-27353406ca1dfdcfa04df167, f-28418085382174a620627171, f-2afa095ebe2d2cf093ee7fc4, f-2c5792670d0770c29171025f, f-30ba68638ef9bd65ad0f120c, f-351b724f9bc3a385a3eae3bf, f-366354a2b13a4ebb2044df26, f-3814c01d79b71c02d3b801ce, f-3b4e7f04d2646651adea7806, f-3ba7df90f4437a80648f3231, f-3bb6a93a3634ad9593f99b58, f-3d2ae587e18ae719ab6cb15d, f-41b4a19271db59d9e28e8ce7, f-477a442233dec03eea4e92f4, f-49e2551da7f47b85a6ac78d7, f-4a22fce20fb0b3ae4135588e, f-4a4a6f7ee948bf9a00558510, f-4b6011c9d4c97c58ab97fa44, f-4bf306f0ad47f4315d5cb1f9, f-4f94363093b88bc79c4cd693, f-55f3b42ac1a7ef146172398e, f-58872bca928ef571458fd84d, f-5ce68128f790d530204a7acb, f-65ad5874d91944e7abe8ab7e, f-690bd9b379374e46889c433a, f-69c95ad5b229dc6ee6db7e47, f-6ed3dd70a4416ad28498977c, f-72e7eb67f1c595bbe065a9be, f-73bcaad013872e8d09cc73c9, f-7729a9b12443822b513005d8, f-78171cc1c14860a1d95478ba, f-820cb1c7def243f05af99aab, f-8406fa5d22d5699c91ae1f57, f-92fc69a3a7c96b649255e0ea, f-96f3d52480d9bc7e58f8c01f, f-971eb66146fb4cf6acbea334, f-977a699abb20ce0bc17ee2dd, f-9da8cc6817a41bc94a421964, f-9e5ea9df2d830ff8d2ed306f, f-a00089b7820aa9b4afc55c7c, f-a2bba4a4053cf6f74fc9bdcf, f-a34bd21537dad2198cd01705, f-ab267cf4d8cfbfa93537b48d, f-ae36fce771a3dba62c57a32d, f-b6615fe3ff02b3fd2b1869c4, f-b7b1c5958631d5d269c163d6, f-b7b3b430e9e6f01563fa3128, f-b8f009b717d9a1f1b2063b32, f-b9bb3ad989c15e72614491cb, f-bb1a686f2bc27645be968f27, f-bcf6265b2f7d90eddf73d056, f-bf8db53c6b2e9ea75d2c8807, f-c04d948525efd7b990c2f7dc, f-c0d91ab8bc10a508bde75b7f, f-c4006f6f398e0f128df40aaa, f-c558a8c3dda72145e268bb32, f-c6313652eb83c5ec45cc4d77, f-c6c0ed558a1638fb4c750b48, f-c6e01482f414aac1a53d7d00, f-c8bda4a8b7c641b70fd3b16d, f-d0189efcddf400622e65c4cc, f-d0c61de7503627f6d2dfaaf0, f-d1589172bfb62d43dece07a5, f-d4290dd613e4546fcf400643, f-d528378e01745a453a48b6de, f-d7067e637e8b0b6bb06cc1c9, f-d8af6a243b624fcca0cc5515, f-d8d6c9aae0c25670a97e2c7b, f-d8e25067ca95345c1dc3f01f, f-d8f63a34528e7bd69a083fa2, f-e110fc989fb1071fbef37c11, f-e2daf8ee7fe712ea318a372a, f-e3ebaaf20e5c9d49aefe1607, f-e61daaacc5b476f2c41cff6f, f-ea78e4984718edcad94e7a83, f-ed9d1989091a21c614d792d5, f-eeeca79c8d903acd904dab55, f-ef468afc86ed8bb1aba15527, f-ef71b02faefa278d17ad89c0, f-f20999c104e7695a5fd035ba, f-f4195d8a64817d37f7433bfa, f-faa8b160b367f1c791341e2c, f-fab3da6e42ac963951275907, f-fbcce4dd1be1c51672a7b290, f-fd4a999fcff9ab8f6687972e, f-ffb1f3d11642bd7c3e42b924

ru · official · sha256:f3b4813abaa9ddd86d286490a5d045fbd1de8e7e7d964541b824b36eee72a7b3RU

§4. Решето Эратосфена Задача: по натуральному n получить все простые числа, не превосходящие n. Вариант — классический, с вычёркиванием кратных начиная с квадрата очередного простого и с внешним циклом до квадратного корня из n. Заводится таблица отметок для чисел от двух до n, изначально все числа считаются возможно простыми. Далее перебирается p от двух, пока квадрат p не превосходит n: если p не вычеркнуто, вычёркиваются все кратные p начиная с p·p с шагом p. По исчерпании внешнего цикла невычеркнутые числа и есть простые. Начинать вычёркивание с квадрата, а не с удвоенного p, существенно: все меньшие кратные p уже вычеркнуты меньшими простыми множителями. Останавливать внешний цикл на корне из n тоже существенно и по той же причине: составное число, не превосходящее n, имеет делитель, не превосходящий корня из n (§1). Крайние случаи: n меньше двух — простых нет, и таблица пуста; n равно двум — единственное простое есть само n, а внешний цикл не выполняется ни разу. Инвариант внешнего цикла: перед обработкой p вычеркнуты в точности те числа, не превосходящие n, у которых есть простой делитель, меньший p. Мера убывания — число необработанных значений p. Оценка: число операций вычёркивания есть n, умноженное на сумму обратных величин простых до корня из n, что даёт порядок n·log log n. Память — n отметок, и это главный предел метода: сегментное решето, разбивающее диапазон на части, есть другой вариант и в настоящее описание не входит.

Referencing norms: f-0042cd727f95c8e7ef62fd61, f-0430dc57a40af8fddd6e3eba, f-078dddfeff560bffd10b5b2a, f-085cf1185a1013573a0981e3, f-097cb90699d33ed742ab5a8e, f-0a61138b53bd1f6fc79b910a, f-0b73743b6bdb6443ab4af87c, f-0f312325be201e74c8b0912d, f-1166b2c7fc5e68d705ad63b6, f-12479457a0875c067b3b34dc, f-14fd3e7eea10d3c5be41362a, f-1aec2f3a675311c85b76e073, f-1d6021ec57ad2bde7675ada7, f-20e039021d168a7b3e1fd4e3, f-26a876ad4db2c2a9a97cbafa, f-26fc6af0a3b7cdbf267ac62a, f-27e9c49c84ca25e3501c2dd3, f-2af8fd57a019763c2a54845c, f-2b5217507d1d7ffd044ca4ab, f-2f0e857eff56c0a3d07cb350, f-357c0f9aee1b948bd3928a6a, f-36d5af63ea166adb3352fad1, f-372ac908c9fcd6dbc0914a2d, f-3c4274392797377a4aef3527, f-3ddda505c7728511f90548aa, f-4231ef959aadac99845ee18d, f-434ca434976be60642722c9d, f-454e9d1c92fb5a1519c25fda, f-4663cc21969b918ceef3e59b, f-46b504eb9018e5466849c2fe, f-487ef73ebbb615be91941e7e, f-4b4db2e7e5e5c8842018787a, f-516527f19c834b8b1332f5cd, f-53457f7483fe5ae2c5715f98, f-55aef1f8823ef37f1fc5c40a, f-56825a9bcd25757d1206cd22, f-5aba4c39509a76b024b546b7, f-5f08d24edf9ef24bcc4d9b6e, f-65fb8393eddf5407628eb2f2, f-67cd74397feb774d521e6bd8, f-6bd764b005e0efb164d9b16b, f-6fa7ac88ea5471948526b0d5, f-71f648ea1c5fdd77e5b14f5e, f-78882c3b1b6ab8ce68a77df2, f-79ab99005fadafbe5812b1de, f-7b76cd17390b4d23e579974f, f-7c0f2173beb1d0f501b992ac, f-7f3926536bd33681071f8fbf, f-81a446a6d4fea209ed0d9125, f-8765c0754119d5bb32075e2b, f-8d6ae7853d30f7575cb5c73e, f-963703d56df1b3c6924fe386, f-9a97d942051735339eb53c6b, f-9bcb51217e132b6fb5e04c24, f-9f95fd7409bc6a98c6163269, f-9ff967db55c82c934b8d2ae4, f-a29539ba2d279cb274bf4750, f-a58a41978fd89bd14385ed4d, f-aa5ba3fbd5397225b04e436d, f-aaecd752713797122ca598d4, f-acc0e9ac2c9184505b093ac6, f-af86dc6a5eae0a3413d37f07, f-b6fcf70010858fbc4961953f, f-b71ae33d50480e0af5f2b5fd, f-bfa6ba0910c2a0893b39ba9f, f-c1470f3c282399d0da9cab20, f-c1d3cfb71c2796fc48f815fd, f-c2635f36be3c7f3e6fbc62b3, f-c3a3609e175391850096a3c9, f-c493d4c63d4d9c81cafbdb7b, f-c654a502d1890b4d5f6b89f3, f-c75f09dfed73bbc803f09324, f-c8ed3a78db2a83541702f9c0, f-cb70d7275c216c44895de923, f-cc1d1c4d436afac85f6f3af4, f-cc9b80f0ca93c9b3559c2467, f-d1136fe8c6495b29dcf6651b, f-d3406b198b0e56c29e3ab8d4, f-d4717f4986adc1990979fdc7, f-d5b50cb8bfc65273c93afd48, f-da7ff4b8c2ee270164897705, f-e88c9bdc213f73e5d37875bd, f-ea01cabc146afa00d2003fa5, f-eb671f9a1e02f8e0d0c49550, f-ed919becf81041a14c647830, f-ee325166e5636fef58e3b5af, f-efa0b748860f8a6e78cd4d14, f-f21bbaf8913e6316387685ba, f-f9128f83d2dad4422119dd6d, f-fcdddfcc518776e936e54ec3, f-fce96ba65e67df682f975535, f-fd2a7d4272675cd9ec1f94b2, f-fdc5dcf02de31a558893e4b5, f-ff008f138068c78e4314adcf

ru · official · sha256:52a570e1e49c4ff5182a5954621770a7fab6222637550a39b8dd5d8c4b86362aRU

§5. Быстрое возведение в степень Задача: по основанию x и неотрицательному целому показателю n получить x в степени n. Вариант — двоичный, справа налево: показатель разбирается по битам от младшего, основание последовательно возводится в квадрат. Заводятся накопитель, равный единице, текущая степень основания, равная x, и остаток показателя, равный n. Пока остаток показателя отличен от нуля: если он нечётен, накопитель умножается на текущую степень; затем текущая степень возводится в квадрат, а остаток показателя делится на два нацело. Инвариант цикла: произведение накопителя на текущую степень основания, возведённую в остаток показателя, равно x в степени n. Именно он объясняет и умножение при нечётном остатке, и возведение в квадрат. Мера убывания — остаток показателя: он строго убывает при делении на два, оставаясь неотрицательным. Крайние случаи: нулевой показатель — цикл не выполняется, и результат равен единице; при этом нулевое основание в нулевой степени настоящее изложение определяет единицей по соглашению и говорит об этом прямо. Отрицательный показатель предусловием исключён. Оценка: число умножений не превосходит удвоенного двоичного логарифма показателя. Вариант слева направо даёт то же число умножений и не требует хранить возводимую в квадрат степень отдельно; настоящее изложение фиксирует вариант справа налево.

Referencing norms: f-00ed10590907efe6cd704628, f-09b60fa01f9662aabc881ca2, f-0d32c05b6c4efd6f6ab686f8, f-1002252ac7e685bf24474ac7, f-170edb5e3c781a00c0f2fe42, f-18aa0e69c5432284d89244b7, f-1b472f139c9abc4830b76d71, f-1c762a256c3ce8caa57d1e7b, f-1e26a11d1e4f62222cee52b8, f-210d8b658788c7f9d6f50e13, f-217a19cb4064830b0522ac9d, f-244dcf40c0b4ca820d692b62, f-25c2bb21f95c4945a697239f, f-25dbfe24b1b820785f128e06, f-27c7ea9f24915191e59a9c4a, f-29ede4512da3f80e1886f5f8, f-2ddd06b63a6500b91a871246, f-2dffebb828adbcd647d24e8d, f-2e90238ceb959445970b333d, f-32220ca63d42e91e125004d5, f-330da93db26dc2397457314f, f-3847651cd1103eeb12fd043a, f-3a2205d90b85e7d4c7397908, f-3bf60f24d77be88c83e94959, f-3c22fb088324bea679a0e946, f-3e96bec6b8c689b39f12378e, f-419ba5e5bd6421569415df95, f-43ba0fa47ec8f1e8a5656a65, f-473404a5515b4b4cb08c84c5, f-4bb7326794e5f4835870ee23, f-509a03b907aa45c3e59a25ba, f-57f53a4b77e29e406fb84fbd, f-589cb3f8b1a820e642d44a77, f-58b7b4b5057ccea175d727c1, f-5ea5d385d94392415f16810c, f-6460ec9e8aedecd0f8a09b43, f-66b675f9af49c1a330878db6, f-676ddaa0de0f2ac0f9a8d05d, f-67de07b7549f6b4ab8f68615, f-776509a9c63a5a0b7ef3b317, f-7b56f81e819ce7e3324b4794, f-7f4c8e9fd09bf35095b18f83, f-80c1d2f753cdcb2a43f3c29f, f-826d4c18cf728eb46df44d1c, f-87ad6ead4872f0fb6a11ea26, f-89156574b252d0560921cce5, f-8a65b8397c0bcf392cf8b070, f-93332ec5e2be4b199e8b709f, f-941c4ef394bddc14c4701917, f-96325eaf376cfe2d50803d07, f-9636fa91ecfad4d507ce8392, f-a615a4776470e5da5456f9d8, f-a988185c560609702c7c2158, f-aabd82da97a698b2d829037f, f-ab8c781bafe0bc187b325011, f-b000d458ab1a0e02cbce40f7, f-b30f0cc4ac57f83ded824339, f-b533a0d89c7224028d59f498, f-b5c8aa64affd9333715d9823, f-b7f1668c26cf68ba35f565f3, f-bbfaff7510bfa0aa8d0da22f, f-bc121896f8bdb5d4f5fd8bf6, f-bda1121dfd17be6ce582f218, f-be6f83c7bc378b91584dad9d, f-bee0059bf908fc85ae5553b3, f-bf37918c7076d97ff199dcee, f-c134a88000f67c2115e1218e, f-ca9ec60e617e6e09cc596352, f-cbdf84811984e1aa43a8e35c, f-cf7bf3e8ec45e8d1e336dce1, f-d1fed534d735044ead8da2f4, f-d278ca2474d593b60afd6696, f-d7c71367cae4166ce45e18be, f-d8f90484fc6ca5efc1f9d0ea, f-dbd8018afe25fb248815eb6f, f-dd19ecafe4d4587fb26ec7fc, f-e34ff7147f536a292eb208ad, f-e444de3ad490d4e6231f5b33, f-e990763d77bdd8062eac2996, f-ebebc0accef7ead26e34f07a, f-ed2c8ec12db21e725b441bab, f-ef8c8959fbac54584b4c0f60, f-f05067d0e937124687a0ae8f, f-f33f9dd73dc8ece151c71915, f-f57aa2f75cc2620079f51a92, f-f5c43a4093efbab0fd9bdd7a, f-f6d5b15e709a4158ca26a086, f-f7f375e8f4e19f3956186594

ru · official · sha256:a9ff967ec1c5ecae34f9e236044236ed0b646375987a39585e97a353c87b9acbRU

§6. Модульное быстрое возведение в степень Задача: по основанию x, неотрицательному показателю n и модулю m, большему единицы, получить остаток x в степени n по модулю m. Вариант — тот же двоичный справа налево, с приведением по модулю после каждого умножения. Отличие от §5 состоит в одном: после каждого умножения — и накопителя, и возводимого в квадрат основания — берётся остаток по модулю m. Основание для этого даёт согласованность умножения со сравнением из §1: остаток произведения равен остатку произведения остатков. Приведение по модулю удерживает все промежуточные величины меньше квадрата модуля, и это главная причина существования отдельного варианта: без приведения промежуточная степень растёт экспоненциально и вычислена быть не может. Крайние случаи: модуль, равный единице, даёт нулевой остаток при любом основании и показателе, и этот случай называется отдельно; нулевой показатель даёт остаток единицы по модулю m, то есть единицу при m больше единицы. Оценка: число умножений то же, что в §5, но каждое умножение выполняется над числами меньше модуля, поэтому стоимость шага ограничена и не растёт. Настоящее описание не утверждает устойчивости к атакам по времени: постоянное время выполнения есть отдельное требование, отдельный вариант и в изложение не входит.

Referencing norms: f-006a08efcdfe804954b53dd8, f-0186b1be107352ea658d3f40, f-02139a45d98f7f366fc3efed, f-03d604532fe25563a4e9dfeb, f-03e4a8c453e045ca4707e5c9, f-04cd117d3e71939929b25b1a, f-0624ea54e6f573b66dd6ccce, f-0f1e7e205b3086dc270842bd, f-108918280091c8e655ed9e48, f-15f4465b1be99d40bcf6e267, f-1a9d931a927227462920c014, f-20373b2e417798355275146c, f-20de8687a42d90075ce17e3f, f-23e5d83c4b4aa773a09e77ec, f-268a0a61d64afd22de4038c0, f-26b54ba09fe8fea4951e4311, f-27c5dab413090c65bd019684, f-280713918d88111f170b25a4, f-2888d28f58a0a79709e2046d, f-2a053cd9cf3084f9173f939f, f-2c01860e49de44c139401e08, f-3395ddd4d8526e27ffbfc200, f-350e027e8c8d0458772ac69b, f-35712e726b51b829121ae887, f-36b5b670e043179c89ef1be6, f-36dae72dcfd792fa8d9362e3, f-3faea2954dadd8784a06c1c6, f-4212edcb79175a3c6486daa2, f-42e093ef094fbde8e1c47d79, f-4431eeb48e77bc1cc84cc661, f-4649fa20befb125b0bbad6e5, f-47eb665fb704201405ebcef6, f-4b5dada3d0aae7f9a7fd6b61, f-4d5b9650e5147b5cb833a8bb, f-570c088e64a1c874e8242be6, f-57b93abe5993cccc2c20acdc, f-5d1ba3b60fc1560218f34709, f-5f0db2df6de78e151fe4c58a, f-62cdbec84167cfd2b1fe3ca5, f-6370d778fe6fb93ccdd59463, f-676a282ca75010928e51bc0e, f-6aa816b9eaf7814c696a8518, f-6c3a80702235cb3de1c80113, f-6eee5adebaeaab88fef73ef1, f-6fe7d67baa437d3a650f6cf3, f-7087481483d901fa5579be01, f-7774c3aa2187f9b79282a94a, f-779631ba21ed4fd17aaff6a8, f-77cd906a0bbb2df42650fd1f, f-7aa33e1163af88182a9b68ce, f-7afa5cdae0fbb3347d24dd77, f-7bdee627ce395d0fc0f3b633, f-7ed6d2eacf5d6c704050aefc, f-7ff9a20f35666ddd781a443c, f-803868ffe8f1df3d12aaf77d, f-85ab9de685a0ad98de96f7b1, f-8cafe28922ac74c75b0e1f59, f-8dd669b4452d0181f73faf49, f-8df172cb723cd0e27a36496f, f-901802a9807701c45454fd9f, f-93db8cc233538cfd54b2ac5e, f-94bec25721492b7b903213f4, f-983333c0e48931b670cd3501, f-98487f6077824ca6a19acc91, f-9e239eda7d1452f64484632e, f-a24563cb90dff7ff0f67959d, f-aa5f30b7e3eca67060ffb8a4, f-aad42d13cdd19b177cb18697, f-adb02d83dd1f6778de7e7a9e, f-afdf4cc6c95046282f460231, f-b401509299579cab85285f18, f-b7eb06532de6b9760a698d75, f-b9a225c1ceb1db43df8b20c0, f-c35c488900c753f5967fe55e, f-c376be87530e1ad16f2cc5fc, f-c604597470c99858e2a750c2, f-c65e5199887ee5139df2e272, f-ca2c3c8068e6fce451fc7588, f-cb62f8ac29d936a700c423a1, f-cfdf67cad643fd276e32dc5f, f-d09703111d8133bfafffa322, f-d0e6d6857f2de65f88ed051d, f-d1401d510d7a83f56ebccdc4, f-d2d67d5cf01255a10df6b99b, f-d7bde1bd7caa01798a5bb66a, f-d8b04ec7c2a48838b8fa41c7, f-d8be053902f54f5381e77a98, f-dc4ec3c88ee9306ac3b5f197, f-e6e439dd1be5cdd329733a5f, f-e7b7ea9d063692c80bdee74d, f-e95d9b77566ea246d74607ea, f-eba55f9ce4320b51496e2abf, f-f388ad4190b820ed45451071, f-f414e4078d1d3decb14786e4, f-f60b60b1425613264c1f4e7c, f-f97c3db60ca918d10df21a92, f-fde3f2474a05702eb8ca28b3, f-ff03d14251dd02913a1d9041

ru · official · sha256:bf655c65982da7eb064903bab20d4f8c2ebfe607fcc26f4711af10079acb66ccRU

ТЕОРИЯ ЧИСЕЛ: НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ, РЕШЕТО И БЫСТРОЕ ВОЗВЕДЕНИЕ В СТЕПЕНЬ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство пяти алгоритмов: алгоритма Евклида и его расширенного варианта, решета Эратосфена, быстрого возведения в степень и его модульного варианта. Изложение не воспроизводит ни один учебник. Происхождение каждого алгоритма названо при его описании локатором; байты первых публикаций не закрепляются. Формулировка шагов, их нумерация и выбор варианта принадлежат настоящему изложению. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: наибольший общий делитель конкретной пары чисел настоящим документом не вычисляется.