Küçük bir sayının asal olup olmadığını anlamak kolaydır: 97'yi kareköküne kadar bölersiniz ve biter. Peki 12 haneli, 50 haneli hatta 100 haneli bir sayı verilirse ne olur? Bu rehberde büyük sayıların asallığını test etmenin yollarını, elle uygulanabilir kısayollardan modern algoritmalara kadar inceleyeceğiz.
Neden Büyük Sayılar Zordur?
Bir sayının asal olduğunu kanıtlamanın "kaba kuvvet" yolu, kareköküne kadar olan bütün sayılara bölmektir. 15 haneli bir sayı için bu, milyonlarca milyar bölen denemesi demektir. Hatta işin ironik tarafı şudur: bir sayının asal olduğunu ispatlamak, bileşik olduğunu göstermekten çoğu zaman daha zordur.
Seviye 1: Bölünebilirlik Denemeleri (Elle)
Sayı elinizde yazılıysa ve küçükse, önce küçük asallarla eleyin:
- 2: Son rakam çift mi?
- 3: Rakamlar toplamı 3'ün katı mı?
- 5: 0 veya 5 ile mi bitiyor?
- 7, 11, 13: Kısa bölme denemeleri.
- Son rakam 1 → 2 ile bölünmez.
- Rakamlar toplamı 2+3+1+5+7+1+1 = 20 → 3 ile bölünmez.
- 5 ile bitmiyor.
- 7 ile deneyin: 2.315.711 ÷ 7 = 30.938,7… bölünmez. 11, 13, 17... ile devam.
Yorucu, değil mi? İşte bilgisayar algoritmaları burada devreye girer.
Seviye 2: Karekök Sınırı
n sayısı bileşikse, mutlaka √n'den küçük bir asal böleni vardır. Yani 15 haneli bir sayı için 10 milyona kadar olan asalları denemek teorik olarak yeterlidir — ama pratikte hâlâ çoktur. Bu yöntem yalnızca orta büyüklükteki sayılarda (yaklaşık 15 basamağa kadar) bilgisayarla uygundur.
Seviye 3: Probabilistik Testler (Fermat)
Pierre de Fermat'nın küçük teoremi der ki: n asal ise, her a için:
Bu koşulu sağlamayan sayılar kesinlikle bileşiktir. Sağlayanlar için ise "muhtemelen asal" diyebiliriz. Tekrarlanan testlerle hata payı katlanarak azalır.
561, 1105, 1729 gibi sayılar bileşik oldukları hâlde Fermat testini geçer. Bu yüzden modern testler, Fermat'nın yerine geliştirilmiş sürümlerini kullanır.
Seviye 4: Miller-Rabin Asallık Testi
Günümüzdeki asallık testlerinin standardı budur; kriptografideki anahtar üretimi de buna dayanır. Miller-Rabin, Fermat testine ekstra kontroller ekleyerek Carmichael tuzaklarını da yakalar.
- n-1 sayısını d × 2^s biçimine yazın.
- Seçilen bazılar için a^d hesaplayın.
- Karekök alma adımlarında n-1'e ulaşılıp ulaşılmadığına bakın.
- Ulaşılamazsa sayı bileşiktir; her taban için ulaşıldıysa "asal" sonucu verilir.
Doğru seçilmiş tabanlarla (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) test, 3,3 × 10²⁴'ten küçük sayılarda kesin sonuç verir.
Sitemizdeki Asal Sayı Hesaplama aracının arkasında tam olarak bu algoritma çalışır. 50 haneli bir sayı girdiğinizde bile saniyenin altında sonuç almanızın sebebi budur.
Daha Büyük Sayılar: Ölümsüz Asallar
Milyonlarca basamaklı asalları bulmak için özel biçimler kullanılır: örneğin Mersenne asalları 2ᵖ - 1 biçimindedir ve özel testlerle (Lucas-Lehmer) doğrulanır. Bugüne kadar bulunan en büyük asal sayı, bu biçimde keşfedilen 40 milyondan fazla basamaklı bir sayıdır. Daha fazlası için Mersenne asalları yazımıza göz atın.
Evde Deneyebilecekleriniz
- Eleyin: 2, 3, 5, 7 bölenlerini elle deneyin; büyük sayılarda bile çoğunu elersiniz.
- Aracı kullanın: Asal Sayı Hesaplama ile kontrol edin, çarpanlarını görün.
- Kendi testinizi yazın: Basit bir döngüyle 2'den √n'ye bölen arayan 5 satırlık bir program bile fikir verir.
Sonuç
Küçük sayılarda bölen denemek yeterlidir; büyük sayılarda ise Miller-Rabin gibi algoritmalar kullanılır. Elle yalnızca bölünürlük kurallarıyla eleme yapabilirsiniz; kesin karar için hesaplama araçlarımız tarayıcınızda, verilerinizi dışarı göndermeden çalışır.