Aritmetika modular

Dalam matematika dan khususnya pada teori bilangan aljabar, aritmetika modular adalah metode aritmetika untuk menyelesaikan permasalahan mengenai bilangan bulat. Ide dasar dari aritmetika modular adalah bekerja dengan sisa hasil pembagian bilangan, bukan dengan bilangan itu sendiri. Salah satu contoh dari aritmetika modular ada pada sistem 12-jam, di mana hari dibagi menjadi dua periode 12-jam. Jika sekarang jarum jam menunjukan pukul 7:00, maka 8 jam kemudian akan menunjukan pukul 3:00. Penambahan sederhana akan menghasilkan . Namun karena jam "berulang" setiap 12 jam, angka 15 "sama dengan" angka 3; ini adalah contoh aritmetika modulo 12.

Walau sudah dipelajari sejak kuno, sejarawan umumnya mengasosiasikan kemunculan aritmetika modular dengan tahun 1801, tahun publikasi buku Disquisitiones Arithmeticae  karya Carl Friedrich Gauss. Pendekatan yang ia gunakan mempermudah penjelasan konjektur-konjektur terkenal, dan menyederhanakan bukti-bukti penting. Implikasi karya Gauss juga ditemukan pada bidang selain teori bilangan, seperti aljabar dan geometri.

Kegunaan aritmetika modular meningkat pada abad ke-20. Operasi aritmetika dasar pada komputer yang bekerja pada jumlah bit yang tetap, pada dasarnya adalah operasi aritmetika modular. Penerapan pada bidang industri memicu perkembangan algoritma aritmetika modular.

Sejarah

Asal mula 

Pada abad ke-3 SM, Euklides merumuskan fondasi-fondasi aritmetika dalam bukunya Element. Di dalamnya, terdapat sebuah lema yang umum dirujuk sebagai lema Euklides, versi awal dari teorema dasar aritmetika dan studi mengenai bilangan sempurna dalam proposisi 36 pada bukunya ke-9. Diofantos dari Alexandria (sekitar 250 M) menulis buku Arithmetica yang memuat 130 persamaan. Sebagian besar isinya membahas permasalahan yang memiliki hanya satu solusi, baik dalam bentuk pecahan maupun bilangan bulat. Buku tersebut juga menunjukkan bahwa jumlah dari dua bilangan sempurna tidak pernah dalam bentuk . Bentuk persamaan yang ia bahas, dengan koefisien persamaan dan solusi yang diharapkan berupa bilangan bulat, saat ini dikenal sebagai persamaan Diofantin.

Aritmetika modular juga berkembang di Cina. Sekitar 300 M, Sunzi Suanjing menulis risalah matematika, yang pada permasalahan ke-26 di bab ke-3 berisi: "Anggap ada barang yang jumlahnya tidak kita ketahui. Dengan menghitung tiga demi tiga, ada tersisa dua barang. Dengan menghitung lima demi lima, ada sisa tiga barang, dan ketika dihitung tujuh demi tujuh, ada sisa dua. Berapa banyak barang yang ada disana?".

Qin Jiushao (1202-1261) mengembangkan teorema sisa Cina dalam risalah matematika yang ia tulis. Materi pada risalah tesebut sangat dalam; membahas sistem kekongruenan linear pada kasus modulus-modulus pada sistem tidak saling koprima. George Sarton menyatakan bahwa karyanya pada sistem kekongruenan melebihi Leonhard Euler dan Gauss. Namun, karya Qin Jiushao tidak tedengar di luuar Cina sebelum abad ke-20. Karyanya ditemukan ulang oleh sejarawan Joseph Needham. Di sisi lain, kemiripan notasi yang digunakan di Arab dan Cina mengusulkan ada kontak yang terjadi pada periode-periode sebelumnya.

India juga memiliki tradisi kuat dalam aritmetika. Aryabhata (476 - 550) secara sistematik mencari solusi bilangan bulat dari persamaan linear dengan dua variabel dan koefisien bilangan bulat. Algoritmanya dirujuk sebagai "Kuttaka" pada bukunya Âryabhatîya. Persamaan Diofantin derajat dua dipelajari Brahmagupta (598 - 668). Pada abad ke-12, Bhāskara II menyempurnakan metode Chakravala.

Masa Islam abad pertengahan memegang peran ganda dalam perkembangan aritmetika: menggabungkan pengetahuan yang didapatkan di Yunani, India, Cina, dan Eropa, dan menciptakan penemuan baru. Hal ini termasuk studi mengenai sifat dari himpunan bilangan, seperti prima, sempurna, ramah (amicable), dan poligonal. Dalam konteks ini, Qusta bin Lûqâ melakukan terjemahan parsial buku Arithmetica milik Diofantos dari Alexandria, di akhir abad ke-9. Pada masa yang sama, Al-Hajjaj menerjemahkan Elemen milik Euclid. Koleganya, Al-Kharizmi (sekitar 783 - 850), menulis buku mengenai numerisasi. Terjemahan bahasa Latin dari buku ini adalah Algoritmi de numero Indorum. Tsabit bin Qurrah (836-901) mempelajari bilangan amicable dan bilangan sempurna. Ibnu Haitham (965 - 1039) melanjutkan hasil kerjanya dan menemukan teorema Wilson.

Perkembangan di Eropa 

Pada tahun 1621, Claude-Gaspard Bachet de Méziriac menerjemahkan buku Diofantos ke bahasa Latin, yang memicu ketertarikan matematikawan saat itu. Pierre de Fermat banyak memberikan pernyataan matematika, tiga yang terkenal adalah teorema terakhir-nya, teorema jumlah dua persegi, dan teorema kecil-nya. Marin Mersenne mencari bilangan prima yang mememiliki sifat unik. Fermat berkorespodensi dengannya, menulis [terjemahan] "Jika saya mengetahui alasan fundamental mengapa 3, 5, 7, 17, 257, 65537, ..., adalah bilangan prima, sepertinya saya akan menemukan hal yang sangat indah dalam masalah ini, karena saya sudah menemukan hal hebat yang saya bagikan kepadamu saat ini". Bilangan tersebut dikenal sebagai bilangan Fermat, walau sifat keprimaannya bilangan-bilangan tersebut ternyata hanya tebakan yang keliru dari Fermat. Rene Descartes melakukan penelitian tanpa hasil, dalam membuktikan jika sisa pembagian bilangan prima dengan 8 bernilai 1 atau 3, bilangan prima tersebut dapat ditulis dalam bentuk .

Kontribusi Carl Friedrich Gauss 

Ketika berusia 17 tahun, Gauss membuktikan teorema quadratic reciprocity. Setahun kemudian, pada 30 Maret 1796, ia menyadari kalkulasi aritmetika-nya memungkinkan untuk mengontruksi heptadekagon (poligon dengan 17 sisi) dengan menggunakan jangka dan penggaris, sebuah permasalahan yang tidak terjawab sejak masa kuno. Akhirnya pada 1801, ia mempublikasikan Disquisitiones Arithmeticae (Penelitian tentang Aritmetika), dan dijuluki pangeran matematikawan.

Dua penemuan Gauss tersebut berasal dari pendekatan yang sama, dengan peralatan yang lebih maju ketimbang pada masa Fermat maupun Euler. Hal ini memungkinkan untuk menulis pembuktian yang lebih sederhana, walau menjadi lebih abstrak. Pendekatannya adalah dasar bagi aritmetika modular.

Aritmetika modular awalnya diterapkan kepada bilangan bulat, lalu ke polinomial, dilanjutkan kepada himpunan bilangan baru yang sekarang disebut dengan bilangan Gaussian.

Semua persamaan Diofantin Fermat sudah terselesaikan saat ini, kecuali untuk teorema terakhirnya. Beberapa konjektur baru muncul. Sebagai contoh, jika a dan b saling koprima, apakah barisan aritmetika dengan nilai awal a dan kelipatan b memiliki bilangan prima, jika iya berapa banyak? Gauss dan matematikawan lain seperti Legendre berhipotesis bahwa ada takhingga prima di barisan tersebut, namun mereka tidak mampu membuktikannnya.

Aritmetika modular juga semakin diperkaya. Dirichlet, seorang siswa Gauss membuktikan teorema aritmetic progression dengan mengembangkan konsep karakter, sekaligus memberi dasar formal untuk ilmu teori bilangan analitik.

Abad ke-20

Kriptografi 

Kriptografi adalah ilmu yang mempelajari sandi rahasia, dan awalnya termasuk dalam matematika murni. Di sisi lain, aplikasi pada bidang industri yang meningkat membuat notasi matematika yang dikembangkan Gauss populer digunakan dalam ilmu ini. Pada tahun 1883, Auguste Kerckhoffs menyatakan bahwa "keamanan sistem kriptografi seharusnya tidak didasarkan pada kerahasiaan algoritma yang digunakan. Keamanan seharusnya hanya bergantung pada kerahasiaan kunci." Pendekatan baru ini memodifikasi bentuk ilmu ini. Pada pertengahan abad ke-20, ilmu ini menjadi cabang dari matematika terapan.

Pada awal tahun 1930-an, kantor sandi Polandia meminta matematikawan Marian Rejewski untuk memecahkan kode mesin Enigma, yang digunakan oleh Jerman. Kode lawas, seperti sandi Caesar, didefinisikan ulang sebagai transformasi matematis pada himpunan modulus Gaussian atas bilangan bulat. Istilah "aritmatika modular" digunakan untuk menjelaskan teknik ini.

Teori informasi 

Kriptografi bukan satu-satunya bidang yang menggunakan istilah "aritmetika modular". Bidang ilmu teori informasi muncul pada akhir Perang Dunia II. Dalam kepemimpinan Claude Shannon, bidang tersebut menjadi cabang dari matematika terapan. Walau kerahasiaan adalah salah satu topik diskusi, reabilitas (keandalan) juga menjadi tema utama bidang tersebut. Richard Hamming membuat algoritma pertama pada tahun 1950. Sekali lagi, modulus bilangan buat digunakan teknik pengkodean sederhana seperti checksum. Pada tahun 1960, pengkodean yang lebih kuat dikembangkan, didasarkan pada polinomal dengan koefisien atas finite field. Aritmetika yang digunakan untuk objek tersebut umumnya menggunakan kata "modular".

Ilmu komputer menjadi kajian akademik pada awal tahun 1960. Batasan tak terhindarkan dari struktur prosesor mengharuskan bilangan direpresentasikan dalam bentuk bit yang terbatas; menjustifikasi penggunaan modulo. Istilah "aritmetika modular" sering muncul, kita bahkan dapat menemukan bilangan Gaussian atau polinomial, sebagai contoh, untuk kalkulasi bilangan bulat berukuran besar.

Teknik yang dikembangkan untuk kriptografi, teori kode, dan aritmetika komputer, didasarkan pada konsep yang sama, memberikan suatu kesatuan di matematika terkait teori informasi.

Objek dengan aritmetika modular

Kekongruenan bilangan bulat 

Penerapan aritmetika modular tertua ada pada bilangan bulat. Setelah menetapkan sebuah bilangan bulat , yang disebut dengan modulus, kekongruenan modulo n dilakukan dengan melakukan perhitungan terhadap sisa hasil pembagian bilangan-bilangan terhadap n. Dua bilangan bulat dikatakan kongruen modulo, jika selisih kedua bilangan tersebut merupakan kelipatan (yaitu, jika ada bilangan bulat  sehingga ).

Kekongruenan modulo n adalah sebuah relasi kekongruenan, artinya kekongruenan adalah relasi ekuivalensi yang kompatibel dengan operasi penambahan, pengurangan, dan perkalian. Kekongruenan modulo dilambangkan:

Tanda kurung mengartikan bahwa  berlaku untuk kedua ruas persamaan. Notasi ini berbeda dengan notasi  (tanpa tanda kurung), yang mengacu pada operasi modulus. Notasi  merujuk pada sebuah bilangan bulat unik  dengan  dan memenuhi  (Dengan kata lain, sisa  ketika dibagi dengan ).

Sebagai contoh, dalam modulus 12 seseorang dapat menyatakan bahwa , karena  merupakan kelipatan 12. Cara lain untuk menyatakannya adalah dengan mengatakan bahwa 38 dan 14 memiliki sisa yang sama, yakni 2, ketika dibagi dengan 12.

Himpunan  adalah himpunan semua bilangan bulat yang kongruen dengan a modulo n. Himpunan ini disebut kelas kekongruenan, kelas residu, atau cukup dengan residu dari a modulo n; dan dilambangkan dengan . Gauss berkontribusi dengan menganalisis struktur himpunan kelas kekongruenan ini, yang sekarang dikenal dengan gelanggang bilangan bulat modulo , dan dilambangkan , , atau . Namunn, notasi  tidak disarankan karena bisa disalahartikan dengan himpunan bilangan bulat adic-. Gelanggang   fundamental untuk berbagai cabang matematika (lihat  di bawah).

Gelanggang ini didefinisikan untuk  n > 0 sebagai:

Operasi penjumlahan, pengurangan, dan perkalian di  adalah analogi dari kekongruenan bilangan bulat:

 
 
 

Dalam hal ini,  adalah gelanggang komutatif. Misalnya, di gelanggang , dapat ditulis

seperti dalam aritmetika modular untuk sistem 24 jam.

Polinomial 

Gauss menyadari aritmetika modular juga dapat diterapkan pada himpunan polinomial dengan koefisien bilangan pecahan, karena himpunan tersebut memiliki penjumlahan, perkalian, dan pembagian Euklides. Kekongruenan pada himpunan ini didasarkan dari sisa hasil bagi Euklides sebuah polinomial dengan polinomial lain.

Gauss menerapkan pendekatan ini ke polinomial  dan menemukan faktor-faktor primitifnya, yang disebut dengan polinomial siklotomik. Hal ini digunakan untuk menemukan konstruksi penggaris dan jangka dari heptadekagon, sebuah poligon reguler dengan 17 sisi. Namun, ia ragu untuk menganggap penerapan ini termasuk dalam aritmetika; ia menulis: "Teori pembagian pada lingkaran, atau pada poligon reguler ..., bukan bagian dari aritmetika dengan sendirinya, namun prinsipnya didapatkan dari aritmetika tingkat lanjut".

Bilangan aljabar 

Pada kasus polinomial dengan koefisien bilangan bulat, sifat pembagian hanya berlaku untuk polinomial dengan koefisien derajat tersebesar bernilai 1 atau -1. Bagian ini membahas modulus berupa polinomial , dengan struktur modular yang didapatkan masih bagian dari gelanggangnya. Gelanggang ini berisi himpunan bilangan dalam bentuk , dengan  dan  berupa bilangan bulat dan  berupa unit bilangan imajiner, yang berkorespodensi dengan monomial . Himpunan tersebut dikenal sebagai bilangan

Sistem residu 
Setiap kelas residu modulo  dapat diwakili oleh salah satu anggotanya, meskipun biasanya mewakili setiap kelas residu dengan bilangan bulat nonnegatif terkecil yang termasuk dalam kelas (karena ini adalah sisa yang tepat yang dihasilkan dari pembagian). Dua anggota kelas residu yang berbeda modulo  adalah modulo tidak selaras . Selain itu, setiap bilangan bulat milik satu dan hanya satu kelas residu modulo .

Himpunan bilangan bulat  disebut modulo sistem residu terkecil . Setiap rangkaian bilangan bulat , tidak ada dua yang kongruen modulo , disebut modulo sistem residu lengkap .

Sistem residu terkecil adalah sistem residu lengkap, dan sistem residu lengkap hanyalah satu himpunan yang berisi tepat satu perwakilan dari setiap kelas residu modulo . Sebagai contoh. modulo 4 sistem residu terkecil adalah {0, 1, 2, 3}. Beberapa sistem residu lengkap lainnya modulo 4 meliputi:

{1, 2, 3, 4}
{13, 14, 15, 16}
{−2, −1, 0, 1}
{−13, 4, 17, 18}
{−5, 0, 6, 21}
{27, 32, 37, 42}

Beberapa set yang  bukan  sistem residu lengkap modulo 4 adalah:

{−5, 0, 6, 22}, karena 6 kongruen dengan 22 modulo 4.
{5, 15}, karena modulo 4 sistem residu lengkap harus memiliki tepat 4 kelas residu yang tidak selaras.

Sistem residu berkurang 

Fungsi total Euler , himpunan dari  bilangan bulat yang relative prime menjadi  dan saling tidak selaras di bawah modulus  disebut modulo sistem residu tereduksi . Himpunan {5,15} dari atas, misalnya, adalah turunan dari modulo 4 sistem residu tereduksi.

Perkembangan teoritis 
Dalam matematika, umum dijumpai sebuah konsep matematika yang dikembangkan dalam sebuah bidang, digunakan ulang pada bidang-bidang lain. Hal yang sama juga berlaku untuk aritmetika modular, yang membantu banyak bidang matematika murni, seperti aljabar dan teori Galois. Namun, perkembangan-perkembangan berikut tidak dianggapkan sebagai kasus khusus dari aritmetika modular, karena digunakan bersama konsep-konsep lainnya.

Struktur hasil bagi 

Dalam matematika modern, aritmetika modular diformalkan dengan menggunakan konsep Euclidean ring. Konsep relasi ekuivalensi memungkinkan aritmetika modular diterapkan ke banyak struktur aljabar. Sebagai contoh, hasil bagi sebuah grup dengan sebuah subgrup normal, dengan menggunakan teorema Jordan-Holder, adalah alat dasar untuk mengklasifikasikan grup hingga. Grup hasil bagi juga digunakan dalam topologi aljabar untuk mengelompokkan lipatan.

Sifat kekongruenan bilangan bulat 
Hubungan kekongruenan bilangan bulat dapat ditulis sebagai

yang secara eksplisit menunjukkan hubungannya dengan pembagian Euklides. Namun, suku  tersebut bukanlah sisa pembagian  oleh . Dalam pengartian yang lebih tepat,  bahwa  dan  memiliki sisa yang sama ketika dibagi dengan, yakni

dengan  adalah sisa pembagian keduanya. Mengurangkan kedua ekspresi diatas, kita dapat menemukan hubungan  sebelumnya, dengan memilih 

Definisi kekongruenan juga berlaku untuk nilai negatif. Sebagai contoh:

Sifat dasar 
Relasi kekongruenan pada bilangan bulat memenuhi semua kondisi relasi ekuivalensi. Dengan demikian, pada relasi kekongruenan  modulo  berlaku
 Sifat refleksif:  
 Sifat simetris: jika  maka 
 Sifat transitif: jika  dan , maka 
Untuk sebarang nilai . Lebih lanjut, operasi penjumlahan dan perkalian tetap berlaku pada relasi kekongruen modulo . Jika  memenuhi  dan , maka  dan  . Hal ini juga menyebabkan beberapa operasi lain tetap berlaku:
 Penjumlahan skalar:  dan 
Perkalian skalar: 
 Perpangkatan: , untuk bilangan bulat non-negatif 
 Untuk polinomial  dengan koefisien-koefisien bilangan bulat, berlaku 
Untuk operasi pencoretan (pembatalan) berlaku aturan berikut:
 Bentuk  dapat disederhanakan menjadi 
Bentuk  dapat disederhanakan menjadi 
 Untuk kasus  dan  saling koprima, bentuk  dapat disederhanakan menjadi 

Jika , belum tentu berlaku  . Hal tersebut hanya berlaku jika  koprima dengan  dan , dengan  adalah fungsi total Euler.

Invers perkalian 
Tidak semua relasi kekongruenan modulo  memiliki invers perkalian. Eksistensi bilangan bulat  (sehingga ) ada jika dan hanya jika  saling koprima dengan modulus . Secara khusus, jika  adalah bilangan prima maka  (yang terletak diantara ) akan selalu koprima dengan . Dalam kasus ini, invers perkalian kekongruenan modulo  ada untuk semua bilangan yang tidak kongruen dengan nol. Bilangan bulat  disebut invers perkalian modular dari  modulo . Berikut beberapa sifat invers perkalian modular:
 
 Jika  dan  ada, maka berlaku . Pada kasus , hal ini dapat digunakan untuk menunjukkan ketunggalan invers perkalian.
 Jika  dan  ada, maka solusi untuk kekongruenan linear tersebut adalah 

Invers perkalian invers   dapat cari secara efisien dengan menemukan nilai  pada Persamaan Bézout ; dengan menggunakan algoritme Euklides diperluas.

Sifat lain 
Berikut daftar beberapa hasil lebih lanjut terkait hubungan kekongruenan:
 Teorema kecil Fermat: Jika  adalah bilangan prima yang tidak membagi , maka .
 Teorema Euler: Jika  dan  koprima, maka , dengan  adalah fungsi total Euler
 Konsekuensi sederhana dari teorema kecil Fermat adalah jika  adalah bilangan prima, maka  adalah kebalikan perkalian dari . Lebih umum lagi, dari teorema Euler, jika  dan  adalah koprima, maka . 
 Konsekuensi sederhana lainnya adalah jika  dengan  adalah fungsi total Euler, maka  asalkan  adalah koprima dengan .
 Teorema Wilson:  is prime if and only if .
 Teorema sisa Cina: Untuk , , dan koprima , , maka  seperti  dan . Faktanya,   dimana  adalah kebalikan dari  modulo  dan  adalah kebalikan dari  modulo .
 Teorema Lagrange: Kesesuaian , dengan  adalah bilangan prima, dan  adalah polinomial dengan koefisien bilangan bulat , memiliki akar .
 Akar primitif modulo n: Bilangan  adalah akar primitif modulo , untuk bilangan bulat  koprima dengan , bilangan bulat  adalah . Sebuah root modulo  ada jika dan hanya jika  sama dengan  atau , dengan  adalah bilangan prima ganjil dan  adalah bilangan bulat positif. Jika aka4 modulo  primitif ada, maka persis ada  akar primitif, di mana  adalah fungsi total Euler.
 Residu kuadrat: Bilangan bulat  adalah modulo residu kuadrat , jika terdapat bilangan bulat  seperti yang . Kriteria Euler menegaskan bahwa, jika  adalah bilangan prima ganjil, dan  bukan kelipatan , maka  adalah modulo residu kuadrat  jika dan hanya jika

Aplikasi 
Dalam matematika teoretis, aritmatika modular adalah salah satu fondasi teori bilangan, menyentuh hampir setiap aspek studinya, dan itu juga digunakan secara luas dalam teori grup, teori gelanggang, teori simpul, dan aljabar abstrak. Dalam matematika terapan, ini digunakan dalam aljabar komputer, kriptografi, ilmu komputer, kimia dan visual dan seni musikal.

Aplikasi yang sangat praktis adalah menghitung checksum dalam pengenal bilangan deret. Misalnya, Nomor Buku Standar Internasional (ISBN) menggunakan aritmatika modulo 11 (untuk 10 digit ISBN) atau modulo 10 (untuk ISBN 13 digit) untuk deteksi kesalahan. Demikian juga, Nomor Rekening Bank Internasional (IBAN), misalnya, menggunakan aritmatika modulo 97 untuk melihat kesalahan input pengguna di nomor rekening bank. Dalam kimia, digit terakhir dari nomor registrasi CAS (nomor pengenal unik untuk setiap senyawa kimia) adalah digit pemeriksa, yang dihitung dengan mengambil digit terakhir dari dua bagian pertama Nomor CAS dikalikan 1, digit sebelumnya dikalikan 2, digit sebelumnya dikali 3 dll., menjumlahkan semua ini dan menghitung.

Dalam kriptografi, aritmatika modular secara langsung mendukung sistem kunci publik seperti RSA dan Diffie–Hellman, dan menyediakan finite field yang mendasari kurva elips, dan digunakan dalam berbagai algoritma kunci simetris termasuk Standar Enkripsi Lanjutan (AES), Algoritma Enkripsi Data Internasional (IDEA), dan RC4. RSA dan Diffie–Hellman menggunakan eksponen modular.

Dalam aljabar komputer, aritmatika modular biasanya digunakan untuk membatasi ukuran koefisien integer dalam penghitungan dan data menengah. Digunakan dalam faktorisasi polinomial, masalah di mana semua algoritma efisien yang diketahui menggunakan aritmatika modular. Digunakan oleh implementasi yang paling efisien dari algoritma pembagi persekutuan terbesar polinomial, eksak aljabar linear dan basis Gröbner di atas bilangan bulat dan bilangan rasional. Seperti yang diposting di Fidonet pada tahun 1980-an dan diarsipkan di Rosetta Code, aritmatika modular digunakan untuk menyangkal konjektur jumlah pangkat Euler pada Sinclair QL mikrokomputer menggunakan hanya seperempat dari presisi integer yang digunakan oleh CDC 6600 superkomputer untuk membantahnya dua dekade sebelumnya melalui pencarian brute force.

Dalam ilmu komputer, aritmatika modular sering diterapkan dalam operasi bitwise dan operasi lain yang melibatkan lebar tetap, struktur data siklik. Operasi modulo, seperti yang diterapkan di banyak bahasa pemrograman dan kalkulator, adalah aplikasi aritmetika modular yang sering digunakan dalam konteks. Operator logika XOR menjumlahkan 2 bit, modulo 2.

Contoh implementasi 

Di bawah ini adalah tiga fungsi C yang cukup cepat, dua untuk melakukan perkalian modular dan satu untuk eksponensial modular pada bilangan bulat tak bertanda yang tidak lebih besar dari 63 bit, tanpa luapan transien.

Cara algoritmik untuk menghitung :

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   if (!((a | b) & (0xFFFFFFFFULL << 32)))
       return a * b % m;

   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d >= m) d -= m;
       a <<= 1;
   }
   return d;
}

Pada arsitektur komputer di mana format presisi perpanjangan dengan setidaknya 64 bit mantissa tersedia (seperti tipe mo ganda panjang), the following routine is , dengan menggunakan trik yang, dengan perangkat keras, perkalian floating-point menghasilkan bit paling signifikan dari produk yang disimpan, sementara perkalian bilangan bulat menghasilkan bit yang paling tidak signifikan:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   long double x;
   uint64_t c;
   int64_t r;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}

Di bawah ini adalah fungsi C untuk melakukan eksponensial modular, yang menggunakan fungsi  yang diterapkan di atas.

Cara algoritmik untuk menghitung :

uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t r = m==1?0:1;
    while (b > 0) {
        if (b & 1)
            r = mul_mod(r, a, m);
        b = b >> 1;
        a = mul_mod(a, a, m);
    }
    return r;
}

Namun, agar semua rutinitas di atas bekerja,  tidak boleh melebihi 63 bit.

Lihat pula 

 Gelanggang Boolean
 Buffer melingkar
 Pembagian
 Bidang terbatas
 Simbol Legendre
 Eksponen modular
 Modulo (matematika)
 Grup perkalian bilangan bulat modulo n
 Periode Pisano (deret Fibonacci modulo  n )
 Modulo dasar primitif
 Timbal balik kuadrat
 Residu kuadrat
 Rekonstruksi rasional (matematika)
 Sistem residu pengurangan
 Aritmatika bilangan deret (kasus khusus aritmatika modular)
 Aljabar Boolean dua elemen
 Topik yang berkaitan dengan teori grup di balik aritmatika modular:
 Grup siklik
 Grup perkalian bilangan bulat modulo n
 Teorema penting lainnya yang berkaitan dengan aritmatika modular:
 Teorema Carmichael
 Teorema sisa Cina
 Teorema Euler
 Teorema kecil Fermat (kasus khusus dari teorema Euler)
 Teorema Lagrange
 Lemma Thue

Catatan

Referensi 
 John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
 . See in particular chapters 5 and 6 for a review of basic modular arithmetic.
 Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.3: Modular arithmetic, pp. 862–868.
 Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. .

Pranala luar 
 Dalam modular art artikel, seseorang dapat mempelajari lebih lanjut tentang aplikasi aritmatika modular dalam seni.
 An article tentang aritmatika modular di wiki GIMPS
 Modular Arithmetic and patterns in addition and multiplication tables

 
Gelanggang hingga
Teori grup
Artikel dengan contoh kode C