Öklid algoritması
Kısa tanım
İki tam sayının en büyük ortak bölenini, büyük sayıyı küçüğe art arda bölüp kalanla devam ederek bulan eski ve hızlı yöntemdir.
Diğer adları: Bölme algoritması
Antik Yunan matematikçisi Öklid'in Elemanlar kitabında anlattığı bu yöntem, bugün hâlâ bilgisayarların en çok kullandığı algoritmalardan biridir. Amacı iki tam sayının en büyük ortak bölenini (EBOB) asal çarpanlara ayırmadan bulmaktır.
Nasıl çalışır?
Temel fikir şudur: EBOB(a, b) = EBOB(b, a mod b). Büyük sayıyı küçüğe bölersin, kalanı alırsın; sonra bölen ile kalanla aynı işlemi tekrarlarsın. Kalan sıfır olduğunda son bölen aradığın EBOB'dur.
Örnek: EBOB(252, 105) için 252 = 2 × 105 + 42, ardından 105 = 2 × 42 + 21, son olarak 42 = 2 × 21 + 0. Kalan sıfır olduğu anda bölen 21'dir, yani EBOB 21'dir. Aynı sonucu asal çarpanlarla bulmak (252 = 2² × 3² × 7, 105 = 3 × 5 × 7) daha uzun sürer, büyük sayılarda ise neredeyse imkânsızlaşır.
Nerelerde kullanılır?
EBOB bulunduktan sonra EKOK da kolayca hesaplanır: EKOK(a, b) = a × b / EBOB(a, b). Kesirleri sadeleştirmek, dişli ya da takvim döngülerinin ne zaman çakışacağını bulmak bu ikilinin tipik kullanımıdır; EBOB EKOK hesaplama aracı adımları gösterir. Genişletilmiş Öklid algoritması ise modüler ters bulmaya yarar ve RSA gibi şifreleme sistemlerinin temelinde yer alır; bu konuya modüler üs alma ile birlikte bakabilirsin.
Algoritmanın gücü, adım sayısının sayıların basamak sayısıyla orantılı kalmasıdır; yüzlerce basamaklı sayılarda bile birkaç yüz bölmede sonuca ulaşır.