Як знайти первісну від кореня
Математика - складна і всеосяжна наука. Не знаючи формули, не можна вирішити просту задачу по темі. Що вже говорити про такі випадки, коли для вирішення завдання потрібно щось більше, ніж просто вивести одну формулу і підставити наявні значення. До таких належить знаходження первісної від кореня.
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).
Статті за темою "Як знайти первісну від кореня"
Оцініть, будь ласка статтю