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

Найдите все первообразные корни для заданного модуля n — образующие мультипликативной группы (Z/nZ)*. Введите любое целое положительное число, чтобы получить первообразные корни, функцию Эйлера, визуализацию циклической группы и пошаговую проверку с таблицами степеней.

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

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

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

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

🔐

Диффи-Хеллман

Протокол обмена ключами использует первообразные корни в качестве генераторов

🔏

Шифрование Эль-Гамаля

Криптосистема с открытым ключом, основанная на дискретных логарифмах

✍

Цифровые подписи

Подписи DSA и Шнорра опираются на генераторы циклических групп

🎲

Псевдослучайные числа

Линейные конгруэнтные генераторы используют свойства первообразных корней

📡

Корректирующие коды

Коды Рида-Соломона и БЧХ используют генераторы конечных полей

🧮

Теория чисел

Исчисление индексов, квадратичные вычеты и задачи дискретного логарифмирования

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

Концепция	Формула / Определение	Описание
Первообразный корень	\(\text{ord}_n(g) = \varphi(n)\)	Целое число g, чей порядок по модулю n равен функции Эйлера
Функция Эйлера	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Количество целых чисел в [1, n], взаимно простых с n
Критерий существования	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Первообразные корни существуют только для этих форм (p — нечетное простое)
Количество корней	\(\varphi(\varphi(n))\)	Количество первообразных корней, если они существуют
Тест первообразного корня	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) для всех простых \(p \| \varphi(n)\)	Достаточное условие: проверка только для простых делителей φ(n)
Генерация всех корней	\(g^k \bmod n\) где \(\gcd(k, \varphi(n)) = 1\)	Как только найден один корень g, за ним следуют все остальные

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

Первообразный корень по модулю 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))\) первообразных корней в общей сложности.

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

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

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

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

FAQ

Что такое первообразный корень по модулю n?

Первообразный корень по модулю n — это такое целое число g, что степени g¹, g², …, g^φ(n) по модулю n дают каждое целое число, взаимно простое с n, ровно один раз. Эквивалентно, g имеет мультипликативный порядок, равный φ(n), что означает, что g порождает всю мультипликативную группу (Z/nZ)*.

Для каких значений n существуют первообразные корни?

Первообразные корни существуют тогда и только тогда, когда n равно 1, 2, 4, p^k или 2p^k, где p — нечетное простое число, а k — положительное целое число. Например, n = 7 (простое), n = 9 (3²) и n = 14 (2 × 7) имеют первообразные корни, а n = 8, n = 12 и n = 15 — нет.

Сколько первообразных корней у числа n?

Если у числа n есть первообразные корни, то их количество по модулю n равно φ(φ(n)), где φ — функция Эйлера. Например, n = 7 имеет φ(φ(7)) = φ(6) = 2 первообразных корня, которыми являются 3 и 5.

Как найти первообразные корни?

Чтобы найти первообразные корни n: сначала вычислите φ(n) и разложите его на множители. Затем для каждого кандидата g, взаимно простого с n, проверьте, что g^(φ(n)/p) не сравнимо с 1 по модулю n для каждого простого делителя p числа φ(n). Если все проверки пройдены, g является первообразным корнем. Все остальные корни можно найти как g^k mod n, где gcd(k, φ(n)) = 1.

Почему первообразные корни важны в криптографии?

Первообразные корни лежат в основе обмена ключами Диффи-Хеллмана, шифрования Эль-Гамаля и алгоритмов цифровой подписи. Они гарантируют сложность задачи дискретного логарифмирования, что является основой безопасности этих криптографических протоколов. Первообразный корень порождает все элементы группы, максимизируя пространство поиска для злоумышленников.

Ссылайтесь на этот контент, страницу или инструмент так:

"Калькулятор первообразного корня" на сайте https://ru.miniWebtool.com/калькулятор-первообразного-корня/ от MiniWebtool, https://MiniWebtool.com/

командой miniwebtool. Обновлено: 2026-04-16

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.