Введение
Алгоритм Тонелли–Шенкса (называемый Шенксом алгоритмом RESSOL) используется в модульной арифметике для решения уравнения относительно r в конгруэнции вида r2 ≡ n (mod p), где 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.
Моя задержка с ознакомлением с этими историческими ссылками была связана с тем, что я одолжил первый том «Истории Диксона» другу, и он так и не был возвращен. Согласно Диксону, среднее значение двух вычислений символа Лежандра объясняется следующим образом: вероятность того, что является квадратичным вычетом, равна , что меньше, чем , но , поэтому в среднем потребуется проверить, является ли a квадратичным вычетом, дважды. Это показывает, что алгоритм Тонелли–Шенкса работает очень хорошо, если модуль p случаен, то есть если не особенно велик по отношению к количеству цифр в двоичном представлении . Как указано выше, алгоритм Чиполлы работает лучше, чем алгоритм Тонелли–Шенкса, если (и только если) . Однако, если вместо этого использовать алгоритм Сазерленда для вычисления дискретного логарифма в 2-й Силовой подгруппе , можно заменить на выражение, асимптотически ограниченное . Явно, вычисляется такое , что и затем удовлетворяет (обратите внимание, что кратно 2, поскольку является квадратичным вычетом). Алгоритм требует найти квадратичный невычет. Нет известного детерминированного алгоритма, работающего за полиномиальное время для поиска такого . Однако, если обобщенная гипотеза Римана верна, существует квадратичный невычет, что позволяет проверить все числа до этого предела и найти подходящее за полиномиальное время. Следует помнить, однако, что это наихудший сценарий; в общем случае, находится в среднем за 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.
Применение
Алгоритм Тонелли-Шенкса может (естественно) использоваться в любом процессе, где требуется вычисление квадратных корней по модулю простого числа. Например, он может быть использован для нахождения точек на эллиптических кривых. Он также полезен при вычислениях в криптосистеме Рабина и на этапе просеивания в квадратичном решете.