16.7: Додаток для розробки програмного забезпечення

Китайська теорема про залишок є результатом елементарної теорії чисел про розв'язання систем одночасних конгруенцій. Китайський математик Сунь-Ци писав про теорему в першому столітті н.е. ця теорема має деякі цікаві наслідки при проектуванні програмного забезпечення для паралельних процесорів.

Лемма\(16.41\)

\(n\)Дозволяти\(m\) і бути додатними цілими числами такі, що\(\gcd( m, n) = 1\text{.}\) Тоді для\(a, b \in {\mathbb Z}\) системи

\ begin {вирівнювати*} х &\ equiv a\ pmod {м}\\ x &\ equiv b\ pmod {n}\ end {align*}

має рішення. Якщо\(x_1\) і\(x_2\) є двома рішеннями системи, то\(x_1 \equiv x_2 \pmod{mn}\text{.}\)

Доказ

Рівняння\(x \equiv a \pmod{m}\) має рішення, оскільки\(a + km\) задовольняє рівнянню для всіх\(k \in {\mathbb Z}\text{.}\) Ми повинні показати, що існує ціле число\(k_1\) таке, що

\[ a + k_1 m \equiv b \pmod{n}\text{.} \nonumber \]

Це еквівалентно тому, щоб показати, що

\[ k_1 m \equiv (b-a) \pmod{n} \nonumber \]

має рішення для\(k_1\text{.}\) Since\(m\) і\(n\) є відносно простими, існують цілі числа\(s\) і\(t\) такі, що\(ms + nt = 1\text{.}\) Отже,

\[ (b-a) ms = (b-a) -(b-a) nt\text{,} \nonumber \]

або

\[ [(b-a)s]m \equiv (b-a) \pmod{n}\text{.} \nonumber \]

Тепер нехай\(k_1 = (b-a)s\text{.}\)

Щоб показати, що будь-які два рішення є конгруентними по модулю\(mn\text{,}\)\(c_2\) нехай\(c_1\) і є двома розв'язками системи. Тобто,

\ begin {align*} c_i &\ equiv a\ pmod {m}\\ c_i &\ equiv b\ pmod {n}\ кінець {align*}

для\(i = 1, 2\text{.}\) Тоді

\ begin {align*} c_2 &\ equiv c_1\ pmod {м}\\ c_2 &\ equiv c_1\ pmod {n}\ текст {.} \ end {вирівнювати*}

Тому обидва\(m\) і\(n\) розділити\(c_1 - c_2\text{.}\) Отже,\(c_2 \equiv c_1 \pmod{mn}\text{.}\)

Приклад\(16.42\)

Давайте вирішимо систему

\ почати {вирівнювати*} х &\ equiv 3\ pmod {4}\ x &\ equiv 4\ pmod {5}\ текст {.} \ end {вирівнювати*}

Рішення

Використовуючи евклідовий алгоритм, ми можемо знайти цілі числа\(s\) і\(t\) такі, що\(4s + 5t = 1\text{.}\) Два таких цілих числа\(s = 4\) і\(t = -3\text{.}\) Отже,

\[ x = a + k_1 m = 3 + 4k_1 = 3 + 4[(5 - 4)4] = 19\text{.} \nonumber \]

Теорема\(16.43\). Chinese Remainder Theorem

\(n_1, n_2, \ldots, n_k\)Дозволяти бути натуральні числа такі, що\(\gcd(n_i, n_j) = 1\) для\(i \neq j\text{.}\) Тоді для будь-яких цілих чисел\(a_1, \ldots, a_k\text{,}\) система

\ почати {вирівнювати*} х &\ equiv a_1\ pmod {n_1}\\ x &\ equiv a_2\ pmod {n_2}\\ &\ vdots\\ x &\ equiv a_k\ pmod {n_k}\ кінець {align*}

має рішення. Крім того, будь-які два рішення системи є конгруентними по модулю\(n_1 n_2 \cdots n_k\text{.}\)

Доказ

Ми будемо використовувати математичну індукцію за кількістю рівнянь в системі. Якщо є\(k= 2\) рівняння, то теорема вірна по Леммі\(16.41\). Тепер припустимо, що результат вірний для системи\(k\) рівнянь або менше, і що ми хочемо знайти рішення

\ почати {вирівнювати*} х &\ equiv a_1\ pmod {n_1}\\ x &\ equiv a_2\ pmod {n_2}\\ &\ vdots\\ x &\ equiv a_ {k+1}\ pmod {n_ {k+1}}\ текст {.} \ end {вирівнювати*}

Розглядаючи перші\(k\) рівняння, існує рішення, яке є унікальним по модулю\(n_1 \cdots n_k\text{,}\) скажімо\(a\text{.}\) Оскільки\(n_1 \cdots n_k\) і\(n_{k+1}\) є відносно простим, система

\ почати {вирівнювати*} х &\ equiv a\ pmod {n_1\ cdots n_k}\\ x &\ equiv a_ {k+1}\ pmod {n_ {k+1}}\ кінець {align*}

має рішення, яке є унікальним\(n_1 \ldots n_{k+1}\) модулем леми.

Приклад\(16.44\)

Давайте вирішимо систему

\ почати {вирівнювати*} х &\ equiv 3\ pmod {4}\ x &\ equiv 4\ pmod {5}\ x &\ equiv 1\ pmod {9}\ x &\ equiv 5\ pmod {7}\ текст {.} \ end {вирівнювати*}

Рішення

З Прикладу\(16.42\) ми знаємо, що\(19\) це рішення перших двох конгруенцій, і будь-яке інше рішення системи є конгруентним\(19 \pmod{20}\text{.}\) Отже, ми можемо зменшити систему до системи з трьох конгруенцій:

\ почати {вирівнювати*} х &\ еквив 19\ pmod {20}\ x &\ equiv 1\ pmod {9}\ x &\ equiv 5\ pmod {7}\ текст {.} \ end {вирівнювати*}

Вирішуючи наступні два рівняння, ми можемо звести систему до

\ почати {вирівнювати*} х &\ еквив 19\ pmod {180}\ x &\ equiv 5\ pmod {7}\ текст {.} \ end {вирівнювати*}

Вирішуючи цю останню систему, ми виявляємо, що\(19\) це рішення для системи, яке є унікальним до модулю\(1260\text{.}\)

Одне цікаве застосування китайської теореми про залишок при проектуванні комп'ютерного програмного забезпечення полягає в тому, що теорема дозволяє розбити обчислення за участю великих цілих чисел на кілька менш грізних обчислень. Комп'ютер буде обробляти цілочисельні обчислення тільки до певного розміру через розмір свого процесорного чіпа, який, як правило, є 32 або 64-бітним процесорним чіпом. Наприклад, найбільше ціле число, доступне на комп'ютері з 64-бітовим процесорним чіпом, це

\[ 2^{63} - 1 = 9{,}223{,}372{,}036{,}854{,}775{,}807\text{.} \nonumber \]

Більші процесори, такі як 128 або 256-бітні, були запропоновані або знаходяться в стадії розробки. Йдеться навіть про 512-бітному процесорному чіпі. Найбільше ціле число, що такий чіп може зберігати з бути\(2^{511} - 1\text{,}\), який буде 154 цифра числа. Однак нам доведеться мати справу з набагато більшими числами, щоб зламати складні схеми шифрування.

Спеціальне програмне забезпечення необхідне для обчислень з більшими цілими числами, які не можуть бути додані безпосередньо машиною. Використовуючи китайську теорему про залишок, ми можемо розбити великі цілі доповнення та множення на обчислення, які комп'ютер може обробляти безпосередньо. Це особливо корисно на комп'ютерах паралельної обробки, які мають можливість запускати кілька програм одночасно.

Більшість комп'ютерів мають єдиний центральний процесор (CPU), що містить один процесорний чіп і може додавати лише два числа одночасно. Щоб додати список з десяти чисел, процесор повинен зробити дев'ять доповнень послідовно. Однак комп'ютер паралельної обробки має більше одного процесора. Наприклад, комп'ютер з 10 процесорами може виконувати 10 різних доповнень одночасно. Якщо ми можемо взяти велике ціле число і розбити його на частини, відправляючи кожну частину в інший процесор, то виконуючи кілька доповнень або множень одночасно на цих частинок, ми можемо працювати з цілим числом, яке комп'ютер не зможе обробляти в цілому.

Приклад\(16.45\)

Припустимо, що ми бажаємо помножити\(2134\) на\(1531\text{.}\)

Рішення

Ми будемо використовувати цілі числа\(95\text{,}\)\(97\text{,}\)\(98\text{,}\) і\(99\) тому, що вони відносно прості. Ми можемо розбити кожне ціле число на чотири частини:

\ почати {вирівнювати*} 2134 &\ еквив 44\ pmod {95}\\ 2134 &\ equiv 0\ pmod {97}\ 2134 &\ equiv 76\ pmod {98}\ 2134 &\ еквив 55\ pmod {99}\ кінець {вирівнювати*}

і

\ почати {вирівнювати*} 1531 &\ еквив 11\ pmod {95}\ 1531 &\ еквив 76\ pmod {97}\ 1531 &\ еквив 61\ pmod {98}\ 1531 &\ еквив 46\ pmod {99}\ текст {.} \ end {вирівнювати*}

Помноживши відповідні рівняння, отримаємо

\ почати {вирівнювати*} 2134\ cdot 1531 &\ еквив 4\ cdot 1\ еквив 9\ pmod {95}\ 2134\ cdot 1531 &\ еквив 0\ cdot 76\ еквив 0\ pmod {97}\ 2134\ cdot 76\ cdot 61\ equiv 30\ pmod {98}\ 2134\ ccov точка 1531 &\ еквівалент 5\ cdot 46\ еквив 5\ pmod {9}\ текст {.} \ end {вирівнювати*}

Кожен з цих чотирьох обчислень може бути відправлений на інший процесор, якщо наш комп'ютер має кілька процесорів. За вищенаведеним розрахунком ми знаємо, що\(2134 \cdot 1531\) це рішення системи

\ почати {вирівнювати*} х &\ еквив 9\ pmod {95}\ x &\ equiv 0\ pmod {97}\ x &\ equiv 30\ pmod {98}\ x &\ equiv 55\ pmod {99}\ текст {.} \ end {вирівнювати*}

Китайська теорема про залишок говорить нам, що рішення є унікальними до модулю\(95 \cdot 97 \cdot 98 \cdot 99 = 89{,}403{,}930\text{.}\) Рішення цієї системи конгруенцій для\(x\) говорить нам, що\(2134 \cdot 1531 = 3{,}267{,}154\text{.}\)

Перетворення обчислень в чотири підобчислення займе деякий час обчислень. Крім того, вирішення системи конгруенцій також може зайняти значний час. Однак якщо у нас є багато обчислень, які потрібно виконати на певному наборі чисел, має сенс перетворити задачу, як ми зробили вище, і виконувати необхідні обчислення одночасно.