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

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

Калькулятор первообразного корня находит все первообразные корни для заданного модуля n — целые числа g, чьи степени \(g^1, g^2, \ldots, g^{\varphi(n)}\) порождают каждый элемент мультипликативной группы \((\mathbb{Z}/n\mathbb{Z})^*\). Введите любое положительное целое число, чтобы мгновенно увидеть все первообразные корни, функцию Эйлера \(\varphi(n)\), интерактивную визуализацию циклической группы, таблицу степеней и пошаговую проверку наименьшего первообразного корня.

Применение первообразных корней

Основные концепции и формулы

Понимание первообразных корней

Первообразный корень по модулю n — это целое число g такое, что \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) равно множеству всех целых чисел от 1 до n−1, которые взаимно просты с n. В терминах теории групп, g является генератором (порождающим элементом) циклической мультипликативной группы \((\mathbb{Z}/n\mathbb{Z})^*\). Например, 3 является первообразным корнем по модулю 7, потому что степени 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) дают каждый элемент множества {1, 2, 3, 4, 5, 6}.

Когда существуют первообразные корни?

Классический результат теории чисел (доказанный Гауссом) утверждает, что первообразные корни по модулю n существуют тогда и только тогда, когда n является одним из чисел: 1, 2, 4, p^k или 2p^k, где p — нечетное простое число и k ≥ 1. Для других значений n группа \((\mathbb{Z}/n\mathbb{Z})^*\) не является циклической — она распадается в прямое произведение циклических групп согласно Китайской теореме об остатках — поэтому ни один элемент не может породить всю группу. Например, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) не имеет первообразного корня.

Как эффективно находить первообразные корни

Стандартный алгоритм работает в две фазы. Фаза 1: поиск наименьшего первообразного корня путем перебора. Для каждого кандидата g, начиная с 2, вычисляется \(g^{\varphi(n)/p} \bmod n\) для каждого простого делителя p числа \(\varphi(n)\). Если ни один из этих результатов не равен 1, то g является первообразным корнем. На практике наименьший первообразный корень обычно невелик — предполагается, что он составляет \(O(n^\epsilon)\) для любого \(\epsilon > 0\). Фаза 2: как только известен один первообразный корень g, все остальные первообразные корни вычисляются как \(g^k \bmod n\), где \(\gcd(k, \varphi(n)) = 1\), что дает ровно \(\varphi(\varphi(n))\) первообразных корней в общей сложности.

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

1. Введите модуль n: Введите положительное целое число в поле ввода или нажмите одну из кнопок быстрого примера для автоматического заполнения.
2. Нажмите Найти первообразные корни: Нажмите кнопку, чтобы вычислить все первообразные корни по модулю n.
3. Ознакомьтесь с результатами: Посмотрите количество, полный список первообразных корней, значение функции Эйлера, порядок группы и информацию о том, существуют ли первообразные корни для вашего n.
4. Изучите визуализацию: Для n ≤ 100 интерактивное колесо циклической группы показывает, как каждый первообразный корень порождает всю группу через свои степени. Нажмите на любой чип корня, чтобы увидеть анимацию его цикла на колесе.
5. Изучите таблицу степеней: Сетка показывает g^k mod n для k = 1, 2, …, φ(n), при этом первообразные корни и единичный элемент выделены разными цветами.

Первообразные корни в криптографии

Первообразные корни играют центральную роль в современной криптографии. В обмене ключами Диффи-Хеллмана две стороны договариваются о большом простом числе p и генераторе подгруппы большого простого порядка q, где q делит p−1, затем обмениваются открытыми ключами g^a mod p и g^b mod p. Общий секрет g^ab mod p практически невозможно определить злоумышленнику, поскольку вычисление дискретных логарифмов в больших циклических подгруппах считается трудной задачей. Аналогично, шифрование Эль-Гамаля и алгоритм цифровой подписи (DSA) полагаются на сложность задачи дискретного логарифмирования в этих подгруппах.

FAQ

Продвинутые математические операции:

• Калькулятор матрицы смежности Новый
• Антилогарифмический Калькулятор
• Калькулятор бета-функции
• Калькулятор биномиального коэффициента
• Калькулятор биномиального распределения
• Побитовый калькулятор Популярное
• Упроститель Булевой Алгебры Новый
• Калькулятор центральной предельной теоремы
• Калькулятор китайской теоремы об остатках
• Комбинированный калькулятор
• Калькулятор дополнительной функции ошибки
• Калькулятор комплексных чисел Популярное
• Калькулятор цепных дробей
• Калькулятор беспорядков (субфакториал)
• Калькулятор кратчайшего пути Дейкстры
• Калькулятор Энтропии
• Калькулятор функции ошибки
• Калькулятор функции Эйлера
• Калькулятор экспоненциального распада
• Калькулятор экспоненциального роста: высокая точность
• Калькулятор экспоненциального интеграла
• Калькулятор показателей (высокая точность)
• Калькулятор расширенного алгоритма Евклида
• Калькулятор факториала Популярное
• Калькулятор гамма-функции
• Калькулятор золотого сечения
• Калькулятор раскраски графов Новый
• Валидатор последовательности степеней графа
• Калькулятор Порядка в Теории Групп Новый
• Калькулятор полураспада
• Проверка Гамильтонова Пути Новый
• Калькулятор формулы включений-исключений Новый
• Решатель Карты Карно (K-Map) Популярное
• Решатель Линейного Программирования Новый
• Калькулятор стационарного распределения цепи Маркова
• Калькулятор минимального остовного дерева
• Калькулятор Модульного Возведения в Степень Новый
• Калькулятор модулярного мультипликативного обратного
• Калькулятор отрицательного биномиального распределения Новый
• Калькулятор сетевого потока (Максимальный поток) Новый
• Калькулятор процентного роста Популярное
• Калькулятор перестановок
• Калькулятор перестановок с повторениями Новый
• Калькулятор принципа голубятни
• Проверка планарного графа Новый
• Калькулятор распределения Пуассона
• Калькулятор корней многочленов с подробными шагами
• Калькулятор первообразного корня
• Калькулятор вероятности
• Калькулятор распределения вероятностей
• Калькулятор пропорций
• Калькулятор квадратичных формул
• Калькулятор Колец и Полей Новый
• Калькулятор округления Новый
• Научный Калькулятор
• Калькулятор экспоненциальной записи
• Калькулятор теории множеств Популярное
• Калькулятор значащих цифр Популярное
• Решатель задачи о стабильных браках Новый
• Калькулятор чисел Стирлинга
• Калькулятор суммы кубов
• Калькулятор суммы последовательных чисел
• Калькулятор суммы квадратов
• Калькулятор топологической сортировки Новый
• Решатель задачи коммивояжёра (TSP) Новый
• Генератор таблицы истинности
• Генератор диаграммы Венна (3 множества)