Как найти первообразную от корня
- Нахождение первообразной от корня
- Понятие первообразного корня
- Эффективные алгоритмы
- Упрощение задачи
- Алгоритм нахождения первообразного корня
- Доказательство эффективности алгоритма
- Скорость роста первообразных корней
Нахождение первообразной от корня
Математика – сложная и всеобъемлющая наука. Не зная формулы, нельзя решить простую задачу по теме. Что уж говорить о таких случаях, когда для решения задачи нужно нечто большее, чем просто вывести одну формулу и подставить имеющиеся значения. К таковым относится нахождение первообразной от корня.
Понятие первообразного корня
Стоит уточнить, что здесь имеется в виду нахождение первообразного корня, коим по модулю n называется число g – такое, что все степени этого числа по модулю n проходятся по всем взаимно простым с n числам. Математически это можно выразить так: если g – первообразный корень по модулю n, то для любого целого числа, такого, что gcd(a,n) = 1, найдется такое число k, что g^k ≡ a (mod n).
Эффективные алгоритмы
В предыдущем шаге была приведена теорема, которая показывает, что если наименьшее число k, для которого g^k ≡ 1 (mod n), равняется Φ(n), то g – это первообразный корень. Отсюда видно, что k является показателем g. Для любого a выполняется теорема Эйлера – a^(Φ(n)) ≡ 1 (mod n) – поэтому, чтобы проверить, что g является первообразным корнем, достаточно убедиться, что для всех меньших Φ(n) чисел d выполняется g^d ≢ 1 (mod n). Однако этот алгоритм довольно медленный.
Упрощение задачи
Из теоремы Лагранжа можно сделать вывод, что показатель любого из чисел по модулю n – это делитель Φ(n). Это упрощает задачу. Достаточно убедиться, что для всех собственных делителей d | Φ(n) выполняется g^d ≢ 1 (mod n). Этот алгоритм уже намного быстрее предыдущего.
Алгоритм нахождения первообразного корня
Факторизуйте число Φ(n) = p_1^(a_1 ) … p_s^(a_s ). Докажите, что в алгоритме, описанном в предыдущем шаге, в качестве d достаточно рассматривать лишь числа следующего вида: Φ(n) / p_i . Действительно, пускай d – это произвольный собственный делитель Φ(n). Тогда, очевидно, найдется такое j, что d | Φ(n) / p_j , то есть d*k = Φ(n) / p_j.
Доказательство эффективности алгоритма
Но если бы g^d ≡ 1 (mod n), то у нас вышло бы g^(Φ(n) / p_j) ≡ g^(d * k) ≡ (g^d )^k ≡ 1^k ≡ 1 (mod n). То есть получается, что среди чисел вида Φ(n) / p_j нашлось бы такое, для которого не выполнилось бы условие, что, собственно, и требовалось доказать.
Алгоритм нахождения первообразного корня, таким образом, выглядеть будет следующим образом. Сначала находится Φ(n), затем оно факторизуется. После перебираются все числа g = 1 … n, и для каждого из них считаются все величины Φ(n) / p_i (mod n). В случае если для текущего g эти все числа являются отличными от единицы, это g и будет искомым первообразным корнем.
Скорость роста первообразных корней
Что касается скорости роста первообразных корней с ростом n, здесь известны только приблизительные оценки. Первообразные корни, как известно – величины сравнительно небольшие. Одной из известных оценок является оценка Шупа (Shoup). В ней говорится, что если гипотеза Римана истинна, первообразным корнем будет O(log^6n).
