Главная Войти О сайте

Как найти первообразную от корня

Как найти первообразную  от корня

Содержание:
  1. Нахождение первообразной от корня
  2. Понятие первообразного корня
  3. Эффективные алгоритмы
  4. Упрощение задачи
  5. Алгоритм нахождения первообразного корня
  6. Доказательство эффективности алгоритма
  7. Скорость роста первообразных корней

Нахождение первообразной от корня

Математика – сложная и всеобъемлющая наука. Не зная формулы, нельзя решить простую задачу по теме. Что уж говорить о таких случаях, когда для решения задачи нужно нечто большее, чем просто вывести одну формулу и подставить имеющиеся значения. К таковым относится нахождение первообразной от корня.

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

Стоит уточнить, что здесь имеется в виду нахождение первообразного корня, коим по модулю 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^6⁡n).


CompleteRepair.Ru