Проверка квадратичных вычетов

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

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

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

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

Целое число a является квадратичным вычетом по простому модулю p, если существует такое x, что x² ≡ a (mod p), — иными словами, a является полным квадратом в модульной арифметике, даже если не является им среди обычных целых чисел. Критерий Эйлера позволяет быстро проверить это, не перебирая x напрямую: a является квадратичным вычетом по модулю p тогда и только тогда, когда a^((p−1)/2) ≡ 1 (mod p), и невычетом, если оно ≡ −1.

Результат обычно выражают через символ Лежандра (a/p), равный +1, −1 или 0. Калькулятор вычисляет его — это рутинный шаг в курсах теории чисел и криптографических алгоритмах: квадратичные вычеты напрямую встречаются в тестах простоты, в алгоритме Тонелли–Шенкса для вычисления квадратных корней по модулю и в некоторых конструкциях цифровых подписей и доказательств с нулевым разглашением.

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

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

Комментарии

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

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

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