Агуулгыг алгасах

Монтгомеригийн үржүүлэлт

Тооны онолын олон алгоритм, тухайлбал анхны тооны шалгуур эсвэл бүхэл тоог үржигдэхүүнд задлах, мөн криптографийн RSA зэрэг нь том тоогоор модуль авах олон үйлдэл шаарддаг. $x y \bmod{n}$ мэтийн үржүүлэлтийг ердийн алгоритмаар тооцоолоход нэлээд удаан байдаг, учир нь үржвэрээс $n$-г хэдэн удаа хасахыг мэдэхийн тулд хуваалт хийх шаардлагатай. Хуваалт бол үнэхээр өртөг өндөртэй үйлдэл, ялангуяа том тоотой ажиллах үед.

Монтгомеригийн (модулийн) үржүүлэлт нь ийм үржүүлэлтийг илүү хурдан тооцоолох боломж олгодог арга юм. Үржвэрийг хувааж, $n$-г олон удаа хасахын оронд энэ нь доод битүүдийг хураахын тулд $n$-ийн үржвэрүүдийг нэмээд, дараа нь доод битүүдийг зүгээр л хаядаг.

Монтгомеригийн илэрхийлэл

Гэвч Монтгомеригийн үржүүлэлт үнэгүй ирдэггүй. Алгоритм зөвхөн Монтгомеригийн огторгуйд ажилладаг. Мөн бид үржүүлж эхлэхийн өмнө тоонуудаа тэр огторгуй руу хувиргах хэрэгтэй.

Огторгуйн хувьд бидэнд $n$-тэй харилцан анхны, өөрөөр хэлбэл $\gcd(n, r) = 1$ байх эерэг бүхэл тоо $r \ge n$ хэрэгтэй. Практикт бид $r$-г үргэлж эерэг бүхэл тоо $m$-ийн хувьд $2^m$ гэж сонгодог, учир нь тэгвэл үржүүлэлт, хуваалт болон $r$ модулийн үйлдлүүдийг шилжүүлэлт болон бусад битийн үйлдлээр үр ашигтай хэрэгжүүлж болно. Тэгш тоог үржигдэхүүнд задлах хэцүү биш тул бараг бүх хэрэглээнд $n$ нь сондгой тоо байна. Тиймээс $2$-ын зэрэг бүр $n$-тэй харилцан анхны байх болно.

Монтгомеригийн огторгуй дахь тоо $x$-ийн төлөөлөгч $\bar{x}$-г дараах байдлаар тодорхойлно:

$$\bar{x} := x \cdot r \bmod n$$

Хувиргалт нь үнэндээ бидний оновчлохыг хүсэж буй яг тийм үржүүлэлт болохыг анхаараарай. Тиймээс энэ нь одоо ч өртөг өндөртэй үйлдэл хэвээр байна. Гэвч та тоог огторгуй руу ганц удаа хувиргахад л хангалттай. Монтгомеригийн огторгуйд орсны дараа та хүссэн хэмжээгээрээ олон үйлдлийг үр ашигтай хийж болно. Эцэст нь эцсийн үр дүнг буцаан хувиргана. Тиймээс та $n$ модулиар олон үйлдэл хийж байгаа цагт энэ нь асуудал болохгүй.

Монтгомеригийн огторгуй дотор та ихэнх үйлдлийг ердийнхөөрөө хийсээр байж болно. Та хоёр элемент нэмэх ($x \cdot r + y \cdot r \equiv (x + y) \cdot r \bmod n$), хасах, тэнцүү эсэхийг шалгах, тэр байтугай тооны $n$-тэй хамгийн их ерөнхий хуваагчийг тооцоолж болно ($\gcd(n, r) = 1$ тул). Бүгдийг ердийн алгоритмаар.

Гэвч үржүүлэлтийн хувьд энэ нь тийм биш.

Бид үр дүнг дараах байдлаар хүлээж байна:

$$\bar{x} * \bar{y} = \overline{x \cdot y} = (x \cdot y) \cdot r \bmod n.$$

Гэвч ердийн үржүүлэлт бидэнд дараахыг өгнө:

$$\bar{x} \cdot \bar{y} = (x \cdot y) \cdot r \cdot r \bmod n.$$

Тиймээс Монтгомеригийн огторгуй дахь үржүүлэлтийг дараах байдлаар тодорхойлно:

$$\bar{x} * \bar{y} := \bar{x} \cdot \bar{y} \cdot r^{-1} \bmod n.$$

Монтгомеригийн хураалт

Монтгомеригийн огторгуй дахь хоёр тооны үржүүлэлт нь $x \cdot r^{-1} \bmod n$-г үр ашигтай тооцоолохыг шаарддаг. Энэ үйлдлийг Монтгомеригийн хураалт гэж нэрлэдэг бөгөөд мөн REDC алгоритм гэж нэрлэгддэг.

$\gcd(n, r) = 1$ тул бид $0 < r^{-1}, n^{\prime} < n$ байх, дараах нөхцөлийг хангах $r^{-1}$ ба $n^{\prime}$ гэсэн хоёр тоо байдгийг мэднэ

$$r \cdot r^{-1} + n \cdot n^{\prime} = 1.$$

$r^{-1}$ ба $n^{\prime}$ хоёуланг Өргөтгөсөн Евклидийн алгоритм ашиглан тооцоолж болно.

Энэ адилтгалыг ашиглан бид $x \cdot r^{-1}$-г дараах байдлаар бичиж болно:

$$\begin{aligned} x \cdot r^{-1} &= x \cdot r \cdot r^{-1} / r = x \cdot (-n \cdot n^{\prime} + 1) / r \\ &= (-x \cdot n \cdot n^{\prime} + x) / r \equiv (-x \cdot n \cdot n^{\prime} + l \cdot r \cdot n + x) / r \bmod n\\ &\equiv ((-x \cdot n^{\prime} + l \cdot r) \cdot n + x) / r \bmod n \end{aligned}$$

Эдгээр эквивалент нь дурын бүхэл тоо $l$-ийн хувьд биелнэ. Энэ нь бид $x \cdot n^{\prime}$ дээр $r$-ийн дурын үржвэрийг нэмж эсвэл хасаж болно, өөрөөр хэлбэл $q := x \cdot n^{\prime}$-г $r$ модулиар тооцоолж болно гэсэн үг.

Эндээс $x \cdot r^{-1} \bmod n$-г тооцоолох дараах алгоритм гарна:

function reduce(x):
    q = (x mod r) * n' mod r
    a = (x - q * n) / r
    if a < 0:
        a += n
    return a

$x < n \cdot n < r \cdot n$ ($x$ нь үржүүлэлтийн үржвэр байсан ч) ба $q \cdot n < r \cdot n$ тул бид $-n < (x - q \cdot n) / r < n$ гэдгийг мэднэ. Тиймээс эцсийн модулийн үйлдлийг ганц шалгалт ба нэг нэмэлтээр хэрэгжүүлнэ.

Бидний харж байгаагаар Монтгомеригийн хураалтыг ямар ч хүнд модулийн үйлдэлгүйгээр хийж болно. Хэрэв бид $r$-г $2$-ын зэрэг гэж сонговол алгоритм дахь модулийн үйлдэл ба хуваалтыг битмаск болон шилжүүлэлт ашиглан тооцоолж болно.

Монтгомеригийн хураалтын хоёр дахь хэрэглээ нь тоог Монтгомеригийн огторгуйгаас ердийн огторгуй руу буцаан шилжүүлэх явдал юм.

Хурдан урвуугийн арга

$n^{\prime} := n^{-1} \bmod r$ урвууг үр ашигтай тооцоолохын тулд бид дараах аргыг (Ньютоны аргаас санаа авсан) ашиглаж болно:

$$a \cdot x \equiv 1 \bmod 2^k \Longrightarrow a \cdot x \cdot (2 - a \cdot x) \equiv 1 \bmod 2^{2k}$$

Үүнийг амархан батлаж болно. Хэрэв бидэнд $a \cdot x = 1 + m \cdot 2^k$ байвал:

$$\begin{aligned} a \cdot x \cdot (2 - a \cdot x) &= 2 \cdot a \cdot x - (a \cdot x)^2 \\ &= 2 \cdot (1 + m \cdot 2^k) - (1 + m \cdot 2^k)^2 \\ &= 2 + 2 \cdot m \cdot 2^k - 1 - 2 \cdot m \cdot 2^k - m^2 \cdot 2^{2k} \\ &= 1 - m^2 \cdot 2^{2k} \\ &\equiv 1 \bmod 2^{2k}. \end{aligned}$$

Энэ нь бид $2^1$ модулиар $a$-гийн урвуу болгон $x = 1$-ээс эхэлж, аргыг хэдэн удаа хэрэглэвэл давталт бүрт $x$-ийн зөв битийн тоог хоёр дахин нэмэгдүүлнэ гэсэн үг.

Implementation

Using the GCC compiler we can compute $x \cdot y \bmod n$ still efficiently, when all three numbers are 64 bit integer, since the compiler supports 128 bit integer with the types __int128 and __uint128.

long long result = (__int128)x * y % n;

However there is no type for 256 bit integer. Therefore we will here show an implementation for a 128 bit multiplication.

using u64 = uint64_t;
using u128 = __uint128_t;
using i128 = __int128_t;

struct u256 {
    u128 high, low;

    static u256 mult(u128 x, u128 y) {
        u64 a = x >> 64, b = x;
        u64 c = y >> 64, d = y;
        // (a*2^64 + b) * (c*2^64 + d) =
        // (a*c) * 2^128 + (a*d + b*c)*2^64 + (b*d)
        u128 ac = (u128)a * c;
        u128 ad = (u128)a * d;
        u128 bc = (u128)b * c;
        u128 bd = (u128)b * d;
        u128 carry = (u128)(u64)ad + (u128)(u64)bc + (bd >> 64u);
        u128 high = ac + (ad >> 64u) + (bc >> 64u) + (carry >> 64u);
        u128 low = (ad << 64u) + (bc << 64u) + bd;
        return {high, low};
    }
};

struct Montgomery {
    Montgomery(u128 n) : mod(n), inv(1) {
        for (int i = 0; i < 7; i++)
            inv *= 2 - n * inv;
    }

    u128 init(u128 x) {
        x %= mod;
        for (int i = 0; i < 128; i++) {
            x <<= 1;
            if (x >= mod)
                x -= mod;
        }
        return x;
    }

    u128 reduce(u256 x) {
        u128 q = x.low * inv;
        i128 a = x.high - u256::mult(q, mod).high;
        if (a < 0)
            a += mod;
        return a;
    }

    u128 mult(u128 a, u128 b) {
        return reduce(u256::mult(a, b));
    }

    u128 mod, inv;
};

Хурдан хувиргалт

Тоог Монтгомеригийн огторгуй руу хувиргах одоогийн арга нэлээд удаан. Илүү хурдан аргууд бий.

Та дараах хамаарлыг анзаарч болно:

$$\bar{x} := x \cdot r \bmod n = x \cdot r^2 / r = x * r^2$$

Тоог огторгуй руу хувиргах нь зүгээр л тухайн тоог огторгуй дотор $r^2$-тэй үржүүлэх явдал юм. Тиймээс бид $r^2 \bmod n$-г урьдчилан тооцоолж, тоог 128 удаа шилжүүлэхийн оронд зүгээр л нэг үржүүлэлт хийж болно.

In the following code we initialize r2 with -n % n, which is equivalent to $r - n \equiv r \bmod n$, shift it 4 times to get $r \cdot 2^4 \bmod n$. This number can be interpreted as $2^4$ in Montgomery space. If we square it $5$ times, we get $(2^4)^{2^5} = (2^4)^{32} = 2^{128} = r$ in Montgomery space, which is exactly $r^2 \bmod n$.

struct Montgomery {
    Montgomery(u128 n) : mod(n), inv(1), r2(-n % n) {
        for (int i = 0; i < 7; i++)
            inv *= 2 - n * inv;

        for (int i = 0; i < 4; i++) {
            r2 <<= 1;
            if (r2 >= mod)
                r2 -= mod;
        }
        for (int i = 0; i < 5; i++)
            r2 = mul(r2, r2);
    }

    u128 init(u128 x) {
        return mult(x, r2);
    }

    u128 mod, inv, r2;
};