Quadratic Residues Modulo

Halo, tahukah pembaca mengenai suatu operasi matematika bernama modulo? penulis sedikit penasaran dengan esensi dari modulo ini, jadi aja pengen langsung tulis aja biar bisa dishare kan lumayan nih. Yuk langsung masuk aja
Postingan ini terinspirasi dari kuliah teori komputasi dari lab ilmu rekayasa dan komputasi #seremgatuh. Jadi selidik demi selidik, operasi modulo ini cukup unik, kenapa? coba pembaca cek deh di kalkulator, gimana caranya ngoperasiin modulo. Saya sempet mikir lama dan searching di google bahkan buat nyari gimana caranya ngoperasiin modulo di kalkulator.

Jadi gini ceritanya, ketika di kelas saya nemu soal coba hitung modulo dari -2 dan 13. saya bingung kan, apa sih esensi dari modulo #gilabahasanya. Apa sih arti dari modulo itu, kalo jawaban dari -2 modulo 13 itu 11, gimana sih caranya? Cukup aneh juga soalnya baru kepikiran sekarang kenapa baru mikir apa sih arti dari modulo kaya yang ga pernah diajarin aja. Ternyata gampang aja, modulo itu bukan selisih, tapi merupakan sisa. Ibarat kita punya 7 potong pizza, trus harus dibagiin ke 10 orang, nah 7 modulo 10 itu tetep 7, karena si pemilik pizza sunggu sangat ikhlas dan penyayangnya sehingga tidak ingin ada anggota yang ga kebagian pizza, jadinya potongan pizzanya tetep disisain 7. Jadi 7 modulo 10 itu tetep 7. Kasus yang sama juga jika potongan pizzanya ada 14, maka setiap orang bakal dikasih 1 dan 4 potongan sisanya ga dibagiin ke siapa-siapa. Jadi 14 modulo 10 itu 4, itulah cerita-cerita khayalan yang bisa diangkat.

Nah simpel gitu kan, gimana kalo ada bilangan negatif misalnya -2 modulo 13? Secara teori dan konsep, modulo itu adalah bilangan antara 0 dan bilangan yang nge-modulo-in itu dikurangi 1 (bahasa apa itu). Jadi misal modulo 13, berarti hasilnya pasti di antara 0 dan 12, ga mungkin 13 lah ya. kalo bilangan negatif (asal pikirannya ga negatif pasti gampang), kita tambahkan dia dengan bilangan si modulo itu, misal -2 kita tambah dengan 13 jadi 11. Nah baru deh kita hitung 11 modulo 13 yaitu hasilnya 11.

Lanjut lagi… Sekarang makin susah nih, ada yang namanya quadratic residues modulo (aduh bahasanya).

Berikut adalah pembahasan quadratic residues modulo. Makhluk apaan coba? dari namanya itu quadratic artinya sesuatu kuadrat-kuadrat, kemudian ada residues modulo yaitu sisa modulo. Jadi kalo digabungin ya kuadrat-kuadrat sisa modulo gitu (apa sih?). Jadi artinya tuh, bilangan antara 0 sampai bilangan x dikurangi 1, yang merupakan bilangan modulo dari perkalian kuadrat antara 0 sampai bilangan x dikurangi 1 itu juga (what the hell on earth is that?). X yang dimaksud disini adalah nilai yang kita inginkan, apapun itu.

Misal kita ambil aja berapa quadratic residues dari 3? Berarti kita cari antara 0 sampai 2 berapa sisa modulo kuadratnya.

Jadi kita bakal dapet kalo:

1 kuadrat modulo 3 = 1

2 kuadrat modulo 3 = 1

Udah cukup sampe 2 aja kan x dikurangi 1 menurut teorinya tuh. Jadi quadratic residues modulo dari 3 itu cuma bilangan 1 aja gitu.

Nah bakal tambah seru lagi kalo coba cari quadratic residues modulo dari 13 atau 30 atau 100 gituh, nah tambah repot kan makanya biar gampang mari kita bikin code nya saja. Berikut saya lampirkan gambar mengenai kodingan yang siapa tau bermanfaat untuk mencari quadratic residues modulo.

Selamat menikmati!


					
Advertisements