Як знайти первообразную від кореня.

Математика - складна і всеосяжна наука. Не знаючи формули, не можна вирішити просту задачу по темі. Що вже говорити про такі випадки, коли для вирішення завдання потрібно щось більше, ніж просто вивести одну формулу і підставити наявні значення. До таких відноситься знаходження первообразной від кореня.
Інструкція
1
Варто уточнити, що тут мається на увазі знаходження первообразного кореня, яким по модулю n називається число g - таке, що всі ступені цього числа по модулю n проходяться по всіх взаємно простим з n числам. Математично це можна виразити так: якщо g - первісний корінь по модулю n, то для будь-якого цілого числа, такого, що gcd (a, n) = 1, знайдеться таке число k, що g ^ k? a (mod n).
2
В попередньому кроці була приведена теорема, яка показує, що якщо найменше число k, для якого g ^ k? 1 (mod n), дорівнює? (N), то g - це первісний корінь. Звідси видно, що k є показником g. Для будь-якого a виконується теорема Ейлера - a ^ (? (N))? 1 (mod n) - тому, щоб перевірити, що g є первісним коренем, досить переконатися, що для всіх менших? (N) чисел d виконується g ^ d? 1 (mod n). Однак цей алгоритм досить повільний.
3
З теореми Лагранжа можна зробити висновок, що показник будь-якого з чисел по модулю n - це дільник? (N). Це спрощує завдання. Досить переконатися, що для всіх власних дільників d |? (N) виконується g ^ d? 1 (mod n). Цей алгоритм вже набагато швидше попереднього.
4
Факторізуйте число? (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.
5
Але якби g ^ d? 1 (mod n), то у нас вийшло б g ^ (? (N)/p_j)? g ^ (d * k)? (G ^ d) ^ k? 1 ^ k? 1 (mod n). Тобто виходить, що серед чисел виду? (N)/p_j знайшлося б таке, для якого не виповнилося би умову, що, власне, і потрібно було довести.
6
Алгоритм знаходження первообразного кореня, таким чином, виглядати буде наступним чином. Спочатку знаходиться? (N), потім воно факторізуется. Після перебираються всі числа g = 1 ... n, і для кожного з них вважаються всі величини? (N)/p_i (mod n). У разі якщо для поточного g ці всі числа є відмінними від одиниці, це g і буде шуканим первісним коренем.
7
Якщо вважати, що у числа? (N) є O (log? (N)), а зведення в ступінь виконується за допомогою алгоритму бінарного зведення в ступінь, тобто за O (log? N), можна дізнатися час роботи алгоритму. А одно воно O (Ans * log (n) * log? N) + t. Тут t - це час факторизації числа? (N), а Ans - це результат, тобто значення первообразного кореня.
Корисна порада
Що стосується швидкості росту первісних коренів із зростанням n, тут відомі тільки приблизні оцінки. Первісні корені, як відомо - величини порівняно невеликі. Однією з відомих оцінок є оцінка Шупа (Shoup). У ній говориться, що якщо гіпотеза Рімана істинна, первісним коренем буде O (log ^ 6? N).