Тонелли-Хвостовики алгоритм (далее по Шанксу как алгоритм RESSOL) используется в модульной арифметике решить для г в конгруэнции вида г 2 ≡ п ( по модулю р ), где р представляет собой простой : то есть, чтобы найти квадратный корень из n по модулю p .
Тонелли – Шанкс нельзя использовать для составных модулей: поиск квадратных корней по модулю составных чисел является вычислительной проблемой, эквивалентной целочисленной факторизации . [1]
Эквивалентная, но немного более избыточная версия этого алгоритма была разработана Альберто Тонелли [2] [3] в 1891 году. Обсуждаемая здесь версия была независимо разработана Дэниелом Шанксом в 1973 году, который объяснил:
Мое опоздание с изучением этих исторических ссылок было вызвано тем, что я одолжил первый том « Истории» Диксона другу, и он так и не был возвращен. [4]
Согласно Диксону [3] алгоритм Тонелли может извлекать квадратные корни из x по модулю простых степеней p λ, кроме простых чисел.
Основные идеи
Учитывая ненулевое значение и нечетное простое число , Критерий Эйлера говорит нам, что имеет квадратный корень (т. е. является квадратичным вычетом ) тогда и только тогда, когда:
.
Напротив, если число не имеет квадратного корня (не является вычетом), критерий Эйлера говорит нам, что:
.
Найти такие , потому что половина целых чисел от 1 до есть это свойство. Итак, мы предполагаем, что у нас есть доступ к такому невычету.
Делясь (обычно) на 2 несколько раз, мы можем написать в виде , где странно. Обратите внимание, что если мы попробуем
,
тогда . Если, тогда квадратный корень из . В противном случае для, у нас есть а также удовлетворение:
; а также
это -й корень из 1 (потому что ).
Если при выборе а также для конкретного удовлетворяющий вышеуказанному (где не является квадратным корнем из ), мы можем легко вычислить другой а также для так, чтобы выполнялись указанные выше соотношения, то мы можем повторять это до становится корень -й степени из 1, т. е. . В таком случае квадратный корень из .
Мы можем проверить, есть ли это корень 1-й степени из 1, возведя его в квадрат раз и проверяем, 1. Если это так, то ничего делать не нужно, тот же выбор а также работает. Но если это не так, должно быть -1 (потому что возведение в квадрат дает 1, и может быть только два квадратных корня 1 и -1 из 1 по модулю ).
Чтобы найти новую пару а также , мы можем умножить фактором , быть определенным. потом необходимо умножить на коэффициент хранить . Итак, нам нужно найти фактор чтобы это корень -й степени из 1 или эквивалентно это корень -й степени из -1.
Хитрость здесь в том, чтобы использовать , известный без остатка. Критерий Эйлера, примененный к показанный выше говорит, что это корень -й степени из -1. Итак, возведя в квадрат неоднократно у нас есть доступ к последовательности корень -й степени из -1. Мы можем выбрать подходящий, чтобы служить. Приведенный ниже алгоритм появляется естественным образом после небольшого обслуживания переменных и упрощенного сжатия регистров.
В противном случае используйте повторное возведение в квадрат, чтобы найти наименьшее i , 0 < i < M , такое, что
Позволять , и установите
После того, как вы решите сравнение с r, второе решение будет. Если хотя бы я такой, чтоесть M , то решения сравнения не существует, т. е. n не является квадратичным вычетом.
Это наиболее полезно, когда p 1 (mod 4).
Для простых чисел, таких что p ≡ 3 (mod 4), эта проблема имеет возможные решения. Если они удовлетворяют, это единственные решения. Если не,, n - квадратичный невычет, решений нет.
Доказательство
Мы можем показать, что в начале каждой итерации цикла выполняются следующие инварианты цикла :
Первоначально:
(поскольку z - квадратичный невычет по критерию Эйлера)
(поскольку n - квадратичный вычет)
На каждой итерации с M ' , c' , t ' , R' новые значения заменяют M , c , t , R :
так как у нас есть это но ( i - наименьшее значение такое, что)
Из и тест на t = 1 в начале цикла, мы видим, что мы всегда найдем i в 0 < i < M такое, что. M строго меньше на каждой итерации, и поэтому алгоритм гарантированно останавливается. Когда мы достигаем условия t = 1 и останавливаемся, последний инвариант цикла означает, что R 2 = n .
Порядок т
Мы можем альтернативно выразить инварианты цикла, используя порядок элементов:
как прежде
Каждый шаг алгоритма перемещает t в меньшую подгруппу, измеряя точный порядок t и умножая его на элемент того же порядка.
Пример
Решение сравнения r 2 ≡ 5 (mod 41). 41 является простым числом, как требуется, и 41 1 (mod 4). 5 - квадратичный вычет по критерию Эйлера: (как и раньше, операции в неявно являются mod 41).
так ,
Найдите значение для z:
, поэтому 2 - квадратичный вычет по критерию Эйлера.
, поэтому 3 - квадратичный невычет: set
Набор
Петля:
Первая итерация:
, так что мы еще не закончили
, так
Вторая итерация:
, так что мы еще не закончили
так
Третья итерация:
, и мы закончили; возвращаться
Действительно, 28 2 5 (mod 41) и (−28) 2 ≡ 13 2 ≡ 5 (mod 41). Таким образом, алгоритм дает два решения нашего сравнения.
Скорость алгоритма
Алгоритм Тонелли – Шанкса требует (в среднем по всем возможным входным данным (квадратичным вычетам и квадратичным невычетам))
модульные умножения, где это количество цифр в двоичном представлении а также это количество единиц в двоичном представлении . Если требуемый квадратичный невычет можно найти, проверив, является ли случайно выбранный номер является квадратичным невычетом, требует (в среднем) вычисления символа Лежандра. [5] Среднее значение двух вычислений символа Лежандра объясняется следующим образом: квадратичный вычет со случайностью , что меньше, чем но , поэтому в среднем нам нужно будет проверить, есть ли является двукратным квадратичным вычетом.
По сути, это показывает, что алгоритм Тонелли – Шанкса работает очень хорошо, если модуль является случайным, то есть если не особенно велика по отношению к количеству цифр в двоичном представлении . Как написано выше, алгоритм Чиполлы работает лучше, чем алгоритм Тонелли – Шанкса, если (и только если). Однако, если вместо этого использовать алгоритм Сазерленда для вычисления дискретного логарифма в 2-силовской подгруппе, можно заменить с выражением, которое асимптотически ограничено . [6] В явном виде вычисляется такой, что а потом удовлетворяет (Обратите внимание, что делится на 2, потому что является квадратичным вычетом).
Алгоритм требует от нас найти квадратичный невычет . Не существует известного детерминированного алгоритма, который работал бы за полиномиальное время для поиска такого. Однако если обобщенная гипотеза Римана верна, существует квадратичный невычет, [7] позволяя проверять каждый до этого предела и найти подходящий за полиномиальное время . Однако имейте в виду, что это наихудший сценарий; в общем, обнаруживается в среднем в 2 испытаниях, как указано выше.
Использует
Алгоритм Тонелли – Шанкса может (естественно) использоваться для любого процесса, в котором необходимы квадратные корни по простому модулю. Например, его можно использовать для поиска точек на эллиптических кривых . Это также полезно для вычислений в криптосистеме Рабина и на этапе просеивания квадратного сита .
Обобщения
Тонелли – Шанкса можно обобщить на любую циклическую группу (вместо ) и корням k для произвольного целого числа k , в частности, взятию корня k- й степени из элемента конечного поля . [8]
Если в одной и той же циклической группе должно быть получено много квадратных корней, а S не слишком велик, таблица квадратных корней элементов 2-го порядка может быть подготовлена заранее, а алгоритм упрощен и ускорен следующим образом.
Выносим за скобки степени 2 из p - 1, определяя Q и S как:с нечетным Q.
^Сазерленд, Эндрю В. (2011), "Структура вычисление и дискретные логарифмы в конечном абелевых р-групп", Математика вычислений , 80 : 477-500, Arxiv : 0809.3413 , DOI : 10,1090 / s0025-5718-10-02356-2
^Бах, Эрик (1990), "Явные оценки для проверки простоты чисел и связанных с ними проблемы", Математика вычислений , 55 (191): 355-380, DOI : 10,2307 / 2008811 , JSTOR 2008811
↑ Адлеман, Л. М., К. Мандерс и Г. Миллер: 1977, «Об укоренении в конечных полях». В: 18-й симпозиум IEEE по основам информатики. С. 175-177.
^ "Accademia nazionale dei Lincei, Рим. Rendiconti, (5), 1, 1892, 116-120."
Рекомендации
Иван Нивен; Герберт С. Цукерман; Хью Л. Монтгомери (1991). Введение в теорию чисел (5-е изд.). Вайли. С. 110–115 . ISBN 0-471-62546-9.
Дэниел Шэнкс. Теоретические алгоритмы пяти чисел. Труды Второй конференции Манитобы по вычислительной математике. Стр. 51–70. 1973 г.
Альберто Тонелли, Bemerkung über die Auflösung quadratischer Congruenzen. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen. Стр. 344–346. 1891. [1]
Гаган Тара Нанда - Математика 115: Алгоритм RESSOL [2]