Lewati ke konten utama

Bagian 16.5 Penerapan pada Perancangan Perangkat Lunak

Teorema Sisa Cina merupakan hasil dalam teori bilangan elementer mengenai penyelesaian sistem kongruensi simultan. Matematikawan Cina Sun-tsï menulis tentang teorema ini pada abad pertama Masehi. Teorema ini memiliki beberapa konsekuensi menarik bagi perancangan perangkat lunak untuk prosesor paralel.

Bukti.
Persamaan \(x \equiv a \pmod{m}\) mempunyai solusi karena \(a + km\) memenuhi persamaan tersebut untuk setiap \(k \in {\mathbb Z}\text{.}\) Kita harus menunjukkan bahwa terdapat bilangan bulat \(k_1\) sedemikian sehingga
\begin{equation*} a + k_1 m \equiv b \pmod{n}\text{.} \end{equation*}
Hal ini ekuivalen dengan menunjukkan bahwa
\begin{equation*} k_1 m \equiv (b-a) \pmod{n} \end{equation*}
mempunyai solusi untuk \(k_1\text{.}\) Karena \(m\) dan \(n\) relatif prima, terdapat bilangan bulat \(s\) dan \(t\) sedemikian sehingga \(ms + nt = 1\text{.}\) Akibatnya,
\begin{equation*} (b-a) ms = (b-a) -(b-a) nt\text{,} \end{equation*}
atau
\begin{equation*} [(b-a)s]m \equiv (b-a) \pmod{n}\text{.} \end{equation*}
Sekarang ambil \(k_1 = (b-a)s\text{.}\)
Untuk menunjukkan bahwa sembarang dua solusi kongruen modulo \(mn\text{,}\) misalkan \(c_1\) dan \(c_2\) adalah dua solusi sistem tersebut. Artinya,
\begin{align*} c_i & \equiv a \pmod{m}\\ c_i & \equiv b \pmod{n} \end{align*}
untuk \(i = 1, 2\text{.}\) Maka
\begin{align*} c_2 & \equiv c_1 \pmod{m}\\ c_2 & \equiv c_1 \pmod{n}\text{.} \end{align*}
Oleh karena itu, \(m\) maupun \(n\) membagi \(c_1 - c_2\text{.}\) Akibatnya, \(c_2 \equiv c_1 \pmod{mn}\text{.}\)

Contoh 16.5.2.

Mari kita selesaikan sistem
\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\text{.} \end{align*}
Dengan menggunakan algoritma Euklides, kita dapat menemukan bilangan bulat \(s\) dan \(t\) sedemikian sehingga \(4s + 5t = 1\text{.}\) Dua bilangan bulat yang memenuhi syarat itu adalah \(s = 4\) dan \(t = -3\text{.}\) Akibatnya,
\begin{equation*} x = a + k_1 m = 3 + 4k_1 = 3 + 4[(5 - 4)4] = 19\text{.} \end{equation*}

Bukti.
Kita akan menggunakan induksi matematika pada banyaknya persamaan dalam sistem. Jika terdapat \(k= 2\) persamaan, teorema ini benar berdasarkan Lema 16.5.1. Sekarang andaikan hasil tersebut benar untuk suatu sistem yang terdiri atas \(k\) persamaan atau kurang dan kita hendak mencari solusi dari
\begin{align*} x & \equiv a_1 \pmod{n_1}\\ x & \equiv a_2 \pmod{n_2}\\ & \aatavdots{\equiv}\\ x & \equiv a_{k+1} \pmod{n_{k+1}}\text{.} \end{align*}
Dengan meninjau \(k\) persamaan pertama, terdapat solusi yang tunggal modulo \(n_1 \cdots n_k\text{,}\) katakanlah \(a\text{.}\) Karena \(n_1 \cdots n_k\) dan \(n_{k+1}\) relatif prima, sistem
\begin{align*} x & \equiv a \pmod{n_1 \cdots n_k }\\ x & \equiv a_{k+1} \pmod{n_{k+1}} \end{align*}
mempunyai solusi yang tunggal modulo \(n_1 \ldots n_{k+1}\) berdasarkan lemma tersebut.

Contoh 16.5.4.

Mari kita selesaikan sistem
\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}
Dari Contoh 16.5.2 kita mengetahui bahwa \(19\) merupakan solusi dari dua kongruensi pertama dan setiap solusi lain dari sistem tersebut kongruen dengan \(19 \pmod{20}\text{.}\) Jadi, kita dapat mereduksi sistem tersebut menjadi sistem tiga kongruensi:
\begin{align*} x & \equiv 19 \pmod{20}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}
Dengan menyelesaikan dua persamaan berikutnya, kita dapat mereduksi sistem menjadi
\begin{align*} x & \equiv 19 \pmod{180}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}
Dengan menyelesaikan sistem terakhir ini, kita memperoleh bahwa \(19\) merupakan solusi sistem yang tunggal modulo \(1260\text{.}\)
Salah satu penerapan menarik Teorema Sisa Cina dalam perancangan perangkat lunak komputer ialah bahwa teorema tersebut memungkinkan kita memecah perhitungan yang melibatkan bilangan bulat besar menjadi beberapa perhitungan yang lebih mudah ditangani. Karena ukuran cip prosesornya, komputer hanya dapat menangani perhitungan bilangan bulat sampai ukuran tertentu; cip prosesor tersebut biasanya berukuran 32 atau 64 bit. Sebagai contoh, bilangan bulat terbesar yang tersedia pada komputer dengan cip prosesor 64 bit adalah
\begin{equation*} 2^{63} - 1 = 9{,}223{,}372{,}036{,}854{,}775{,}807\text{.} \end{equation*}
Prosesor yang lebih besar, seperti prosesor 128 atau 256 bit, telah diusulkan atau sedang dikembangkan. Bahkan, cip prosesor 512 bit pernah dibicarakan. Bilangan bulat terbesar yang dapat disimpan oleh cip semacam itu adalah \(2^{511} - 1\text{,}\) yakni bilangan yang terdiri atas 154 digit. Namun, kita perlu menangani bilangan yang jauh lebih besar untuk memecahkan sistem enkripsi canggih.
Perangkat lunak khusus diperlukan untuk perhitungan yang melibatkan bilangan bulat lebih besar yang tidak dapat dijumlahkan secara langsung oleh mesin. Dengan menggunakan Teorema Sisa Cina, kita dapat memecah penjumlahan dan perkalian bilangan bulat besar menjadi perhitungan yang dapat ditangani komputer secara langsung. Hal ini sangat berguna pada komputer pemrosesan paralel yang mampu menjalankan beberapa program secara bersamaan.
Kebanyakan komputer memiliki satu unit pemrosesan pusat (CPU) yang memuat satu cip prosesor dan hanya dapat menjumlahkan dua bilangan pada satu waktu. Untuk menjumlahkan daftar yang berisi sepuluh bilangan, CPU harus melakukan sembilan penjumlahan secara berurutan. Namun, komputer pemrosesan paralel memiliki lebih dari satu CPU. Sebagai contoh, komputer dengan 10 CPU dapat melakukan 10 penjumlahan yang berbeda secara bersamaan. Jika kita dapat memecah bilangan bulat besar menjadi beberapa bagian dan mengirim setiap bagian ke CPU yang berbeda, dengan melakukan beberapa penjumlahan atau perkalian secara serentak pada bagian-bagian tersebut, kita dapat bekerja dengan bilangan bulat yang tidak dapat ditangani komputer secara utuh.

Contoh 16.5.5.

Andaikan kita hendak mengalikan \(2134\) dengan \(1531\text{.}\) Kita akan menggunakan bilangan bulat \(95\text{,}\) \(97\text{,}\) \(98\text{,}\) dan \(99\) karena bilangan-bilangan tersebut saling relatif prima. Kita dapat memecah setiap bilangan bulat menjadi empat bagian:
\begin{align*} 2134 & \equiv 44 \pmod{95}\\ 2134 & \equiv 0 \pmod{97}\\ 2134 & \equiv 76 \pmod{98}\\ 2134 & \equiv 55 \pmod{99} \end{align*}
dan
\begin{align*} 1531 & \equiv 11 \pmod{95}\\ 1531 & \equiv 76 \pmod{97}\\ 1531 & \equiv 61 \pmod{98}\\ 1531 & \equiv 46 \pmod{99}\text{.} \end{align*}
Dengan mengalikan persamaan-persamaan yang bersesuaian, kita memperoleh
\begin{align*} 2134 \cdot 1531 & \equiv 44 \cdot 11 \equiv 9 \pmod{95}\\ 2134 \cdot 1531 & \equiv 0 \cdot 76 \equiv 0 \pmod{97}\\ 2134 \cdot 1531 & \equiv 76 \cdot 61 \equiv 30 \pmod{98}\\ 2134 \cdot 1531 & \equiv 55 \cdot 46 \equiv 55 \pmod{99}\text{.} \end{align*}
Jika komputer kita memiliki beberapa CPU, masing-masing dari keempat perhitungan ini dapat dikirim ke prosesor yang berbeda. Berdasarkan perhitungan di atas, kita mengetahui bahwa \(2134 \cdot 1531\) merupakan solusi dari sistem
\begin{align*} x & \equiv 9 \pmod{95}\\ x & \equiv 0 \pmod{97}\\ x & \equiv 30 \pmod{98}\\ x & \equiv 55 \pmod{99}\text{.} \end{align*}
Teorema Sisa Cina menyatakan bahwa solusi-solusi sistem tersebut tunggal modulo \(95 \cdot 97 \cdot 98 \cdot 99 = 89{,}403{,}930\text{.}\) Dengan menyelesaikan sistem kongruensi ini untuk \(x\text{,}\) kita memperoleh \(2134 \cdot 1531 = 3{,}267{,}154\text{.}\)
Pengubahan perhitungan menjadi empat subperhitungan memerlukan sejumlah waktu komputasi. Selain itu, penyelesaian sistem kongruensi juga dapat memerlukan waktu yang cukup lama. Namun, jika kita perlu melakukan banyak perhitungan pada suatu himpunan bilangan tertentu, masuk akal untuk mengubah masalah seperti yang kita lakukan di atas dan menjalankan perhitungan yang diperlukan secara serentak.
Sblm.Paling AtasLanjut