Vychislitel′no slozhnye zadachi teorii chisel: Ucheb. Posobie

V uchebnom posobii podrobno rassmatrivayutsya chetyre zadachi, privlekayushhie vnimanie issledovatelej na protyazhenii poslednich desyatiletij: razlozhenie bol′shich sostavnych chisel na mnozhiteli, diskretnoe logarifmirovanie v mul′tiplikativnoj gruppe vychetov po prostomu modulyu, reshenie bol′shich razrezhennych sistem linejnych uravnenij nad konechnymi polyami, vychislenie ranga ellipticheskich krivych, opredelennych nad polem racional′nych chisel. Naibolee bystrye algoritmy resheniya pervych dvuch zadach osnovany na tak nazyvaemom algoritme resheta chislovogo polya, svodyashhem ich k resheniyu bol′shich razrezhennych sistem linejnych uravnenij nad konechnymi polyami. Sistemy eti nastol′ko veliki, chto k nim ne primenimy obychnye algoritmy resheniya. Ispol′zuyutsya special′nye blochnye iteracionnye algoritmy. Eta oblast′ prikladnoj teorii chisel aktivno razvivaetsya vo vsem mire v svyazi s prilozheniyami v kriptografii. Iz-za otsutstviya nizhnich ocenok slozhnosti resheniya etich teoretiko-chislovych zadach, edinstvennym sposobom proverki nadezhnosti ispol′zuemych kriptograficheskich algoritmov sluzhit ich prakticheskaya proverka s ispol′zovaniem samych sovershennych algoritmov i naibolee moshhnoj vychislitel′noj techniki. Klyuchevye slova: faktorizaciya, diskretnoe logarifmirovanie, razrezhennye linejnye sistemy uravnenij, rang ellipticheskoj krivoj.