Калькулятор первообразного корня

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

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

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

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

Число g является первообразным корнем по модулю n, если его степени — g¹, g², g³ и так далее — проходят по всем числам, взаимно простым с n, прежде чем начать повторяться, то есть наименьший показатель k, для которого g^k ≡ 1 (mod n), равен ровно φ(n), функции Эйлера. Иными словами, один первообразный корень порождает всю мультипликативную группу по модулю n. Первообразные корни существуют не для каждого модуля: классическая теория чисел (восходящая к Гауссу) показывает, что они существуют только когда n равно 1 (тривиально), 2, 4, степени нечётного простого числа или удвоенной степени нечётного простого числа.

Первообразные корни — рабочий инструмент криптографии, а не просто диковинка: обмен ключами Диффи–Хеллмана и криптосистема Эль-Гамаля опираются на сложность задачи дискретного логарифма в группе, порождённой первообразным корнем, а теоретико-числовые преобразования, применяемые в быстром точном умножении многочленов (важном для некоторых современных криптографических схем и схем исправления ошибок), также зависят от нахождения подходящих первообразных корней модуля.

Введите целый модуль n от 2 до 100 000, и этот калькулятор найдёт его наименьший первообразный корень вместе с φ(n) и числом первообразных корней. Если для этого n первообразного корня не существует, результата нет.

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

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

Комментарии

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

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

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