первісний корінь

визначення

Первісним коренем за модулем (primitive root modulo) називається таке число, що все його ступеня за модулем пробігають по всіх чисел, взаємно простим с. Математично це формулюється таким чином: якщо є первісним коренем за модулем, то для будь-якого цілого такого, що, знайдеться таке ціле, що.

Зокрема, для випадку простого ступеня первісної кореня пробігають по всіх чисел від до.

існування

Первісний корінь по модулю існує тоді і тільки тоді, коли є або ступенем непарного простого, або подвоєною ступенем простого, а також у випадках,,.

Ця теорема (яка була повністю доведена Гауссом в 1801 р) наводиться тут без доказу.

Зв'язок з функцією Ейлера

Нехай - первісний корінь по модулю. Тоді можна показати, що найменше число, для якого (тобто - показник (multiplicative order)), так само. Більш того, вірно і зворотне, і цей факт буде використаний нами нижче в алгоритмі знаходження первісної кореня.

Крім того, якщо по модулю є хоча б один первісний корінь, то всього їх (тому що циклічна група з елементами має генераторів).

Алгоритм знаходження первісної кореня

Наївний алгоритм вимагатиме для кожного тестованого значення часу, щоб обчислити всі його ступеня і перевірити, що вони все різні. Це занадто повільний алгоритм, нижче ми за допомогою декількох відомих теорем з теорії чисел отримаємо більш швидкий алгоритм.

Вище була наведена теорема про те, що якщо найменше число, для якого (тобто - показник), так само, то - первісний корінь. Так як для будь-якого числа, взаємно простого з, виконується теорема Ейлера (), то щоб перевірити, що первісний корінь, досить перевірити, що для всіх чисел, менших, виконувалося. Однак поки це занадто повільний алгоритм.

З теореми Лагранжа слід, що показник будь-якого числа по модулю є дільником. Таким чином, досить перевірити, що для всіх власних дільників виконується. Це вже значно швидший алгоритм, проте можна піти ще далі.

Факторізуем число. Доведемо, що в попередньому алгоритмі досить розглядати в якості лише числа виду. Дійсно, нехай - довільний власний дільник. Тоді, очевидно, знайдеться таке, що, тобто . Однак, якщо б, то ми отримали б:

тобто все одно серед чисел вигляду знайшлося б то, для якого умова не виповнилося, що й треба було довести.

Таким чином, алгоритм знаходження первісної кореня такої. Знаходимо, факторізуем його. Тепер перебираємо всі числа, і для кожного вважаємо все величини. Якщо для поточного всі ці числа виявилися відмінними від, то це і є шуканим первісним коренем.

Час роботи алгоритму (вважаючи, що у числа є подільників, а спорудження до рівня виконується алгоритмом бінарного зведення в ступінь. Тобто за) одно плюс час факторизации числа, де - результат, тобто значення шуканого первообразного кореня.

Про швидкість росту первісних коренів з ростом відомі лише приблизні оцінки. Відомо, що первісні коріння - порівняно невеликі величини. Одна з відомих оцінок - оцінка Шупа (Shoup), що, в припущенні істинності гіпотези Рімана, первісний корінь є.

Реалізація

Функція powmod () виконує бінарне зведення в ступінь по модулю, а функція generator (int p) - знаходить первісний корінь по простому модулю (факторизація числа тут здійснена найпростішим алгоритмом за).

Щоб адаптувати цю функцію для довільних, досить додати обчислення функції Ейлера в змінної, а також відсіювати, які не є взаємно простими с.