Vyčislitel′no složnye zadači teorii čisel: Učeb. Posobie

V učebnom posobii podrobno rassmatrivajutsja četyre zadači, privlekajučšie vnimanie issledovatelej na protjaženii poslednich desjatiletij: razloženie bol′šich sostavnych čisel na množiteli, diskretnoe logarifmirovanie v mul′tiplikativnoj gruppe vyčetov po prostomu modulju, rešenie bol′šich razrežennych sistem linejnych uravnenij nad konečnymi poljami, vyčislenie ranga ėlliptičeskich krivych, opredelennych nad polem racional′nych čisel. Naibolee bystrye algoritmy rešenija pervych dvuch zadač osnovany na tak nazyvaemom algoritme rešeta čislovogo polja, svodjačšem ich k rešeniju bol′šich razrežennych sistem linejnych uravnenij nad konečnymi poljami. Sistemy ėti nastol′ko veliki, čto k nim ne primenimy obyčnye algoritmy rešenija. Ispol′zujutsja special′nye bločnye iteracionnye algoritmy. Ėta oblast′ prikladnoj teorii čisel aktivno razvivaetsja vo vsem mire v svjazi s priloženijami v kriptografii. Iz-za otsutstvija nižnich ocenok složnosti rešenija ėtich teoretiko-čislovych zadač, edinstvennym sposobom proverki nadežnosti ispol′zuemych kriptografičeskich algoritmov služit ich praktičeskaja proverka s ispol′zovaniem samych soveršennych algoritmov i naibolee močšnoj vyčislitel′noj techniki. Ključevye slova: faktorizacija, diskretnoe logarifmirovanie, razrežennye linejnye sistemy uravnenij, rang ėlliptičeskoj krivoj.