Калькулятор модульного квадратного корня Тонелли-Шенкса

Введите n и простое число p, чтобы найти модульный квадратный корень.

Как пользоваться

  1. Введите нужные значения в поля.
  2. Нажмите «Рассчитать», чтобы увидеть результат.
  3. Скопируйте или поделитесь результатом с помощью кнопки «Поделиться».

Об этом калькуляторе

Алгоритм Тонелли—Шенкса находит квадратный корень по модулю — значение r, такое что r² ≡ n (mod p), — для заданного числа n и нечётного простого модуля p, что является одной из фундаментальных операций вычислительной теории чисел. Перед запуском основного алгоритма он проверяет критерий Эйлера: n является квадратичным вычетом по модулю p (то есть квадратный корень вообще существует) тогда и только тогда, когда n^((p−1)/2) ≡ 1 (mod p). Когда p ≡ 3 (mod 4), у квадратного корня есть прямой короткий путь в замкнутом виде, но алгоритм Тонелли—Шенкса нужен для более трудного общего случая p ≡ 1 (mod 4), в котором повторное возведение в квадрат относительно квадратичного невычета используется, чтобы по одному отделять множители 2 от p−1.

Эта операция лежит в основе практической криптографии — прежде всего при восстановлении точки эллиптической кривой по её x-координате в сжатых форматах открытых ключей, используемых в ECDSA и Bitcoin, где y-координату нужно восстановить как квадратный корень по модулю из значения, полученного из уравнения кривой.

Была ли эта страница полезной?

Можно выбрать до 3 реакций.

Комментарии

  • Оставьте первый комментарий.

Популярные калькуляторы

Все калькуляторы