Үржигдэхүүнд задлах хоёртын зэрэгт дэвшүүлэлт¶
$a$, $x$, $y$ бүхэл тоо ба $d \geq 3$ өгөгдсөн, $x$ нь сондгой байх үед $ax^y \pmod{2^d}$-г тооцоолох бодлогыг авч үзье.
Доорх алгоритм нь энэ бодлогыг $O(d)$ нэмэлт ба битийн үйлдэл, мөн $y$-гээр ганц үржүүлэлтээр бодох боломж олгодог.
$2^d$ модулиар мультипликатив бүлгийн бүтцээс шалтгаалан $x \equiv 1 \pmod 4$ байх дурын тоо $x$-г дараах байдлаар илэрхийлж болно
энд $b \equiv 5 \pmod 8$. Ерөнхий чанарыг алдагдуулалгүйгээр бид $x \equiv 1 \pmod 4$ гэж үзнэ, учир нь $x \mapsto -x$ ба $a \mapsto (-1)^{y} a$ орлуулга хийснээр $x \equiv 3 \pmod 4$-г $x \equiv 1 \pmod 4$ болгон хураах боломжтой. Энэ утгаараа $ax^y$-г дараах байдлаар илэрхийлнэ
Алгоритмын гол санаа нь бид $2^d$ модулиар ажиллаж байгааг ашиглан $L(x)$ ба $b^{y L(x)}$-ийн тооцооллыг хялбарчлах явдал юм. Дараа нь тодорхой болох шалтгааны улмаас бид $L(x)$-ийн оронд $4L(x)$-тэй ажиллана, гэхдээ $2^{d-2}$-ын оронд $2^d$ модулиар авна.
In this article, we will cover the implementation for $32$-bit integers. Let
mbin_log_32(r, x)be a function that computes $r+4L(x) \pmod{2^d}$;mbin_exp_32(r, x)be a function that computes $r b^{\frac{x}{4}} \pmod{2^d}$;mbin_power_odd_32(a, x, y)be a function that computes $ax^y \pmod{2^d}$.
Then mbin_power_odd_32 is implemented as follows:
uint32_t mbin_power_odd_32(uint32_t rem, uint32_t base, uint32_t exp) {
if (base & 2) {
/* divider is considered negative */
base = -base;
/* check if result should be negative */
if (exp & 1) {
rem = -rem;
}
}
return (mbin_exp_32(rem, mbin_log_32(0, base) * exp));
}
x-ээс 4L(x)-г тооцоолох¶
$x$ нь $x \equiv 1 \pmod 4$ байх сондгой тоо байг. Түүнийг дараах байдлаар илэрхийлж болно
энд $1 < a_1 < \dots < a_k < d$. Энд $L(\cdot)$ нь үржүүлэгч бүрийн хувьд сайн тодорхойлогдсон, учир нь тэдгээр нь $4$ модулиар $1$-тэй тэнцүү. Тиймээс,
Тиймээс хэрэв бид бүх $1 < k < d$-ийн хувьд $t_k = 4L(2^n+1)$-г урьдчилан тооцоолвол дурын тоо $x$-ийн хувьд $4L(x)$-г тооцоолж чадна.
For 32-bit integers, we can use the following table:
const uint32_t mbin_log_32_table[32] = {
0x00000000, 0x00000000, 0xd3cfd984, 0x9ee62e18,
0xe83d9070, 0xb59e81e0, 0xa17407c0, 0xce601f80,
0xf4807f00, 0xe701fe00, 0xbe07fc00, 0xfc1ff800,
0xf87ff000, 0xf1ffe000, 0xe7ffc000, 0xdfff8000,
0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
0xfff00000, 0xffe00000, 0xffc00000, 0xff800000,
0xff000000, 0xfe000000, 0xfc000000, 0xf8000000,
0xf0000000, 0xe0000000, 0xc0000000, 0x80000000,
};
On practice, a slightly different approach is used than described above. Rather than finding the factorization for $x$, we will consequently multiply $x$ with $2^n+1$ until we turn it into $1$ modulo $2^d$. In this way, we will find the representation of $x^{-1}$, that is
To do this, we iterate over $n$ such that $1 < n < d$. If the current $x$ has $n$-th bit set, we multiply $x$ with $2^n+1$, which is conveniently done in C++ as x = x + (x << n). This won't change bits lower than $n$, but will turn the $n$-th bit to zero, because $x$ is odd.
With all this in mind, the function mbin_log_32(r, x) is implemented as follows:
uint32_t mbin_log_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n < 32; n++) {
if (x & (1 << n)) {
x = x + (x << n);
r -= mbin_log_32_table[n];
}
}
return r;
}
Note that $4L(x) = -4L(x^{-1})$, so instead of adding $4L(2^n+1)$, we subtract it from $r$, which initially equates to $0$.
4L(x)-ээс x-г тооцоолох¶
$k \geq 1$-ийн хувьд дараах нь биелнэ гэдгийг анхаараарай
эндээс (давтан квадрат авах замаар) бид дараахыг гаргаж болно
Энэ үр дүнг $a=2^n+1$ ба $b=d-k$-д хэрэглэснээр $2^n+1$-ийн мультипликатив эрэмбэ нь $2^{d-n}$-ийн хуваагч болохыг гаргаж байна.
Энэ нь эргээд $L(2^n+1)$ нь $2^{n}$-д хуваагдах ёстой гэсэн үг, учир нь $b$-ийн эрэмбэ нь $2^{d-2}$, $b^y$-ийн эрэмбэ нь $2^{d-2-v}$ бөгөөд энд $2^v$ нь $y$-г хуваадаг $2$-ын хамгийн өндөр зэрэг, тиймээс бидэнд
хэрэгтэй, улмаар $v$ нь $k-2$-оос их буюу тэнцүү байх ёстой. Энэ нь арай эвгүй бөгөөд үүнийг зөөлрүүлэхийн тулд бид эхэнд $L(x)$-г $4$-ээр үржүүлнэ гэж хэлсэн. Одоо хэрэв бид $4L(x)$-г мэдэж байвал $4L(x)$ дахь битүүдийг дараалан шалгах замаар түүнийг $4L(2^n+1)$-үүдийн нийлбэр болгон цор ганц байдлаар задалж болно. Хэрэв $n$ дугаар бит $1$ бол бид үр дүнг $2^n+1$-ээр үржүүлж, одоогийн $4L(x)$-г $4L(2^n+1)$-ээр багасгана.
Thus, mbin_exp_32 is implemented as follows:
uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n < 32; n++) {
if (x & (1 << n)) {
r = r + (r << n);
x -= mbin_log_32_table[n];
}
}
return r;
}
Further optimizations¶
It is possible to halve the number of iterations if you note that $4L(2^{d-1}+1)=2^{d-1}$ and that for $2k \geq d$ it holds that
which allows to deduce that $4L(2^n+1)=2^n$ for $2n \geq d$. So, you could simplify the algorithm by only going up to $\frac{d}{2}$ and then use the fact above to compute the remaining part with bitwise operations:
uint32_t mbin_log_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n != 16; n++) {
if (x & (1 << n)) {
x = x + (x << n);
r -= mbin_log_32_table[n];
}
}
r -= (x & 0xFFFF0000);
return r;
}
uint32_t mbin_exp_32(uint32_t r, uint32_t x) {
uint8_t n;
for (n = 2; n != 16; n++) {
if (x & (1 << n)) {
r = r + (r << n);
x -= mbin_log_32_table[n];
}
}
r *= 1 - (x & 0xFFFF0000);
return r;
}
Логарифмын хүснэгт тооцоолох¶
Лог хүснэгтийг тооцоолохын тулд модуль нь $2$-ын зэрэг байх тохиолдолд Полиг–Хеллманы алгоритм-ыг өөрчилж болно.
Энд бидний гол ажил бол $g^x \equiv y \pmod{2^d}$ байх $x$-г тооцоолох явдал юм, энд $g=5$ ба $y$ нь $2^n+1$ хэлбэрийн тоо.
Хоёр талыг $k$ удаа квадрат авбал бид дараахад хүрнэ
$g$-ийн эрэмбэ нь $2^{d}$-ээс их биш болохыг анхаараарай (үнэндээ $2^{d-2}$-ээс, гэхдээ бид тохиромжтой байдлаар $2^d$-г баримтална), тиймээс $k=d-1$ ашиглавал бид зүүн талд $g^1$ эсвэл $g^0$-ийн аль нэгийг авах бөгөөд энэ нь $y^{2^k}$-г $g$-тэй харьцуулах замаар $x$-ийн хамгийн бага битийг тодорхойлох боломж олгоно. Одоо $x=x_0 + 2^k x_1$ гэж үзье, энд $x_0$ нь мэдэгдэж буй хэсэг, $x_1$ нь хараахан мэдэгдээгүй. Тэгвэл
Хоёр талыг $g^{-x_0}$-ээр үржүүлбэл бид дараахыг авна
Одоо хоёр талыг $d-k-1$ удаа квадрат авснаар бид $x$-ийн дараагийн битийг олж, эцэст нь бүх битийг нь сэргээж чадна.