Кіріспе
Тонелли–Шенкс алгоритмі (Шенкс оны RESSOL алгоритмі деп атайды) модульдік арифметикада r² ≡ n (mod p) түріндегі сәйкестікте r-ді табу үшін қолданылады, мұнда p – жай сан: яғни, n-нің p модулі бойынша квадрат түбірін табу үшін. Тонелли–Шенкс алгоритмін құрама модульдер үшін қолдануға болмайды: құрама сандар модулі бойынша квадрат түбір табу, бүтін сандарды жіктеуге тең есептеу мәселесі болып табылады. Осы алгоритмнің эквивалентті, бірақ сәл артық нұсқасын 1891 жылы Альберто Тонелли жасаған. Бұл жерде талқыланатын нұсқаны 1973 жылы Дэниел Шенкс тәуелсіз түрде жасады және былай деп түсіндірді:
Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly more redundant version of this algorithm was developed by
Alberto Tonelli
in 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained:
My tardiness in learning of these historical references was because I had lent Volume 1 of Dickson's History to a friend and it was never returned. According to Dickson, The average of two computations of the Legendre symbol are explained as follows: is a quadratic residue with chance , which is smaller than but , so we will on average need to check if a is a quadratic residue two times. This shows essentially that the Tonelli–Shanks algorithm works very well if the modulus is random, that is, if is not particularly large with respect to the number of digits in the binary representation of As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if) However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2 Sylow subgroup of , one may replace with an expression that is asymptotically bounded by Explicitly, one computes such that and then satisfies (note that is a multiple of 2 because is a quadratic residue). The algorithm requires us to find a quadratic nonresidue There is no known deterministic algorithm that runs in polynomial time for finding such a However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue , making it possible to check every up to that limit and find a suitable within polynomial time. Keep in mind, however, that this is a worst case scenario; in general, is found in on average 2 trials as stated above.
Мен осы тарихи сілтемелерді білуге кешіккенімнің себебі, мен Диксонның «Тарихының» 1-томын досыма беріп, ол оны маған қайтарған жоқ. Диксонның сөзіне сүйенсек, Лежандр символының екі есептеуінің орташасы былай түсіндіріледі: – бұл квадраттық қалдық болу ықтималдығы , ол -тан кіші, бірақ -тан үлкен, сондықтан орташа есеппен a-ның квадраттық қалдық екенін екі рет тексеруіміз керек. Бұл, негізінен, Тонелли–Шенкс алгоритмінің модулі кездейсоқ болғанда, яғни егер өте жақсы жұмыс істейтінін көрсетеді. Жоғарыда айтылғандай, Циполла алгоритмі (және тек егер) болса, Тонелли–Шенкс алгоритмінен жақсы жұмыс істейді. Алайда, егер Сазерленд алгоритмін қолданып, -ның 2 Sylow кіші тобындағы дискретті логарифмді есептесек, оны асимптотикалық түрде шектелген өрнекпен алмастыруға болады. Алгоритм бізге квадраттық емес қалдық табуды талап етеді. Мұндай қалдықты табу үшін полиномдық уақытта жұмыс істейтін белгілі детерминистік алгоритм жоқ. Алайда, егер жалпыланған Риман гипотезасы дұрыс болса, онда квадраттық емес қалдық бар, бұл белгілі бір шекке дейін барлық сандарды тексеруге және полиномдық уақыт ішінде қолайлы қалдық табуға мүмкіндік береді. Дегенмен, бұл ең нашар жағдай екенін есте ұстаңыз; жалпы алғанда, жоғарыда айтылғандай, орташа есеппен 2 сынақтан кейін табылады.
Tonelli–Shanks cannot be used for composite moduli: finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. An equivalent, but slightly more redundant version of this algorithm was developed by
Alberto Tonelli
in 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained:
My tardiness in learning of these historical references was because I had lent Volume 1 of Dickson's History to a friend and it was never returned. According to Dickson, The average of two computations of the Legendre symbol are explained as follows: is a quadratic residue with chance , which is smaller than but , so we will on average need to check if a is a quadratic residue two times. This shows essentially that the Tonelli–Shanks algorithm works very well if the modulus is random, that is, if is not particularly large with respect to the number of digits in the binary representation of As written above, Cipolla's algorithm works better than Tonelli–Shanks if (and only if) However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2 Sylow subgroup of , one may replace with an expression that is asymptotically bounded by Explicitly, one computes such that and then satisfies (note that is a multiple of 2 because is a quadratic residue). The algorithm requires us to find a quadratic nonresidue There is no known deterministic algorithm that runs in polynomial time for finding such a However, if the generalized Riemann hypothesis is true, there exists a quadratic nonresidue , making it possible to check every up to that limit and find a suitable within polynomial time. Keep in mind, however, that this is a worst case scenario; in general, is found in on average 2 trials as stated above.
Қолданылуы
Тонелли-Шенкс алгоритмі (әдеттегідей) жай сан бойынша модульдік квадрат түбірлер қажет болатын кез келген процесте қолданылуы мүмкін. Мысалы, оны эллиптік қисықтардағы нүктелерді табу үшін пайдалануға болады. Бұл Рабин криптожүйесіндегі және квадраттық елеуіштің іріктеу кезеңіндегі есептеулер үшін де пайдалы.