Algoritma Euclid

Mon 4 Mar 2013 - 0:26

karena ndak bisa-bisa menyelesaikan kasus, ya udah deh coba posting apa yang pernah ku dapet di kelas..

ALGORITMA EUCLID

Ketika SD kita dikenalkan FPB(faktor Persekutuan terbesar), atau dalam bahasa inggrisnya greatest common divisor(GCD). GCD ini dalam ilmu kriptografi sering diganakan dalam algoritma asismetris (ada kunci privat dan ada kunci publik), seperti algoritma RSA untuk mencari sebuah bilangan bulat sehingga gcd nya 1.
salah satu algoritma untuk mencari GCD dari 2 bilangan bulat adalah algoritma euclid. Algoritma ini didasarkan pada pernyataan berikut ini. Misalkan diberikan a dan b dengan a>b . untuk menghitung gcd(a,b) , berikut algoritmanya:

a=q_1×b + r_1

b=q_2×r_1+r_2

r_1=q_3×r_2+r_3

…

r_(n-1)=q_(n+1)×r_n+r_(n+1)

r_n=q_(n+2)×r_(n+1)

Diperoleh, gcd⁡(a,b)=r_(n+1)

Contoh:

Akan dihitung gcd⁡(40,24)

Jawab:
40=1× 24 +16
24=1×16 +8
16=2× 8
Jadi, gcd⁡(40,24)=8