خانه ویکی

معکوس پیمانه ای

معکوس پیمانه ای عدد $a$ به پیمانه $m$ ، عددی است مثل $x$ چنان که
\(a \cdot x \equiv 1 \mod m\)
به عدد $x$ ، $a^{-1}$ نیز می گویند.

محاسبه معکوس با الگوریتم اقلیدس

معادله زیر را در نظر بگیرید( $x$ و $y$ مجهول هستند ):
\(a \cdot x + m \cdot y = 1\)
این یک معادله دیوفانتی خطی با دو متغیر است. با استفاده از الگوریتم گسترده اقلیدس می توان جواب این معادله را بدست آورد.

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

محاسبه معکوس با قضیه اویلر

طبق قضیه اویلر:
\(a^{\phi (m)} \equiv 1 \mod m\)
دو طرف را در $a^{-1}$ ضرب می کنیم:
\(a ^ {\phi (m) - 1} \equiv a ^{-1} \mod m\)
که اگر $m$ عددی اول باشد:
\(a ^ {m - 2} \equiv a ^ {-1} \mod m\)
پس می توانیم در $O(\log m)$ معکوس پیمانه ای را به کمک الگوریتم توان به دست آوریم.

محاسبه کسر ها به پیمانه $m$

در بعضی از سوال ها که پاسخشان عددی گویا است، از شما به جای نمایش اعشاری کسر $\frac{p}{q}$ مقدار $p\cdot q^{-1} \mod m$ خواسته می شود. با توجه به این که :
\((a\cdot b^{-1}) \cdot (c\cdot d^{-1}) \equiv (a\cdot c)\cdot (b \cdot d)^{-1} \mod m\)
و این که :
\((a\cdot b^{-1}) + (c\cdot d^{-1}) \equiv (a\cdot d + c \cdot b) \cdot (b \cdot d)^{-1} \mod m\)
می توانیم هنگام جمع و ضرب دو کسر عدد همنهشت با آن ها به پیمانه $m$ را جمع و ضرب کنیم و هنگام تقسیم ، معکوس عدد همنهشت با مخرج را در صورت ضرب کنیم و به این صورت عدد همنهشت با یک کسر به پیمانه $m$ را بدست آوریم.