Анхдагч язгуур¶

Тодорхойлолт¶

Модулийн арифметикт $n$-тэй харилцан анхны тоо бүр нь $n$ модулиар $g$-ийн зэрэгтэй congruence байвал $g$ тоог n модулиар анхдагч язгуур гэж нэрлэдэг. Математикийн хувьд $g$ нь n модулиар анхдагч язгуур байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь $\gcd(a, n) = 1$ байх дурын бүхэл тоо $a$-гийн хувьд дараах нөхцөлийг хангах бүхэл тоо $k$ оршин байх явдал юм:

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

Тэгвэл $k$-г $n$ модулиар $g$ суурьт $a$-гийн индекс эсвэл дискрет логарифм гэж нэрлэнэ. $g$-г мөн $n$ модулиар бүхэл тоонуудын мультипликатив бүлгийн үүсгэгч гэж нэрлэдэг.

Тухайлбал $n$ анхны байх тохиолдолд анхдагч язгуурын зэргүүд $1$-ээс $n-1$ хүртэлх бүх тоог дайран өнгөрнө.

Оршин байх¶

$n$ модулиар анхдагч язгуур оршин байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь:

$n$ нь 1, 2, 4, эсвэл
$n$ нь сондгой анхны тооны зэрэг $(n = p^k)$, эсвэл
$n$ нь сондгой анхны тооны зэргийн хоёр дахин $(n = 2 \cdot p^k)$ байх явдал юм.

Энэ теоремыг Гаусс 1801 онд баталсан.

Эйлерийн функцтэй холбоо¶

$g$ нь $n$ модулиар анхдагч язгуур байг. Тэгвэл $g^k \equiv 1 \pmod n$ байх хамгийн бага тоо $k$ нь $\phi (n)$-тэй тэнцүү болохыг харуулж болно. Түүнчлэн урвуу нь ч мөн үнэн бөгөөд энэ өгүүлэлд анхдагч язгуур олоход энэ баримтыг ашиглана.

Цаашилбал $n$ модулиар анхдагч язгуур байгаа бол тэдгээрийн тоо $\phi (\phi (n) )$-тэй тэнцүү байна.

Анхдагч язгуур олох алгоритм¶

Энгийн алгоритм бол $[1, n-1]$ муж дахь бүх тоог авч үзэх явдал юм. Дараа нь тус бүрийн бүх зэргийг тооцоолж, тэдгээр нь бүгд өөр эсэхийг харах замаар анхдагч язгуур эсэхийг шалгана. Энэ алгоритм $O(g \cdot n)$ complexity-тэй бөгөөд хэтэрхий удаан байх болно. Энэ хэсэгт бид сайн мэдэгдсэн хэд хэдэн теорем ашиглан илүү хурдан алгоритмыг санал болгоно.

Өмнөх хэсгээс бид $g^k \equiv 1 \pmod n$ байх хамгийн бага тоо $k$ нь $\phi (n)$ бол $g$ нь анхдагч язгуур гэдгийг мэднэ. $n$-тэй харилцан анхны дурын тоо $a$-гийн хувьд Эйлерийн теоремоос $a ^ { \phi (n) } \equiv 1 \pmod n$ гэдгийг мэддэг тул $g$ анхдагч язгуур эсэхийг шалгахын тулд $\phi (n)$-ээс бага бүх $d$-ийн хувьд $g^d \not \equiv 1 \pmod n$ болохыг шалгахад хангалттай. Гэвч энэ алгоритм одоо ч хэтэрхий удаан.

Лагранжийн теоремоос бид $n$ модулиар дурын тооны 1-ийн индекс нь $\phi (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}$ гэж үржигдэхүүнд задал. Өмнөх алгоритмд зөвхөн $\frac { \phi (n) } {p_j}$ хэлбэртэй $d$-ийн утгуудыг авч үзэхэд хангалттай гэдгийг батлая. Үнэндээ $d$ нь $\phi (n)$-ийн дурын жинхэнэ хуваагч байг. Тэгвэл мэдээж $d \mid \frac { \phi (n) } {p_j}$, өөрөөр хэлбэл $d \cdot k = \frac { \phi (n) } {p_j}$ байх ийм $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)$ хуваагчтай гэж үзвэл).

Шоуп (1990, 1992) ерөнхийлсөн Риманы таамаглал-ыг үнэн гэж үзвэл $g$ нь $O(\log^6 p)$ болохыг баталсан.

Implementation¶

The following code assumes that the modulo p is a prime number. To make it works for any value of p, we must add calculation of $\phi (p)$.

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