Kriptolojinin Antik Dönemde Atılan Temelleri: Eratosthenes Kalburu

Kriptolojinin Antik Dönemde Atılan Temelleri: Eratosthenes Kalburu 

Kriptografi kelimesi Yunanca gizli anlamına gelen “kripto” ve yazı anlamına gelen “graphi” dan türetilmiştir. Şifre bilimi olarak da adlandırabileceğimiz kriptoloji;  4000 yıl önce Mısırlı bir katibin efendisini anlatmak için hiyeroglifleri şifreleyerek kullanmasıyla oluşmuştur. Ortaya çıktığı ilk 3000 yıl gelişemeyen kriptografi dünyanın farklı yerlerinde en temel şekliyle kullanılmıştır… Bu dönemi incelediğimiz de karşımıza Öklid, Al-Kindi, Eratosthenes vb. bilim insanları çıkmaktadır. Bu yazımızda Eratosthenes Kalburu’nu, işleyişini ve asal sayıları inceleyeceğiz. 

1’den büyük olan, yalnızca 1’e ve kendisine bölünebilen sayılara asal sayı denir. Bu klasik tanım dışında asal sayı denince aklımıza pek bir şey gelmez. Peki asal sayılar sadece bu tanımdan mı ibarettir? Asal sayılar; özel bilgilerin korunabilmesi için şifreleme teknolojilerinde, kredi kartlarında, kuantum kaos teorisinde, internet şifrelerinde ve haberleşme sistemleri gibi birçok alanda kullanılmaktadır. Asal sayıların bu şekilde kullanım alanlarını ve  tanımını yapmak basit olsa da asıl sorun yeni bir büyük asal sayının bulunma sürecinde yaşanmaktadır. Bu sorunu çözmek için günümüze kadar pek çok yöntem geliştirilmiştir. Bir tamsayının asal olup olmadığını bulmak için kullanılan yöntemlerden biri de Eratosthenes Kalburu’dur. 

Yunanlı bilim insanı Eratosthenes tarafından bulunan bu yöntem verilen tamsayının altındaki tüm asal sayıları bulmak için kullanılır. Önce 2’den n’ye kadar olan tüm asal sayılar yazılır ve √ n  den küçük ve eşit asal sayıların çarpanları (2p, 3p…) elenir. Geriye  kalan sayılar asal sayılardır.

Tanımı daha iyi anlayabilmek için 36 sayısına kadar olan asal sayıları Eratosthenes Kalburu yöntemiyle bulmaya çalışalım.

Yukarıda bulunan tablodan sırasıyla sayıları eleyerek asal sayıları bulalım. 1’in asal sayı olmadığını bildiğimizden ilk olarak 1’i eleyerek işlemimize başlayalım. Üstelik 2’nin de asal sayı olduğunu biliyoruz. 

1’i eledik ve 2’yi asal sayı olarak belirttik. Gördüğünüz üzere asal sayıları yeşil, olmayanları ise kırmızı ile belirtiyoruz. Asal sayılar sadece kendisine ve 1’e bölünen sayılar olduğundan şimdi de 2’nin katlarını eleyelim. 

Eleme yapıldıktan sonra kalan sayılardan ilk sıradaki yine asal sayıdır. 3 asal sayı olduğuna göre 3’ün katlarını eleyerek devam edelim. 

Tekrar aynı işlemi uygulayarak 5’in asal sayı olduğunu görüp 5’in katlarını eliyoruz. 

Tabloya göre diğer asal sayımız 7 olmaktadır. Ancak 7’nin katlarının işaretlendiğini görmekteyiz. Aynı şekilde 11,13,17 sayılarının da katlarının elendiğini görmekteyiz. Tanımda belirtildiği gibi Fermat’ın teorisine göre aranan aralıktaki en büyük sayının kareköküne kadar sayıların katlarına  bakmak yeterlidir. Örneğimizde en büyük sayı 36 olduğu için 36’nın karekökü olan 6’ya kadar sayıların katlarına bakmamız yeterlidir. Sonrasında kalburda herhangi bir değişiklik olmadığını görmekteyiz. Buna göre tablomuzdaki asal sayılar: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31’dir.

Bu yöntem kriptografi de algoritma sistemlerinde hala kullanılmaktadır. Elbette gelişen bilgisayar sistemleri teknolojisiyle daha büyük asal sayıları bulmamız kolaylaşacak ve hızlanacaktır.

Siz de aşağıdaki linki tıklayarak kendiniz deneyebilirsiniz.

http://www.hbmeyer.de/eratclass.htm

Yazan: Melisa ACAR

Kaynak*

Kaynak**

Kaynak***

YouTube Kanalımız