CRT

قضیه Chinese Remainder¶

قضیه Chinese Remainder نشان میدهد که اگر یک دستگاه همنشتی خطی به فرم $x\equiv a \pmod{m}$ با این شرط که پیمانه ها دو به دو نسبت به اول باشند آنگاه یک پاسخ منحصر به فرد مانند $x$ به پیمانه ضرب پیمانه های معادلات وجود دارد. این قضیه به ویژه در حل سیستم های معادلات پیمانه ای همزمان که حل آنها به صورت جداگانه دشوار یا غیرممکن است مفید است. برای مثال، اگر دو رابطه همنهشتی داشته باشیم:

$x \equiv 3 \pmod{4}$

$x \equiv 2 \pmod{5}$

با استفاده از CRT میتوانیم یک جواب منحصر به فرد مانند $x$ به پیمانه 20 که هر دو رابطه همنهشتی را ارضا میکند بیابیم.

این قضیه کاربردهای زیادی در رمزنگاری، نظریه اعداد و علوم کامپیوتر دارد. به عنوان مثال، در رمزگذاری RSA برای سرعت بخشیدن به محاسبه معکوس پیمانه ای و در ساخت سیستم های رمزنگاری کلید عمومی بر اساس فاکتورگیری اعداد صحیح استفاده می شود.

الگوریتم¶

ما به دو متغیر نیاز داریم:

$N = n_1 \cdot n_1 \cdot ... \cdot n_i$

$E = \left[ \frac{N}{n_1}, \frac{N}{n_2}, ..., \frac{N}{n_i} \right]$

برای هر عضو از $E$ باید معکوس به پیمانه $n_i$ مانند $y$ محاسبه شود یعنی:

$E_i \cdot y \equiv 1 \pmod{n_i}$

و یک جواب ما به این صورت خواهد بود که:

$x = a_1 \cdot E_1 \cdot y_1 + a_2 \cdot E_2 \cdot y_2 + ... + a_i \cdot E_i \cdot y_i$

و جواب منحصر به فرد ما $x \equiv 0 \pmod{N}$ خواهد بود.

پیاده سازی¶

example.sage
b_list = [2, 3, 10]
n_list = [5, 7, 11]
x = CRT(b_list, n_list)
# x = 87

نویسنده

MohamadAli