Co Prime

Waktu mau belajar Algoritma Asimetri RSA, diriku menemukan kata-kata relatif prima. Kurang lebih kata-katanya gini " kemudian secara acak... pilihlah kunci enkripsi e, sedemikan sehingga e dan (p-1)(q-1) relatif prima" Maksudnya??? kenapa tiba-tiba muncul angka ajaib yang entah dari mana... :(

Segeralah dirikuw mencari dosen matematika, pak Memen, tanpa pikir panjang alias panik ga tanya om2 onliners dulu...
Pak maksudnya relatif prima apa ya pak? Hmmm mana contohnya kata pak Memen... ini pak? Wajah pak memen tiba-tiba jadi bingung juga melihat angka ajaib yang muncul...(kekekekkkk pak memen bingung apalagi akuw... mana tuh contoh gede banget lagi angka-ngkanya). Alhasil pak memen bilang gini, gimana kalo besok saya kasih ibu jawabannya... ibu butuh besok ya? :D "iya pak"



Malamnya berkeluh-kesahlah diriku pada suami tercinta (hihihi) betapa tidak siapnya dirikuw untuk mengajar besok. Oh untungnya-untungnya suamiku berpikir lebih panjang, dia mencari tau maknanya di wikipedia.... eits ketemu versi indonesia yang singkat n ngga padat, tapi mari kita lihat versi englishnya...

Nah ternyata dan ternyata sebuah fakta sederhana terungkap oleh si katak dalam tempurung ini (aku maksudnya :D)
a dan b dikatakan relatif prima bila tidak memiliki faktor yang sama selain 1, atau jika pembagi bersama terbesar (greatest common divisor /gcd) sama dengan 1
Contoh :
6 dan 35 adalah relative prima
6 dan 27 tidak relative prima karena sama-sama bisa dibagi dengan 3

Kenapa diriku begitu panik untuk mengetahui itu saja... (hmm mungkin karena RSA nya sendiri ga sesederhana itu ya, masih ada tahap2an lainnya, ahhh ngeles aja nih :D)
nah buat menentukan sepasang angka itu relatif prima atau tidak cara tercepatnya adalah menggunakan Euclidean Algorithm (kalo angkanya gede butuh ini tapi kalo angkanya kaya contoh barusan mah kagak usah kali... kecuali kalo matematika kamu payah banget... hihihi...)

Algoritma Euclidean sebetulnya buat menentukan greatest common divisor/gcd... ato kalo bahasa sekolah kita dulu faktorial terbesar..
kalo pake tehnik rekursif begini nih algoritmanya
function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)

Contoh : gcd (1071, 1029) = 21
a b explanations
1071 1029 The initial arguments
1029 42 The second argument is 1071 mod 1029
42 21 The second argument is 1029 mod 42
21 0 The second argument is 42 mod 21
21 Since b = 0 we return a

nah kalo sampe return terakhirnya adalah 1, it means a dan b CoPrime
Gitu aja....
Cuma mau cerita itu aja pembukanya panjang bener ya :D, pake ngomongin pak memen lagi... hihihi maaf pak memen, contoh soal RSA dari buku bapak esok harinya membuat pemahaman mahasiswa saya lebih baik pak... n Terimakasih juga hubby... i love you ;)