Як знайти первісну від кореня
Відео 7 9 2011 Розстановки чисел по колу, або Первісні корені
Математика - складна і всеосяжна наука. Не знаючи формули, не можна вирішити просту задачу по темі. Що вже говорити про такі випадки, коли для вирішення завдання потрібно щось більше, ніж просто вивести одну формулу і підставити наявні значення. До таких належить знаходження первісної від кореня.
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) * logn) + t. Тут t - це час факторизации числа? (N), а Ans - це результат, тобто значення первісної кореня.
Корисна порада
Що стосується швидкості росту первісних коренів з ростом n, тут відомі тільки приблизні оцінки. Первісні корені, як відомо - величини порівняно невеликі. Однією з відомих оцінок є оцінка Шупа (Shoup). У ній говориться, що якщо гіпотеза Рімана істинна, первісним коренем буде O (log ^ 6n).
Поділися в соціальних мережах:
Схожі
- Як скласти модуль
- Як скласти корінь і число
- Як порівнювати коріння
- Що таке корінь
- Як обчислити корінь
- Як звести в корінь число
- Як винести з-під знака кореня
- Як знайти просте число
- Як обчислити квадратний корінь
- Як обчислити квадратний корінь числа
- Як вирішувати приклади з корінням
- Як обчислити квадратний корінь в excel
- Як винести число з кореня
- Як знайти корінь ступеня з числа
- Як знайти нод і нок чисел
- Як розкласти на прості множники числа
- Як внести число під корінь
- Як знаходити квадратний корінь
- Як обчислювати комплексні числа
- Що таке арифметичний квадратний корінь
- Як знайти квадратний корінь з числа