Модулийн үржүүлэлтийн урвуу¶

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

Бүхэл тоо $a$-гийн модулийн үржүүлэлтийн урвуу гэдэг нь $a \cdot x$ нь ямар нэг модуль $m$-ээр $1$-тэй зэрэгцүү байх бүхэл тоо $x$ юм. Албан ёсоор бичвэл: бид дараах нөхцөлийг хангах бүхэл тоо $x$-г олохыг хүсэж байна

$$a \cdot x \equiv 1 \mod m.$$

Бид $x$-г мөн зүгээр $a^{-1}$ гэж тэмдэглэнэ.

Модулийн урвуу үргэлж оршдоггүйг тэмдэглэх нь зүйтэй. Жишээ нь $m = 4$, $a = 2$ гэе. $m$ модулиар бүх боломжит утгыг шалгаснаар дээрх тэгшитгэлийг хангах $a^{-1}$-г олж чадахгүй нь тодорхой болно. Модулийн урвуу оршин байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь $a$ ба $m$ харилцан анхны байх ($\gcd(a, m) = 1$) явдал гэдгийг батлах боломжтой.

Энэ өгүүлэлд бид модулийн урвуу оршин байх тохиолдолд түүнийг олох хоёр арга, мөн бүх тооны модулийн урвууг шугаман хугацаанд олох нэг аргыг танилцуулна.

Өргөтгөсөн Евклидийн алгоритм ашиглан модулийн урвууг олох¶

Дараах тэгшитгэлийг ($x$ ба $y$ үл мэдэгдэхтэй) авч үзье:

$$a \cdot x + m \cdot y = 1$$

Энэ бол хоёр хувьсагчтай шугаман Диофантын тэгшитгэл юм. Холбогдсон өгүүлэлд үзүүлсний дагуу $\gcd(a, m) = 1$ үед тэгшитгэл шийдтэй байх ба түүнийг өргөтгөсөн Евклидийн алгоритм-аар олж болно. $\gcd(a, m) = 1$ нь мөн модулийн урвуу оршин байх нөхцөл болохыг анхаараарай.

Одоо хоёр талаас нь $m$ модулиар авбал $m \cdot y$-ээс салах бөгөөд тэгшитгэл дараах хэлбэртэй болно:

$$a \cdot x \equiv 1 \mod m$$

Тиймээс $a$-гийн модулийн урвуу нь $x$ болно.

The implementation is as follows:

int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
    cout << "No solution!";
}
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

Notice that the way we modify x. The resulting x from the extended Euclidean algorithm may be negative, so x % m might also be negative, and we first have to add m to make it positive.

Хоёртын зэрэгт дэвшүүлэлт ашиглан модулийн урвууг олох¶

Модулийн урвууг олох өөр нэг арга бол Эйлерийн теоремыг ашиглах явдал бөгөөд энэ теорем нь $a$ ба $m$ харилцан анхны бол дараах congruence үнэн гэж хэлдэг:

$$a^{\phi (m)} \equiv 1 \mod m$$

$\phi$ нь Эйлерийн функц юм. Дахин хэлэхэд $a$ ба $m$ харилцан анхны байх нь мөн модулийн урвуу оршин байх нөхцөл байсан.

Хэрэв $m$ анхны тоо бол энэ нь Фермагийн бага теорем болж хялбарчлагдана:

$$a^{m - 1} \equiv 1 \mod m$$

Дээрх тэгшитгэлүүдийн хоёр талыг $a^{-1}$-ээр үржүүлбэл бид дараахыг авна:

Дурын (гэхдээ харилцан анхны) модуль $m$-ийн хувьд: $a ^ {\phi (m) - 1} \equiv a ^{-1} \mod m$
Анхны модуль $m$-ийн хувьд: $a ^ {m - 2} \equiv a ^ {-1} \mod m$

Эдгээр үр дүнгээс бид $O(\log m)$ хугацаанд ажилладаг хоёртын зэрэгт дэвшүүлэлтийн алгоритм-ыг ашиглан модулийн урвууг амархан олж болно.

Хэдийгээр энэ арга өмнөх догол мөрөнд тайлбарласан аргаас ойлгоход хялбар боловч $m$ анхны тоо биш үед бид Эйлерийн фи функцийг тооцоолох шаардлагатай болох ба энэ нь $m$-г үржигдэхүүнд задлахыг шаарддаг тул маш хэцүү байж болно. Хэрэв $m$-ийн анхны үржигдэхүүнд задаргаа мэдэгдэж байвал энэ аргын complexity нь $O(\log m)$ болно.

Евклидийн хуваалт ашиглан анхны модулийн хувьд модулийн урвууг олох¶

Анхны модуль $m > a$ өгөгдсөн үед (эсвэл нэг алхмаар модуль авч багасгаж болно), Евклидийн хуваалт-ын дагуу

$$m = k \cdot a + r$$

энд $k = \left\lfloor \frac{m}{a} \right\rfloor$ ба $r = m \bmod a$, тэгвэл

$$ \begin{align*} & \implies & 0 & \equiv k \cdot a + r & \mod m \\ & \iff & r & \equiv -k \cdot a & \mod m \\ & \iff & r \cdot a^{-1} & \equiv -k & \mod m \\ & \iff & a^{-1} & \equiv -k \cdot r^{-1} & \mod m \end{align*} $$

Хэрэв $m$ анхны биш бол энэ үндэслэл биелэхгүй гэдгийг анхаараарай, учир нь $a^{-1}$ оршин байх нь ерөнхий тохиолдолд $r^{-1}$ оршин байхыг илэрхийлэхгүй. Үүнийг харахын тулд дээрх томьёогоор $12$ модулиар $5^{-1}$-г тооцоолохыг оролдъё. $5 \cdot 5 \equiv 1 \bmod 12$ тул бид $5$ гэсэн хариунд хүрэхийг хүсэж байна. Гэвч $12 = 2 \cdot 5 + 2$ бөгөөд бидэнд $k=2$ ба $r=2$ байх ба $2$ нь $12$ модулиар урвуугүй юм.

Гэхдээ модуль анхны бол $0 < a < m$ байх бүх $a$ нь $m$ модулиар урвуутай байх ба бид $m$-ийн хувьд $a$ тооны модулийн урвууг тооцоолох дараах рекурсив функцийг (C++ дээр) ашиглаж болно

int inv(int a) {
  return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
}

Энэ рекурсийн яг time complexity мэдэгдээгүй байна. Энэ нь $O(\frac{\log m}{\log\log m})$ ба $O(m^{\frac{1}{3} - \frac{2}{177} + \epsilon})$ хоёрын хооронд хаа нэгтээ байна. On the length of Pierce expansions-ийг үзнэ үү. Практикт энэ хэрэгжүүлэлт хурдан бөгөөд жишээ нь $10^9 + 7$ модулийн хувьд үргэлж 50-аас цөөн давталтад дуусна.

Энэ томьёог хэрэглэснээр бид $[1, m-1]$ муж дахь тоо бүрийн модулийн урвууг $O(m)$-д урьдчилан тооцоолж болно.

inv[1] = 1;
for(int a = 2; a < m; ++a)
    inv[a] = m - (long long)(m/a) * inv[m%a] % m;

$m$ модулиар тооны массивын модулийн урвууг олох¶

Бидэнд массив өгөгдсөн бөгөөд түүн дэх бүх тооны модулийн урвууг олохыг хүсэж байна гэж үзье (тэдгээр бүгд урвуутай). Тоо бүрийн урвууг тооцоолохын оронд бид бутархайг угтвар үржвэр (өөрийг нь оруулалгүй) ба дагавар үржвэр (өөрийг нь оруулалгүй)-ээр өргөтгөж, ердөө ганц урвуу тооцоолоход хүрч болно.

$$ \begin{align} x_i^{-1} &= \frac{1}{x_i} = \frac{\overbrace{x_1 \cdot x_2 \cdots x_{i-1}}^{\text{prefix}_{i-1}} \cdot ~1~ \cdot \overbrace{x_{i+1} \cdot x_{i+2} \cdots x_n}^{\text{suffix}_{i+1}}}{x_1 \cdot x_2 \cdots x_{i-1} \cdot x_i \cdot x_{i+1} \cdot x_{i+2} \cdots x_n} \\ &= \text{prefix}_{i-1} \cdot \text{suffix}_{i+1} \cdot \left(x_1 \cdot x_2 \cdots x_n\right)^{-1} \end{align} $$

In the code we can just make a prefix product array (exclude itself, start from the identity element), compute the modular inverse for the product of all numbers and then multiply it by the prefix product and suffix product (exclude itself). The suffix product is computed by iterating from the back to the front.

std::vector<int> invs(const std::vector<int> &a, int m) {
    int n = a.size();
    if (n == 0) return {};
    std::vector<int> b(n);
    int v = 1;
    for (int i = 0; i != n; ++i) {
        b[i] = v;
        v = static_cast<long long>(v) * a[i] % m;
    }
    int x, y;
    extended_euclidean(v, m, x, y);
    x = (x % m + m) % m;
    for (int i = n - 1; i >= 0; --i) {
        b[i] = static_cast<long long>(x) * b[i] % m;
        x = static_cast<long long>(x) * a[i] % m;
    }
    return b;
}