В учебном пособии подробно рассматриваются четыре задачи, привлекающие внимание исследователей на протяжении последних десятилетий: разложение больших составных чисел на множители, дискретное логарифмирование в мультипликативной группе вычетов по простому модулю, решение больших разреженных систем линейных уравнений над конечными полями, вычисление ранга эллиптических кривых, определенных над полем рациональных чисел. Наиболее быстрые алгоритмы решения первых двух задач основаны на так называемом алгоритме решета числового поля, сводящем их к решению больших разреженных систем линейных уравнений над конечными полями. Системы эти настолько велики, что к ним не применимы обычные алгоритмы решения. Используются специальные блочные итерационные алгоритмы. Эта область прикладной теории чисел активно развивается во всем мире в связи с приложениями в криптографии. Из-за отсутствия нижних оценок сложности решения этих теоретико-числовых задач, единственным способом проверки...
V uchebnom posobii podrobno rassmatrivajutsja chetyre zadachi, privlekajuschie vnimanie issledovatelej na protjazhenii poslednikh desjatiletij: razlozhenie bolshikh sostavnykh chisel na mnozhiteli, diskretnoe logarifmirovanie v multiplikativnoj gruppe vychetov po prostomu modulju, reshenie bolshikh razrezhennykh sistem linejnykh uravnenij nad konechnymi poljami, vychislenie ranga ellipticheskikh krivykh, opredelennykh nad polem ratsionalnykh chisel. Naibolee bystrye algoritmy reshenija pervykh dvukh zadach osnovany na tak nazyvaemom algoritme resheta chislovogo polja, svodjaschem ikh k resheniju bolshikh razrezhennykh sistem linejnykh uravnenij nad konechnymi poljami. Sistemy eti nastolko veliki, chto k nim ne primenimy obychnye algoritmy reshenija. Ispolzujutsja spetsialnye blochnye iteratsionnye algoritmy. Eta oblast prikladnoj teorii chisel aktivno razvivaetsja vo vsem mire v svjazi s prilozhenijami v kriptografii. Iz-za otsutstvija nizhnikh otsenok slozhnosti reshenija etikh teoretiko-chislovykh zadach, edinstvennym sposobom proverki...
