Bir sayı yazıyorsunuz, araç bir saniye içinde "asal!" diyor. Peki perdenin arkasında ne oluyor? Bu yazıda bilgisayarların asal sayıları nasıl bulduğunu, test ettiğini ve çarpanlarına nasıl ayırdığını — karmaşık matematik diline boğulmadan — anlatıyoruz. Bonus: sitemizdeki araçların tam da bu algoritmalarla çalıştığını göreceksiniz.
1. Yöntem: Deneme Bölme (Çocukluk Yolu)
En basit yol: 2'den sayının kareköküne kadar bölen aramak.
isAsal(n):
i = 2'den sqrt(n)'e kadar:
n % i == 0 ise → asal değil
→ asalArtısı: Kesin sonuç, anlaşılması kolay. Eksisi: 15 haneli bir sayıda bile milyarlarca işlem gerekir.
Bu yöntem, bilgisayarların ilk yıllarında standarttı; bugün hâlâ "ilk tur filtre" olarak kullanılır.
2. Yöntem: Eratosthenes Kalburu (Liste Üretmek)
Tek tek test yerine toplu asal listesi üretmek gerektiğinde kalbur yöntemi (rehberi) hâlâ şampiyondur: asal olmayanları topluca eleme mantığıyla çalışır ve 10 milyona kadar olan asalları saniyeler içinde döker. Büyük aralıklar için segmenteli varyantı kullanılır — Aralık aracımızın arkasındaki yöntemdir.
3. Yöntem: Fermat Testi (Kısayol)
Fermat'ın küçük teoremi der ki, n asal ise her a için a^(n⁻¹) ≡ 1 (mod n). Bu koşulu sağlamayan sayılar kesin olarak bileşiktir. Hesaplaması, bölmeye göre çok hızlıdır (modüler üslü alma ile). Ancak Carmichael sayıları gibi tuzaklar vardır; tek başına yeterli değildir.
4. Yöntem: Miller-Rabin (Günümüzün Standardı)
Fermat testine eklenen "kare kök kontrol adımları" ile tuzaklar da yakalanır. Doğru seçilmiş tabanlarla (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
- 3,3 × 10²⁴'ten küçük sayılarda kesin sonuç verir.
- Daha büyük sayılarda hata payı, klasik varyantlarda bile 4⁻ᵏ düzeyindedir (k = tur sayısı); pratikte "imkânsız" kadar küçüktür.
Sitemizin asallık testi budur. 50 haneli bir sayı girdiğinizde arka planda gerçekleşen: küçük asallarla hızlı eleme → modüler üslü test → karar.
9.223.372.036.854.775.783 (19 basamak) — asal mı? [Aracımız](/araclar/asal-sayi-hesaplama/) bu sayıyı milisaniyeler içinde doğrular: evet, asaldır. Aynı sonucu deneme bölmeyle doğrulamak, tek başına saatler sürebilirdi.
5. Yöntem: Pollard-Rho (Çarpanları Bulmak)
Asal olmadığını bilmek kolay; bölenleri bulmak zordur. Pollard-Rho algoritması, "doğum günü paradoksu" mantığıyla çalışır: rastgele sayılardan oluşan bir dizide, gizli bölenin modülü altında çakışma arar. Klasik deneme bölmeye göre dramatik biçimde hızlıdır; özellikle orta büyüklükteki bölenlerde (örn. 10-15 basamak) çok etkilidir.
Bizim Asal Çarpanlara Ayırma aracımız, önce küçük asallarla deneme bölme yapar, kalan karmaşık kısım için Pollard-Rho kullanır — üstelik her adımı size "okul yöntemi" biçiminde gösterir.
Algoritmalar Nasıl Karşılaştırılır?
| Yöntem | Amaç | Hız | Kesinlik |
|---|---|---|---|
| Deneme bölme | Test + çarpan | Yavaş (büyük sayıda) | Kesin |
| Kalbur | Toplu liste | Çok hızlı | Kesin |
| Fermat | Test | Hızlı | Tuzaklı |
| Miller-Rabin | Test | Çok hızlı | Pratikte kesin |
| Pollard-Rho | Çarpan bulma | Orta-hızlı | Kesin (çarpanı bulursa) |
Neden "Kesin" ile "Pratikte Kesin" Arasında Fark Var?
Matematikte kanıt her şeydir; ama mühendislikte olasılıklar da iş görür. 2⁻¹²⁸ hata payı, evrenin ömrü boyunca beklenen hata sayısının bile altındadır — kriptografi standartları da bu düzeyi kabul eder. Yine de, istenirse deterministik testlerle (AKS algoritması, 2002) kesinlik elde edilebilir; ama pratikte Miller-Rabin hızını kimse geri çevirmez.
Bu Algoritmaları Siz de Kullanabilirsiniz
Tüm hesaplamalar sitemizde tarayıcınızda çalışır; hiçbir sayı sunucuya gönderilmez:
- Asal Sayı Hesaplama — Miller-Rabin
- Asal Çarpanlara Ayırma — Deneme bölme + Pollard-Rho
- Aralıktaki Asal Sayılar — Segmenteli kalbur
- Aralarında Asal mı? — Euclid algoritması
Sonuç
Bilgisayarların asal sayı "sihri", bölmekten çok daha zarif algoritmalara dayanır: kalbur listeleri üretir, Miller-Rabin saniyeler içinde karar verir, Pollard-Rho gizli bölenleri avlar. Bir dahaki sefere aracımızda "asal" yazısını gördüğünüzde, arka planda 300 yıllık matematiğin çalıştığını bilin.