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

Математика - складна і всеосяжна наука. Не знаючи формули, не можна вирішити просту задачу по темі. Що вже говорити про такі випадки, коли для вирішення завдання потрібно щось більше, ніж просто вивести одну формулу і підставити наявні значення. До таких відноситься знаходження первообразной від кореня.

Інструкція

Варто уточнити, що тут мається на увазі знаходження первообразного кореня, яким по модулю 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 - це результат, тобто значення первообразного кореня.