E018. Первообразные корни

Источник: e-maxx.ru/algo, страница PDF 49.

정의

Первообразным корнем по модулю

(primitive root modulo

) называется такое number

, что все его степени по модулю

пробегают по всем числам, взаимно простым с

. Математически это формулируется таким образом: если

является первообразным корнем по модулю

, то для любого целого

такого, что

, найдётся

такое целое

, что

.

В частности, для случая простого

степени первообразного корня пробегают по всем числам от

до

.

Существование

Первообразный корень по модулю

существует тогда и только тогда, когда

является либо степенью

нечётного простого, либо удвоенной степенью простого, а также в случаях

,

,

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

Связь с функцией Эйлера

Пусть

- первообразный корень по модулю

. Тогда можно показать, что наименьшее number

, для

которого

(т.е.

— показатель

(multiplicative order)), равно

. Более того, верно и

обратное, и этот факт будет использован нами ниже в 알고리즘е нахождения первообразного корня.

Кроме того, если по модулю

есть хотя бы один первообразный корень, то всего их

(т.к. циклическая группа

с

elementами имеет

генераторов).

알고리즘 нахождения первообразного корня

Наивный 알고리즘 потребует для каждого тестируемого значения

времени, чтобы вычислить все его степени

и проверить, что они все различны. Это слишком медленный 알고리즘, ниже мы с помощью нескольких известных теорем из теории чисел получим более быстрый 알고리즘.

Выше была приведена теорема о том, что если наименьшее number

, для которого

(т.е.

— показатель

), равно

, то

— первообразный корень. Так как для любого числа

выполняется теорема

Эйлера (

), то чтобы проверить, что

первообразный корень, достаточно проверить, что

для всех чисел

, меньших

, выполнялось

. Однако пока это слишком медленный 알고리즘. Из теоремы Лагранжа следует, что показатель любого числа по модулю

является делителем

. Таким

образом, достаточно проверить, что для всех собственных делителей

выполняется

. Это уже значительно более быстрый 알고리즘, однако можно пойти ещё дальше.

Факторизуем number

. Докажем, что в предыдущем 알고리즘е достаточно рассматривать в

качестве

лишь числа вида

. Действительно, пусть

— произвольный собственный делитель

.

Тогда, очевидно, найдётся такое

, что

, т.е.

. Однако, если бы

, то

мы получили бы:

т.е. всё равно среди чисел вида

нашлось бы то, для которого 문제 설명 не выполнилось, что и требовалось доказать. Таким образом, 알고리즘 нахождения первообразного корня такой. Находим

, факторизуем его. Теперь

перебираем все числа

, и для каждого считаем все величины

. Если для текущего

все эти числа оказались отличными от

, то это

и является искомым первообразным корнем.

실행 시간 알고리즘а (считая, что у числа

имеется

делителей, а возведение в

степень выполняется 알고리즘ом Бинарного возведения в степень, т.е. за

)

равно

плюс время факторизации числа

, где

— результат, т.е. значение искомого первообразного корня.

Про скорость роста первообразных корней с ростом

известны лишь приблизительные оценки. Известно,

что первообразные корни — сравнительно небольшие величины. Одна из известных оценок — оценка Шупа (Shoup), что, в предположении истинности гипотезы Римана, первообразный корень есть .

구현

Функция powmod() выполняет Binary exponentiation по модулю, а функция generator (int p) -

находит первообразный корень по простому модулю

(факторизация числа

здесь осуществлена

простейшим 알고리즘ом за

). Чтобы адаптировать эту функцию для произвольных

, достаточно

добавить вычисление функции Эйлера в переменной phi.

int powmod (int a, int b, int p) {

int res = 1;

while (b)

if (b & 1)

res = int (res * 1ll * a % p), --b;

else

a = int (a * 1ll * a % p), b >>= 1;

return res;

}

int generator (int p) {

vector<int> fact;

int phi = p-1,  n = phi;

for (int i=2; i*i<=n; ++i)

if (n % i == 0) {

fact.push_back (i);

while (n % i == 0)

n /= i;

}

if (n > 1)

fact.push_back (n);

for (int res=2; res<=p; ++res) {

bool ok = true;

for (size_t i=0; i<fact.size() && ok; ++i)

ok &= powmod (res, phi / fact[i], p) != 1;

if (ok)  return res;

}

return -1;

}