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

Означення

У модульній арифметиці число $g$ називають первісним коренем за модулем n, якщо кожне число, взаємно просте з $n$, конгруентне деякому степеню $g$ за модулем $n$. Математично, $g$ є первісним коренем за модулем n тоді й лише тоді, коли для будь-якого цілого $a$ такого, що $\gcd(a, n) = 1$, існує таке ціле $k$, що:

$g^k \equiv a \pmod n$.

Тоді $k$ називають індексом або дискретним логарифмом числа $a$ за основою $g$ за модулем $n$. Число $g$ також називають твірним елементом мультиплікативної групи цілих чисел за модулем $n$.

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

Існування

Первісний корінь за модулем $n$ існує тоді й лише тоді, коли:

• $n$ дорівнює 1, 2, 4, або
• $n$ є степенем непарного простого числа $(n = p^k)$, або
• $n$ є подвоєним степенем непарного простого числа $(n = 2 \cdot p^k)$.

Цю теорему довів Гаусс у 1801 році.

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

Нехай $g$ — первісний корінь за модулем $n$. Тоді можна показати, що найменше число $k$, для якого $g^k \equiv 1 \pmod n$, дорівнює $\phi (n)$. Більше того, обернене також справедливе, і саме цей факт ми використаємо в цій статті для пошуку первісного кореня.

Крім того, кількість первісних коренів за модулем $n$, якщо вони взагалі існують, дорівнює $\phi (\phi (n) )$.

Коли підходить цей алгоритм?

• Чи модуль $n$ має форму, за якої первісний корінь узагалі існує ($n \in \{1, 2, 4\}$, $n = p^k$ або $n = 2p^k$ для непарного простого $p$)? Інакше шукати нема чого.
• Чи можете ви розкласти на множники $\phi(n)$ — це потрібно, щоб перевіряти кандидатів лише за $d = \tfrac{\phi(n)}{p_j}$? (для самого розкладу → Факторизація)
• Чи задача справді потребує твірного мультиплікативної групи (наприклад, для дискретного логарифма чи дискретного кореня), а не просто степенів за модулем?

Алгоритм пошуку первісного кореня

Наївний алгоритм полягає в тому, щоб розглянути всі числа з відрізка $[1, n-1]$. А потім перевірити кожне з них, чи є воно первісним коренем, обчислюючи всі його степені, щоб переконатися, що вони всі різні. Цей алгоритм має складність $O(g \cdot n)$, що було б надто повільно. У цьому розділі ми пропонуємо швидший алгоритм, який використовує кілька добре відомих теорем.

З попереднього розділу ми знаємо, що якщо найменше число $k$, для якого $g^k \equiv 1 \pmod n$, дорівнює $\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 \mid \phi (n)$, що $g^d \not \equiv 1 \pmod n$. Це вже значно швидший алгоритм, але ми можемо зробити ще краще.

Розкладемо $\phi (n) = p_1 ^ {a_1} \cdots p_s ^ {a_s}$. Доведемо, що в попередньому алгоритмі достатньо розглядати лише ті значення $d$, які мають вигляд $\frac { \phi (n) } {p_j}$. Справді, нехай $d$ — будь-який власний дільник $\phi (n)$. Тоді, очевидно, існує таке $j$, що $d \mid \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} \equiv (g^d) ^k \equiv 1^k \equiv 1 \pmod n$.

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

Тепер у нас є повний алгоритм пошуку первісного кореня:

• Спочатку знаходимо $\phi (n)$ і розкладаємо його на множники.

• Потім перебираємо всі числа $g \in [1, n]$, і для кожного числа, щоб перевірити, чи є воно первісним коренем, робимо таке:

  • Обчислюємо всі $g ^ { \frac {\phi (n)} {p_i}} \pmod n$.
  • Якщо всі обчислені значення відмінні від $1$, то $g$ є первісним коренем.

  Час роботи цього алгоритму становить $O(Ans \cdot \log \phi (n) \cdot \log n)$ (припускаємо, що $\phi (n)$ має $\log \phi (n)$ дільників).

Шоуп (Shoup, 1990, 1992) довів, припускаючи узагальнену гіпотезу Рімана, що $g$ є $O(\log^6 p)$.

Реалізація

У наведеному нижче коді припускається, що модуль p є простим числом. Щоб він працював для будь-якого значення p, ми маємо додати обчислення $\phi (p)$.

C++

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

Python

def powmod(a: int, b: int, p: int) -> int:
    # піднесення до степеня за модулем; pow має вбудовану реалізацію
    return pow(a, b, p)


def generator(p: int) -> int:
    fact = []
    phi = p - 1
    n = phi
    # розкладаємо phi(p) = p - 1 на прості множники
    i = 2
    while i * i <= n:
        if n % i == 0:
            fact.append(i)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        fact.append(n)

    # перебираємо кандидатів і перевіряємо лише степені phi / p_i
    for res in range(2, p + 1):
        if all(powmod(res, phi // f, p) != 1 for f in fact):
            return res
    return -1

TypeScript

function powmod(a: number, b: number, p: number): number {
  // працюємо в BigInt, щоб уникнути переповнення при множенні
  let res = 1n;
  let base = BigInt(a) % BigInt(p);
  let exp = BigInt(b);
  const mod = BigInt(p);
  while (exp > 0n) {
    if (exp & 1n) res = (res * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return Number(res);
}

function generator(p: number): number {
  const fact: number[] = [];
  const phi = p - 1;
  let n = phi;
  // розкладаємо phi(p) = p - 1 на прості множники
  for (let i = 2; i * i <= n; ++i) {
    if (n % i === 0) {
      fact.push(i);
      while (n % i === 0) n = Math.floor(n / i);
    }
  }
  if (n > 1) fact.push(n);

  // перебираємо кандидатів і перевіряємо лише степені phi / p_i
  for (let res = 2; res <= p; ++res) {
    let ok = true;
    for (let i = 0; i < fact.length && ok; ++i) {
      ok = powmod(res, Math.floor(phi / fact[i]), p) !== 1;
    }
    if (ok) return res;
  }
  return -1;
}

Go

func powmod(a, b, p int) int {
	// множимо у int64, щоб уникнути переповнення
	res := int64(1)
	base := int64(a) % int64(p)
	mod := int64(p)
	for b > 0 {
		if b&1 == 1 {
			res = res * base % mod
		}
		base = base * base % mod
		b >>= 1
	}
	return int(res)
}

func generator(p int) int {
	var fact []int
	phi := p - 1
	n := phi
	// розкладаємо phi(p) = p - 1 на прості множники
	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fact = append(fact, i)
			for n%i == 0 {
				n /= i
			}
		}
	}
	if n > 1 {
		fact = append(fact, n)
	}

	// перебираємо кандидатів і перевіряємо лише степені phi / p_i
	for res := 2; res <= p; res++ {
		ok := true
		for i := 0; i < len(fact) && ok; i++ {
			ok = powmod(res, phi/fact[i], p) != 1
		}
		if ok {
			return res
		}
	}
	return -1
}

Відеоматеріали