Aritmetika modular

Dalam matematika, aritmetika modular adalah sistem aritmetika untuk bilangan bulat, di mana angka "membungkus" saat mencapai nilai tertentu, yang disebut modulus. Pendekatan modern untuk aritmatika modular dikembangkan oleh Carl Friedrich Gauss dalam bukunya Disquisitiones Arithmeticae , yang diterbitkan pada tahun 1801.

Penggunaan yang umum dari aritmatika modular adalah dalam sistem 12-jam, di mana hari dibagi menjadi dua periode 12-jam. Jika sekarang jam 7:00, maka 8 jam kemudian menjadi 3:00. Penambahan sederhana akan menghasilkan 7 + 8 = 15, tapi jam "berputar" setiap 12 jam. Karena angka jam dimulai kembali setelah mencapai 12, ini adalah aritmetika modulo 12. Dalam definisi di bawah, 15 adalah kongruen dengan 3 modulo 12, jadi "15:00" pada 24 jam ditampilkan "3:00" pada format 12 jam.

Sejarah

Asal mula

Laman judul edisi 1621 Aritmatika karya Diofantos, diterjemahkan ke dalam bahasa Latin oleh Claude Gaspard Bachet de Méziriac.

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^[1] dalam proposisi 36 pada bukunya ke-9.^[2] 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 $4n+3$ . 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?".^[3]

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.^[4] 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.^[5]

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.^[6] Persamaan Diofantin derajat dua dipelajari Brahmagupta (598 - 668).^[7] 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,^[8] dan menciptakan penemuan baru. Hal ini termasuk studi mengenai sifat dari himpunan bilangan, seperti prima, sempurna, ramah (amicable), dan poligonal.^[9] Dalam konteks ini, Qusta bin Lûqâ melakukan terjemahan parsial buku Arithmetica milik Diofantos dari Alexandria, di akhir abad ke-9.^[9] Pada masa yang sama, Al-Hajjaj menerjemahkan Elemen milik Euclid.^[10] Koleganya, Al-Kharizmi (sekitar 783 - 850), menulis buku mengenai numerisasi. Terjemahan bahasa Latin dari buku ini adalah Algoritmi de numero Indorum.^[11] Tsabit bin Qurrah (836-901) mempelajari bilangan amicable dan bilangan sempurna.^[12] Ibnu Haitham (965 - 1039) melanjutkan hasil kerjanya dan menemukan teorema Wilson.^[13]

Perkembangan di Eropa

Pierre de Fermat banyak berkontribusi mengembangkan aritmatika. Sifat-sifat pembagian Euklides, dasar dari aritmatika modular, banyak digunakan oleh matematikawan saat ini.

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".^[14] 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 $x^{2}+2y^{2}$ .

Alat dalam aritmetika modular

Kekongruenan bilangan bulat

Bilangan bulat $n > 1$ , disebut 'modulus' , dua bilangan bulat dikatakan kongruen modulo $n$ , jika $n$ adalah pembagian dari perbedaannya (yaitu, jika ada bilangan bulat $k$ sehingga $a - b = kn$ ).

Modulo kekongruenan $n$ adalah relasi kekongruenan, artinya ini adalah relasi ekuivalensi yang kompatibel dengan operasi penambahan, pengurangan, dan perkalian. Modulo kekongruenan $n$ dilambangkan:

a\equiv b{\pmod {n}}.

Tanda kurung berarti bahwa $(mod n)$ berlaku untuk seluruh persamaan, tidak hanya di ruas kanan (di sini $b$ ). Notasi ini jangan disamakan dengan notasi $b mod n$ (tanpa tanda kurung), yang mengacu pada operasi modulo. Maka, $b mod n$ menunjukkan bilangan bulat unik $a$ sehingga $0 \leq a < n$ dan $a\equiv b\;({\text{mod}}\;n)$ (misalnya sisa $b$ jika dibagi dengan $n$ ^[15]).

Hubungan kekongruenan dapat ditulis ulang sebagai

a=kn+b,

secara eksplisit menunjukkan hubungannya dengan pembagian Euklides. Namun, $b$ tidak menjadi sisa dari pembagian $a$ oleh $n .$ Sebagai gantinya, pernyataan $a \equiv b (mod n)$ bahwa $a$ dan $b$ memiliki sisa yang sama jika dibagi dengan $n$ adalah,

a=pn+r,

b=qn+r,

dimana $0 \leq r < n$ adalah sisa umum. Dengan mengurangkan dua ekspresi ini, kami memulihkan hubungan sebelumnya:

a-b=kn,

dengan menyetel $k = p - q .$

Contoh

Dalam modulus 12, seseorang dapat menyatakan bahwa:

38\equiv 14{\pmod {12}}

karena $38 - 14 = 24$ , yang merupakan kelipatan 12. Cara lain untuk menyatakannya adalah dengan mengatakan bahwa 38 dan 14 memiliki sisa 2 yang sama, jika dibagi 12.

Definisi kekongruenan juga berlaku untuk nilai negatif. Sebagai contoh:

{\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}

Sifat

Relasi kesesuaian memenuhi semua kondisi dari relasi ekuivalensi:

Refleksivitas: $a \equiv a (mod n)$
Simetri: $a \equiv b (mod n)$ jika $b \equiv a (mod n)$ untuk $a$ , $b$ , dan $n$ .
Transitivitas: Jika $a \equiv b (mod n)$ dan $b \equiv c (mod n)$ , maka $a \equiv c (mod n)$

Jika $a 1 \equiv b 1 (mod n)$ dan $a 2 \equiv b 2 (mod n),$ atau jika $a \equiv b (mod n),$ maka:

$a + k \equiv b + k (mod n)$ untuk bilangan bulat $k$ (kompatibilitas dengan translasi)
$k a \equiv k b (mod n)$ untuk bilangan bulat $k$ (kompatibilitas dengan penskalaan)
$a 1 + a 2 \equiv b 1 + b 2 (mod n)$ (kompatibilitas dengan tambahan)
$a 1 - a 2 \equiv b 1 - b 2 (mod n)$ (kompatibilitas dengan pengurangan)
$a 1 a 2 \equiv b 1 b 2 (mod n)$ (kompatibilitas dengan perkalian)
$a k \equiv b k (mod n)$ untuk bilangan bulat non-negatif $k$ (kompatibilitas dengan eksponen)
$p (a) \equiv p (b) (mod n)$ , untuk polinomial $p (x)$ dengan koefisien integer (kompatibilitas dengan evaluasi polinomial)

Jika $a \equiv b (mod n)$ , maka umumnya $k a \equiv k b (mod n)$ . Namun, hal berikut ini benar:

Jika $c \equiv d (mod φ (n)),$ dengan $φ$ adalah fungsi total Euler, lalu asalkan $a$ koprima dengan $n$ - $a c \equiv a d (mod n)$ .

Untuk pembatalan istilah umum, kami memiliki aturan berikut:

Jika $a + k \equiv b + k (mod n)$ , dengan $k$ adalah sembarang bilangan bulat, lalu $a \equiv b (mod n)$
Jika $k a \equiv k b (mod n)$ dan $k$ koprima dengan $n$ , maka $a \equiv b (mod n)$
Jika $k a \equiv k b (mod kn)$ , maka $a \equiv b (mod n)$

Perkalian modular invers ditentukan oleh aturan berikut:

Eksistensi: ada bilangan bulat yang dilambangkan $a -1$ seperti $aa -1 \equiv 1 (mod n)$ jika dan hanya jika $a$ sesuai dengan $n$ . Bilangan bulat $a -1$ disebut perkalian modular invers dari $a$ modulo $n$ .
Jika $a \equiv b (mod n)$ dan $a -1$ , maka $a -1 \equiv b -1 (mod n)$ (kompatibilitas dengan pembalikan perkalian, dan jika $a = b$ , modulo $n$ )
Jika $a x \equiv b (mod n)$ dan $a$ koprima dengan $n$ , maka solusi untuk kekongruenan linear ini diberikan oleh $x \equiv a -1 b (mod n)$

Perkalian invers $x \equiv a -1 (mod n)$ dapat dihitung secara efisien dengan menyelesaikan Persamaan Bézout $ax+ny=1$ untuk $x,y$ , menggunakan algoritme Euklides diperluas.

Secara khusus, jika $p$ adalah bilangan prima, maka $a$ coprima dengan $p$ untuk $a$ sehingga $0 < a < p$ ; sehingga invers perkalian ada untuk semua $a$ yang tidak kongruen dengan nol modulo $p$ .

Beberapa properti lanjutan dari hubungan kesesuaian adalah sebagai berikut:

Teorema kecil Fermat: Jika $p$ adalah bilangan prima dan tidak membagi $a$ , maka $a p - 1 \equiv 1 (mod p)$ .
Teorema Euler: Jika $a$ dan $n$ koprima, maka $a φ (n) \equiv 1 (mod n)$ , dengan $φ$ adalah fungsi total Euler
Konsekuensi sederhana dari teorema kecil Fermat adalah jika $p$ adalah bilangan prima, maka $a -1 \equiv a p - 2 (mod p)$ adalah kebalikan perkalian dari $0 < a < p$ . Lebih umum lagi, dari teorema Euler, jika $a$ dan $n$ adalah koprima, maka $a -1 \equiv a φ (n) - 1 (mod n)$ .
Konsekuensi sederhana lainnya adalah jika $a \equiv b (mod φ (n)),$ dengan $φ$ adalah fungsi total Euler, maka $k a \equiv k b (mod n)$ asalkan $k$ adalah koprima dengan $n$ .
Teorema Wilson: $p$ is prime if and only if $(p - 1)! \equiv -1 (mod p)$ .
Teorema sisa Cina: Untuk $a$ , $b$ , dan koprima $m$ , $' 'n' '$ , maka $x (mod mn)$ seperti $x \equiv a (mod m)$ dan $x \equiv b (mod n)$ . Faktanya, $x \equiv b m n -1 m + a n m -1 n (mod mn)$ dimana $m n -1$ adalah kebalikan dari $m$ modulo $n$ dan $n m -1$ adalah kebalikan dari $n$ modulo $m$ .
Teorema Lagrange: Kesesuaian $f (x) \equiv 0 (mod p)$ , dengan $p$ adalah bilangan prima, dan $f (x) = a 0 x n + ... + a n$ adalah polinomial dengan koefisien bilangan bulat $a 0 \neq 0 (mod p)$ , memiliki akar $n$ .
Akar primitif modulo n: Bilangan $g$ adalah akar primitif modulo $n$ , untuk bilangan bulat $a$ koprima dengan $n$ , bilangan bulat $k$ adalah $g k \equiv a (mod n)$ . Sebuah root modulo $n$ ada jika dan hanya jika $n$ sama dengan $2, 4, p k$ atau $2 p k$ , dengan $p$ adalah bilangan prima ganjil dan $k$ adalah bilangan bulat positif. Jika aka4 modulo $n$ primitif ada, maka persis ada $φ (φ (n))$ akar primitif, di mana $φ$ adalah fungsi total Euler.
Residu kuadrat: Bilangan bulat $a$ adalah modulo residu kuadrat $n$ , jika terdapat bilangan bulat $x$ seperti yang $x 2 \equiv a (mod n)$ . Kriteria Euler menegaskan bahwa, jika $p$ adalah bilangan prima ganjil, dan $a$ bukan kelipatan $p$ , maka $a$ adalah modulo residu kuadrat $p$ jika dan hanya jika

a^{(p-1)/2}\equiv 1{\pmod {p}}.

Kelas kekongruenan

Seperti relasi kesesuaian lainnya, kekongruenan modulo $n$ adalah relasi ekuivalensi, dan ekuivalen dari bilangan bulat $a$ , dilambangkan dengan $a n$ , adalah himpunan ${\dots , a - 2 n, a - n, a, a + n, a + 2 n, \dots}$ . Himpunan ini, terdiri dari semua bilangan bulat yang kongruen dengan $a$ modulo $n$ , disebut kelas kekongruenan, kelas residu, atau hanya residu dari bilangan bulat $a$ modulo $n$ . Ketika modulus $n$ diketahui dari konteksnya, residu ini dilambangkan $[a]$ .

Sistem residu

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

Himpunan bilangan bulat ${0, 1, 2, \dots, n - 1}$ disebut modulo sistem residu terkecil $' 'n' '$ . Setiap rangkaian bilangan bulat $n$ , tidak ada dua yang kongruen modulo $n$ , disebut modulo sistem residu lengkap $' 'n' '$ .

Sistem residu terkecil adalah sistem residu lengkap, dan sistem residu lengkap hanyalah satu himpunan yang berisi tepat satu perwakilan dari setiap kelas residu modulo $n$ .^[18] 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 $φ(n)$ , himpunan dari $φ(n)$ bilangan bulat yang relative prime menjadi $n$ dan saling tidak selaras di bawah modulus $n$ disebut modulo sistem residu tereduksi $n$ .^[19] Himpunan {5,15} dari atas, misalnya, adalah turunan dari modulo 4 sistem residu tereduksi.

Bilangan bulat modulo n

Himpunan dari semua kelas kekongruenan dari bilangan bulat untuk modulus $n$ disebut gelanggang bilangan bulat modulo $n$ ,^[20] dan dilambangkan ${\textstyle \mathbb {Z} /n\mathbb {Z} }$ , $\mathbb {Z} /n$ , atau $\mathbb {Z} _{n}$ .^[15]^[21] Notasi $\mathbb {Z} _{n}$ adalah, bagaimanapun, tidak disarankan karena bisa disalahartikan dengan himpunan bilangan bulat adic- $n$ . Gelanggang $\mathbb {Z} /n\mathbb {Z}$ adalah fundamental untuk berbagai cabang matematika (lihat § Aplikasi di bawah).

Himpunan ditentukan untuk n > 0 sebagai:

\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n{-}1}}_{n}\right\}.

(Maka $n = 0$ , $\mathbb {Z} /n\mathbb {Z}$ bukan merupakan himpunan kosong; sebaliknya, isomorfik menjadi $\mathbb {Z}$ , maka $a 0 = {a}$ .)

Kami mendefinisikan penjumlahan, pengurangan, dan perkalian di $\mathbb {Z} /n\mathbb {Z}$ dengan aturan berikut:

${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}$
${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}$
${\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.$

Verifikasi bahwa ini adalah definisi yang tepat menggunakan properti yang diberikan sebelumnya.

Maka, $\mathbb {Z} /n\mathbb {Z}$ menjadi gelanggang komutatif. Misalnya, di gelanggang $\mathbb {Z} /24\mathbb {Z}$ , maka

{\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}

seperti dalam aritmatika untuk sistem 24 jam.

Kami menggunakan notasi $\mathbb {Z} /n\mathbb {Z}$ karena ini adalah gelanggang hasil bagi dari $\mathbb {Z}$ oleh ideal $n\mathbb {Z}$ , satu set yang berisi semua bilangan bulat habis dibagi oleh $n$ , di mana $0\mathbb {Z}$ adalah himpunan singleton ${0}$ . Jadi $\mathbb {Z} /n\mathbb {Z}$ adalah bidang $n\mathbb {Z}$ adalah ideal maksimal (yaitu, jika $n$ adalah bilangan prima).

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.^[22]

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 $a\cdot b{\pmod {m}}$ :^[23]

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 ^{[butuh klarifikasi]}, 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:^{[butuh rujukan]}

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 $mul_mod$ yang diterapkan di atas.

Cara algoritmik untuk menghitung $a^{b}{\pmod {m}}$ :

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, $m$ 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

^ Heath, Thomas (1911). "The thirteen books of Euclid's Elements". The Mathematical Gazette. 6 (92): 98–101.
^ "Euclid's Elements, Book IX, Proposition 36". mathcs.clarku.edu. Diakses tanggal 2021-02-09.
^ Martzloff, Jean-Claude. (1988). Histoire des mathématiques chinoises. Impr. Louis-Jean). Paris: Masson. hlm. 129. ISBN 2-225-81265-9. OCLC 416811520.
^ Chen, Joseph C. Y. (1996-03-01). Early Chinese Work in Natural Science: A Re-examination of the Physics of Motion, Acoustics, Astronomy and Scientific Thoughts (dalam bahasa Inggris). Hong Kong University Press. hlm. 224. ISBN 978-962-209-385-0.
^ Chemla, Karine (1994). "Similarities between chineese and arabic mathematical writings : (I) root extraction". Arabic Sciences and Philosophy. 4 (2): 207–266.
^ Agathe Keller. Un commentaire indien du VIIème siècle, Bhâskara et le ganitapada de l’aryabhatiya. Histoire, Philosophie et Sociologie des sciences. Université Paris 7 - Denis Diderot, 2000. Français. ffhalshs-00006349f
^ Sarasvati, S. S. Prakash (1986). A critical study of Brahmagupta and his works. Delhi.
^ Pinès, Shlomo (1986). Studies in Arabic versions of Greek texts and in Medieval science. Leiden.
^ ^a ^b L'âge d'or des sciences arabes : exposition présentée à l'Institut de monde arabe, Paris, 25 octobre 2005-19 mars 2006. Alaoui, Brahim., Institut du monde arabe (France). [Arles]: Actes Sud. 2005. ISBN 2-7427-5672-8. OCLC 317446627.
^ Berggren, John Lennart (1986). Episodes in the Mathematics of Medieval Islam. Springer. hlm. 70–71.
^ Crossley, John; Henry, Alan (1990). "Thus Spake al-Khwārizimī: A Translation of the Text of Cambridge University Library Ms. li.vi.5". Historia Mathematica. 17: 103–131.
^ Carmody, Francis J. (1941). Thabit b. Qurra, Four Astronomical Tracts in Latin. Berkeley.
^ Rashed, Roshdi (1980). "Ibn al-haytham et le théorème de Wilson". Archive for History of Exact Sciences. 22 (4): 305–321.
^ Fermat, Korespodensi, sebuah surat kepada Marin Mersenne, 25 Desember 1640.
^ ^a ^b "Comprehensive List of Algebra Symbols". Math Vault (dalam bahasa Inggris). 2020-03-25. Diakses tanggal 2020-08-12.
^ Weisstein, Eric W. "Modular Arithmetic". mathworld.wolfram.com (dalam bahasa Inggris). Diakses tanggal 2020-08-12.
^ (Pettofrezzo & Byrkit 1970, hlm. 90)
^ (Long 1972, hlm. 78)
^ (Long 1972, hlm. 85)
^ Ini adalah gelanggang, ditunjukkan di bawah.
^ "2.3: Integers Modulo n". Mathematics LibreTexts (dalam bahasa Inggris). 2013-11-16. Diakses tanggal 2020-08-12.
^ "Euler's sum of powers conjecture". rosettacode.org (dalam bahasa Inggris). Diakses tanggal 2020-11-11.
^ Kode ini menggunakan notasi literal C untuk bilangan heksadesimal panjang tanpa tanda, yang diakhiri dengan ULL . Lihat juga bagian 6.4.4 dari spesifikasi bahasa n1570.

Referensi

John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001 . 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. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3.
Long, Calvin T. (1972). Elementary Introduction to Number Theory (edisi ke-2nd). Lexington: D. C. Heath and Company. LCCN 77171950.
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory . Englewood Cliffs: Prentice Hall. LCCN 71081766.
Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Pranala luar

Hazewinkel, Michiel, ed. (2001) [1994], "Congruence", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
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

Templat:Teori bilangan

[1] Heath, Thomas (1911). "The thirteen books of Euclid's Elements". The Mathematical Gazette. 6 (92): 98–101.

[2] "Euclid's Elements, Book IX, Proposition 36". mathcs.clarku.edu. Diakses tanggal 2021-02-09.

[3] Martzloff, Jean-Claude. (1988). Histoire des mathématiques chinoises. Impr. Louis-Jean). Paris: Masson. hlm. 129. ISBN 2-225-81265-9. OCLC 416811520.

[4] Chen, Joseph C. Y. (1996-03-01). Early Chinese Work in Natural Science: A Re-examination of the Physics of Motion, Acoustics, Astronomy and Scientific Thoughts (dalam bahasa Inggris). Hong Kong University Press. hlm. 224. ISBN 978-962-209-385-0.

[5] Chemla, Karine (1994). "Similarities between chineese and arabic mathematical writings : (I) root extraction". Arabic Sciences and Philosophy. 4 (2): 207–266.

[6] Agathe Keller. Un commentaire indien du VIIème siècle, Bhâskara et le ganitapada de l’aryabhatiya. Histoire, Philosophie et Sociologie des sciences. Université Paris 7 - Denis Diderot, 2000. Français. ffhalshs-00006349f

[7] Sarasvati, S. S. Prakash (1986). A critical study of Brahmagupta and his works. Delhi.

[8] Pinès, Shlomo (1986). Studies in Arabic versions of Greek texts and in Medieval science. Leiden.

[:1-9] L'âge d'or des sciences arabes : exposition présentée à l'Institut de monde arabe, Paris, 25 octobre 2005-19 mars 2006. Alaoui, Brahim., Institut du monde arabe (France). [Arles]: Actes Sud. 2005. ISBN 2-7427-5672-8. OCLC 317446627.

[10] Berggren, John Lennart (1986). Episodes in the Mathematics of Medieval Islam. Springer. hlm. 70–71.

[11] Crossley, John; Henry, Alan (1990). "Thus Spake al-Khwārizimī: A Translation of the Text of Cambridge University Library Ms. li.vi.5". Historia Mathematica. 17: 103–131.

[12] Carmody, Francis J. (1941). Thabit b. Qurra, Four Astronomical Tracts in Latin. Berkeley.

[13] Rashed, Roshdi (1980). "Ibn al-haytham et le théorème de Wilson". Archive for History of Exact Sciences. 22 (4): 305–321.

[14] Fermat, Korespodensi, sebuah surat kepada Marin Mersenne, 25 Desember 1640.

[:0-15] "Comprehensive List of Algebra Symbols". Math Vault (dalam bahasa Inggris). 2020-03-25. Diakses tanggal 2020-08-12.

[16] Weisstein, Eric W. "Modular Arithmetic". mathworld.wolfram.com (dalam bahasa Inggris). Diakses tanggal 2020-08-12.

[17] (Pettofrezzo & Byrkit 1970, hlm. 90)

[18] (Long 1972, hlm. 78)

[19] (Long 1972, hlm. 85)

[20] Ini adalah gelanggang, ditunjukkan di bawah.

[21] "2.3: Integers Modulo n". Mathematics LibreTexts (dalam bahasa Inggris). 2013-11-16. Diakses tanggal 2020-08-12.

[22] "Euler's sum of powers conjecture". rosettacode.org (dalam bahasa Inggris). Diakses tanggal 2020-11-11.

[23] Kode ini menggunakan notasi literal C untuk bilangan heksadesimal panjang tanpa tanda, yang diakhiri dengan ULL . Lihat juga bagian 6.4.4 dari spesifikasi bahasa n1570.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]