MAXimal

добавлено: 16 Jan 2009 0:58
редактировано: 20 Aug 2012 23:51

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

Определение

Первообразным корнем по модулю $n$ (primitive root modulo $n$ ) называется такое число $g$ , что все его степени по модулю $n$ пробегают по всем числам, взаимно простым с $n$ . Математически это формулируется таким образом: если $g$ является первообразным корнем по модулю $n$ , то для любого целого $a$ такого, что ${\rm gcd}(a,n)=1$ , найдётся такое целое $k$ , что $g^k \equiv a \pmod{n}$ .

В частности, для случая простого $n$ степени первообразного корня пробегают по всем числам от $1$ до $n-1$ .

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

Первообразный корень по модулю $n$ существует тогда и только тогда, когда $n$ является либо степенью нечётного простого, либо удвоенной степенью простого, а также в случаях $n=1$ , $n=2$ , $n=4$ .

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

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

Пусть $g$ - первообразный корень по модулю $n$ . Тогда можно показать, что наименьшее число $k$ , для которого $g^k \equiv 1 \pmod{n}$ (т.е. $k$ — показатель $g$ (multiplicative order)), равно $\phi(n)$ . Более того, верно и обратное, и этот факт будет использован нами ниже в алгоритме нахождения первообразного корня.

Кроме того, если по модулю $n$ есть хотя бы один первообразный корень, то всего их $\phi( \phi(n) )$ (т.к. циклическая группа с $k$ элементами имеет $\phi(k)$ генераторов).

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

Наивный алгоритм потребует для каждого тестируемого значения $g$ $O(n)$ времени, чтобы вычислить все его степени и проверить, что они все различны. Это слишком медленный алгоритм, ниже мы с помощью нескольких известных теорем из теории чисел получим более быстрый алгоритм.

Выше была приведена теорема о том, что если наименьшее число $k$ , для которого $g^k \equiv 1 \pmod{n}$ (т.е. $k$ — показатель $g$ ), равно $\phi(n)$ , то $g$ — первообразный корень. Так как для любого числа $a$ , взаимно простого с $n$ , выполняется теорема Эйлера ( $a^{\phi(n)} \equiv 1 \pmod{n}$ ), то чтобы проверить, что $g$ первообразный корень, достаточно проверить, что для всех чисел $d$ , меньших $\phi(n)$ , выполнялось $g^d \not\equiv 1 \pmod{n}$ . Однако пока это слишком медленный алгоритм.

Из теоремы Лагранжа следует, что показатель любого числа по модулю $n$ является делителем $\phi(n)$ . Таким образом, достаточно проверить, что для всех собственных делителей $d\ |\ \phi(n)$ выполняется $g^d \not\equiv 1 \pmod{n}$ . Это уже значительно более быстрый алгоритм, однако можно пойти ещё дальше.

Факторизуем число $\phi(n) = p_1^{a_1} \ldots p_s^{a_s}$ . Докажем, что в предыдущем алгоритме достаточно рассматривать в качестве $d$ лишь числа вида $\frac{ \phi(n) }{ p_i }$ . Действительно, пусть $d$ — произвольный собственный делитель $\phi(n)$ . Тогда, очевидно, найдётся такое $j$ , что $d\ |\ \frac{ \phi(n) }{ p_j }$ , т.е. $d \cdot k = \frac{ \phi(n) }{ p_j }$ . Однако, если бы $g^d \equiv 1 \pmod{n}$ , то мы получили бы:

$g^{\frac{ \phi(n) }{ p_j }} \equiv g^{d \cdot k} [...]$

т.е. всё равно среди чисел вида $\frac{ \phi(n) }{ p_i }$ нашлось бы то, для которого условие не выполнилось, что и требовалось доказать.

Таким образом, алгоритм нахождения первообразного корня такой. Находим $\phi(n)$ , факторизуем его. Теперь перебираем все числа $g = 1 \ldots n$ , и для каждого считаем все величины $g^{ \frac{ \phi(n) }{ p_i } } \pmod{n}$ . Если для текущего $g$ все эти числа оказались отличными от $1$ , то это $g$ и является искомым первообразным корнем.

Время работы алгоритма (считая, что у числа $\phi(n)$ имеется $O \left( \log \phi(n) \right)$ делителей, а возведение в степень выполняется алгоритмом Бинарного возведения в степень, т.е. за $O(\log n)$ ) равно $O \left( {\rm Ans} \cdot \log \phi(n) \cdot \log n \right)$ плюс время факторизации числа $\phi(n)$ , где $\rm Ans$ — результат, т.е. значение искомого первообразного корня.

Про скорость роста первообразных корней с ростом $n$ известны лишь приблизительные оценки. Известно, что первообразные корни — сравнительно небольшие величины. Одна из известных оценок — оценка Шупа (Shoup), что, в предположении истинности гипотезы Римана, первообразный корень есть $O (\log^6 n)$ .

Реализация

Функция powmod() выполняет бинарное возведение в степень по модулю, а функция generator (int p) - находит первообразный корень по простому модулю $p$ (факторизация числа $\phi(n)$ здесь осуществлена простейшим алгоритмом за $O( \sqrt{ \phi(n) } )$ ).

Чтобы адаптировать эту функцию для произвольных $p$ , достаточно добавить вычисление функции Эйлера в переменной $phi$ , а также отсеивать $res$ , не являющиеся взаимно простыми с $n$ .

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;
}