Сандық теорияда индекстік есептеу алгоритмі

Кіріспе

Есептеулік сандар теориясында индекстік есептеу алгоритмі – дискретті логарифмдерді есептеуге арналған ықтималдық алгоритм. p саны жай сан болатын дискретті логарифм үшін арналған индекстік есептеу, шекті өрістерге және эллиптік қисықтардың кейбір түрлеріне бейімделген алгоритмдер отбасына әкеледі. Алгоритм кіші жай сандардың дискретті логарифмдері арасындағы қатынастарды жинақтап, оларды сызықтық алгебра тәсілімен есептейді және соңында қажетті дискретті логарифмді кіші жай сандардың дискретті логарифмдері арқылы көрсетеді.

Сипаттама

Шамамен айтқанда, дискретті логарифмдеу мәселесі бізден g, h және n модулі берілгенде, x табуды сұрайды. Алгоритм (төменде егжей-тегжейлі сипатталған) q-прост топқа қолданылады. Ол кіріс ретінде факторлық базаны қажет етеді. Бұл факторлық база әдетте -1 саны мен 2-ден басталатын алғашқы r жай саннан тұрады. Тиімділік тұрғысынан, біз осы факторлық базаның кіші болғанын қалаймыз, бірақ үлкен топ үшін дискретті логарифмді шешу үшін факторлық базаның (салыстырмалы түрде) үлкен болуын қажет етеміз. Алгоритмнің практикалық іске асырылуында осы қарама-қайшылық мақсаттардың арасында белгілі бір тепе-теңдік орнатылады. Алгоритм үш кезеңнен тұрады. Алғашқы екі кезең тек генератор g және жай модуль q-ға байланысты, және r кіші жай санның факторлық базасының дискретті логарифмдерін табады. Үшінші кезең h санының дискретті логарифмін факторлық базаның дискретті логарифмдері арқылы анықтайды. Бірінші кезең факторлық база мен генератордың g дәрежесі арасындағы r сызықтық тәуелсіз қатынастар жиынтығын іздеуден тұрады. Әр қатынас r белгісізі бар сызықтық теңдеулер жүйесіне бір теңдеу қосады, атап айтқанда, факторлық базадағы r жай санның дискретті логарифмдерін. Бұл кезең оңай параллелдеуге болады және оны көптеген компьютерлер арасында бөлуге болады. Екінші кезең факторлық базаның дискретті логарифмдерін есептеу үшін сызықтық теңдеулер жүйесін шешеді. Жүздеген мыңдаған немесе миллиондаған теңдеулер жүйесі – бұл үлкен жадты қажет ететін маңызды есептеу, және ол оңай параллелдеуге келмейді, сондықтан әдетте суперкомпьютер қолданылады. Бұл кішкентай дискретті логарифмді есептеулер үшін салыстырмалы түрде шағын қадам болып саналды. Дегенмен, үлкен дискретті логарифмдік жазбалар тек жұмысты сызықтық алгебрадан сілемге ауыстыру арқылы (яғни, айнымалылар санын азайту арқылы теңдеулер санын арттыру арқылы) мүмкін болды. Үшінші кезең генератордың g дәрежесін іздейді, оны h аргументімен көбейту арқылы gsh = (−1)f0 2f1 3f2···prfr түрінде факторлауға болады. Соңында, төртінші кезең деп атауға тым қарапайым операцияда, екінші және үшінші кезеңдердің нәтижелерін қарапайым алгебралық амалдар арқылы қайта реттеуге болады, нәтижесінде қажетті дискретті логарифм x = f0logg(−1) + f1logg2 + f2logg3 + ··· + frloggpr − s шығады.

Roughly speaking, the discrete log problem asks us to find an x such that , where g, h, and the modulus n are given. The algorithm (described in detail below) applies to the group where q is prime. It requires a factor base as input. This factor base is usually chosen to be the number −1 and the first r primes starting with 2. From the point of view of efficiency, we want this factor base to be small, but in order to solve the discrete log for a large group we require the factor base to be (relatively) large. In practical implementations of the algorithm, those conflicting objectives are compromised one way or another. The algorithm is performed in three stages. The first two stages depend only on the generator g and prime modulus q, and find the discrete logarithms of a factor base of r small primes. The third stage finds the discrete log of the desired number h in terms of the discrete logs of the factor base. The first stage consists of searching for a set of r linearly independent relations between the factor base and power of the generator g. Each relation contributes one equation to a system of linear equations in r unknowns, namely the discrete logarithms of the r primes in the factor base. This stage is embarrassingly parallel and easy to divide among many computers. The second stage solves the system of linear equations to compute the discrete logs of the factor base. A system of hundreds of thousands or millions of equations is a significant computation requiring large amounts of memory, and it is not embarrassingly parallel, so a supercomputer is typically used. This was considered a minor step compared to the others for smaller discrete log computations. However, larger discrete logarithm records were made possible only by shifting the work away from the linear algebra and onto the sieve (i. e., increasing the number of equations while reducing the number of variables). The third stage searches for a power s of the generator g which, when multiplied by the argument h, may be factored in terms of the factor base gsh = (−1)f0 2f1 3f2···prfr. Finally, in an operation too simple to really be called a fourth stage, the results of the second and third stages can be rearranged by simple algebraic manipulation to work out the desired discrete logarithm x = f0logg(−1) + f1logg2 + f2logg3 + ··· + frloggpr − s.

Бірінші және үшінші кезеңдер екеуі де оңай параллелдеуге болады, және шын мәнінде үшінші кезең алғашқы екі кезеңнің нәтижелеріне тәуелді емес, сондықтан оны олармен бірдей уақытта орындауға болады. Факторлық базаның өлшемі r таңдау өте маңызды, және оның егжей-тегжейлі сипаттамасы осы жерде мүмкін емес. Факторлық база неғұрлым үлкен болса, 1-кезеңде қатынастарды табу оңайырақ болады, және 3-кезеңді аяқтау оңайырақ болады, бірақ 2-кезеңге өту үшін сізге көбірек қатынастар қажет, және 2-кезең оңайырақ болады. 1 және 2-кезеңдер үшін қажетті есептеулердің әртүрлі түрлеріне сәйкес келетін компьютерлердің қолжетімділігі де маңызды.

Басқа топтардағы қолданулар

Эллиптік қисықтардағы нүктелер тобындағы жай элементтер ұғымының болмауы, осы топтарда көрсетілген индекстік есептеу әдісін қолдану үшін тиімді факторлық базаны табуға мүмкіндік бермейді. Сондықтан, бұл алгоритм эллиптік қисықтар тобындағы дискретті логарифмдерді тиімді түрде шеше алмайды. Дегенмен: ерекше қисықтардың (суперсинглярлық эллиптік қисықтар деп аталады) үшін, мәселені жалпы әдістерге қарағанда жылдам шешуге арналған мамандандырылған алгоритмдер бар. Бұл ерекше қисықтарды пайдаланудан оңай қашуға болатындықтан, 2009 жылы белгілі бір өрістер үшін, осы өрістердегі жалпы эллиптік қисықтардағы нүктелер тобындағы дискретті логарифм мәселесін жалпы әдістерге қарағанда жылдам шешуге болатыны дәлелденді. Алгоритмдер, шындығында, индекстік есептеу әдісінің өңделген нұсқалары болып табылады.

Тарих

Алгоритмнің негізгі идеясы Western және Miller (1968) еңбегіне қарызды, ол Kraitchik (1922) идеяларына тікелей байланысты. Алғашқы практикалық іске асырулар 1976 жылы дискретті логарифмге негізделген Диффи-Хеллман криптожүйесі таныстырылғаннан кейін жүзеге асты. Мерклдің Стэнфорд университетіндегі диссертациясы (1979) Полиг (1977) және Хеллман мен Рейнери (1983) тарапынан бағаланды, сондай-ақ олар іске асыруды жетілдірді. Адлеман алгоритмді оңтайландырып, оны қазіргі түрінде ұсынды.

Индекс Калькулус туысы

Индекс калькулусы көптеген алгоритмдер отбасын қалыптастырды. Шешімді өрістерде, үшін, кейбір жағдайда ең озық алгоритмдер – дискретті логарифмдер үшін сандық өрістердің ілкіші, , егер - ға қарағанда үлкен болса, функциялық өрістердің ілкіші, , егер - ға қарағанда кішкентай болса, және жоғары дәрежелі сандық өрістердің ілкіші, егер орташа мәнде болса. Кейбір эллипстік қисықтар отбасы үшін дискретті логарифмді уақыт ішінде шешуге болады, бірақ жалпы жағдай экспоненциалды болып қалады.