Как найти первообразную функции под корнем — Сайт, где вы сможете решить свои вопросы

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

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

Инструкция

Стоит уточнить, что здесь имеется в виду нахождение первообразного корня, коим по модулю 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) есть O (log Φ(n)), а возведение в степень выполняется при помощи алгоритма бинарного возведения в степень, то есть за O (log ⁡n), можно узнать время работы алгоритма. А равно оно O (Ans * log ⁡Φ(n) * log⁡n) + t. Здесь t – это время факторизации числа Φ(n), а Ans – это результат, то есть значение первообразного корня.

Полезный совет

Что касается скорости роста первообразных корней с ростом n, здесь известны только приблизительные оценки. Первообразные корни, как известно – величины сравнительно небольшие. Одной из известных оценок является оценка Шупа (Shoup). В ней говорится, что если гипотеза Римана истинна, первообразным корнем будет O(log^6⁡n).

Источники:

• первообразные корни