Asal Sayı Kontrolü Nasıl Yapılır?

Kullanıcının girdiği bir sayının Asal sayı olup olmadığını kontrol eden python kodu aşağıdadır. Öncesinde değinmek istediğim 2 konu var.

Asal Sayılar Neden Önemli?

Sadece matematiksel olarak konuşacak olsaydık. Aritmetiğin temel teoremini hatırlatmak isterdim: “1’den büyük her tam sayının asal sayıların çarpımı şeklinde tek bir yolla yazılabileceğini ifade eder”
İki asal sayının çarpımı özellikle şifreleme ve güvenlik alanlarında çok sık kullanılır. Çünkü bunlarla yapılan şifrelemeler çok uzun süre boyunca kırılamazlar. Bu yüzden bankacılık, kripto para, dijital imza, uçtan uca şifreleme ile çalışan mesajlaşma programları, tarayıcılar asal sayılarla çalışırlar.

Asal Sayı Algoritması

Kullanıcı dışarıdan bir sayı girdiğinde bunun gerçekten asal sayı olup olmadığını nasıl kontrol etmek için nelere dikkat edeceğimize bakalım.

Girdi al: Kullanıcıdan bir değer al.
Tam sayı kontrolü (tek adım): Değer int() ile tam sayıya çevrilebiliyor mu?
- Hayır ise → “Girdiğiniz sayı tam sayı değildir” de, çık.
- Evet ise devam.
Alt sınır kontrolü: Sayı 2’den küçükse → asal değildir, çık.
2 kontrolü: Sayı tam olarak 2 ise → asaldır, erken çık.
Çift sayı kontrolü: Sayı 2’den büyük ve çift ise → asal değildir; bölenlere 2 ve sayi//2 ekle, döngüye hiç girme.
Tek bölen taraması: i = 3’ten başla, i * i <= sayi olana kadar i += 2 ile ilerle.
- sayi % i == 0 ise → i ve eşi sayi // i bölenlere eklenir (tam kare durumunda eşi iki kez eklememek için es != i kontrolü).
Karar:
- Bölen listesi boş → “xxx, asal bir sayıdır”.
- Dolu → küçükten büyüğe sırala, “xxx, asal olmayan bir sayıdır çünkü y, z … tam sayı bölenlerine sahiptir”.

Asal Sayı Kontrolü için Python Kodu

Python

def asal_mi(deger):
    # 1) Tam sayı kontrolü — tek adım
    try:
        sayi = int(deger)
    except ValueError:
        print("Girdiğiniz sayı tam sayı değildir")
        return

    # 2) 2'den küçükler asal değildir (negatif, 0, 1)
    if sayi < 2:
        print(f"{sayi}, asal olmayan bir sayıdır çünkü 1'den büyük olmalıdır")
        return

    # 3) 2 tek çift asaldır — erken çıkış
    if sayi == 2:
        print(f"{sayi}, asal bir sayıdır")
        return

    bolenler = []

    # 4) 2'den büyük çift sayılar asal değildir — erken çıkış
    if sayi % 2 == 0:
        bolenler.append(2)
        es = sayi // 2
        if es != 2:
            bolenler.append(es)
    else:
        # 5) Sadece tek bölenleri tara: 3, 5, 7, ...
        i = 3
        while i * i <= sayi:
            if sayi % i == 0:
                bolenler.append(i)
                es = sayi // i
                if es != i:      # tam kare durumunda aynı böleni iki kez eklememek için
                    bolenler.append(es)
            i += 2

    # 6) Karar
    if not bolenler:
        print(f"{sayi}, asal bir sayıdır")
    else:
        bolenler.sort()
        bolen_str = ", ".join(str(b) for b in bolenler)
        print(f"{sayi}, asal olmayan bir sayıdır çünkü {bolen_str} tam sayı bölenlerine sahiptir")


# Kullanıcıdan giriş al
girdi = input("Bir sayı giriniz: ")
asal_mi(girdi)

def asal_mi(deger):
    # 1) Tam sayı kontrolü — tek adım
    try:
        sayi = int(deger)
    except ValueError:
        print("Girdiğiniz sayı tam sayı değildir")
        return

    # 2) 2'den küçükler asal değildir (negatif, 0, 1)
    if sayi < 2:
        print(f"{sayi}, asal olmayan bir sayıdır çünkü 1'den büyük olmalıdır")
        return

    # 3) 2 tek çift asaldır — erken çıkış
    if sayi == 2:
        print(f"{sayi}, asal bir sayıdır")
        return

    bolenler = []

    # 4) 2'den büyük çift sayılar asal değildir — erken çıkış
    if sayi % 2 == 0:
        bolenler.append(2)
        es = sayi // 2
        if es != 2:
            bolenler.append(es)
    else:
        # 5) Sadece tek bölenleri tara: 3, 5, 7, ...
        i = 3
        while i * i <= sayi:
            if sayi % i == 0:
                bolenler.append(i)
                es = sayi // i
                if es != i:      # tam kare durumunda aynı böleni iki kez eklememek için
                    bolenler.append(es)
            i += 2

    # 6) Karar
    if not bolenler:
        print(f"{sayi}, asal bir sayıdır")
    else:
        bolenler.sort()
        bolen_str = ", ".join(str(b) for b in bolenler)
        print(f"{sayi}, asal olmayan bir sayıdır çünkü {bolen_str} tam sayı bölenlerine sahiptir")


# Kullanıcıdan giriş al
girdi = input("Bir sayı giriniz: ")
asal_mi(girdi)

Yukarıdaki kodu sadece günlük hayatta kullanabilirsiniz. 20 basamaklı bir sayı girdiğinizde evde kullandığımız bilgisayarlarda belki de saatlerce/günlerce sürecek. Bunun için çok daha büyük sayıları kontrol etmek adına Miller-Robin (ki RSA yönteminde bu kullanılır) algoritması kullanılır.

Miller-Robin Asallık Testi – Python Kodları

Python

import random

def miller_rabin(n, k=40):
    """
    n: test edilecek tam sayı
    k: rastgele taban sayısı (hata olasılığı <= (1/4)^k)
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    # n - 1 = 2^s * d , d tek
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False   # tanık bulundu → bileşik
    return True            # tüm tabanlar geçti → asal


# Test
while True:
    girdi = input("Bir sayı giriniz (çıkmak için q): ")
    if girdi.lower() == 'q':
        break
    try:
        n = int(girdi)
    except ValueError:
        print("Girdiğiniz sayı tam sayı değildir")
        continue

    if miller_rabin(n):
        print(f"{n}, asal bir sayıdır")
    else:
        print(f"{n}, asal olmayan bir sayıdır")

import random

def miller_rabin(n, k=40):
    """
    n: test edilecek tam sayı
    k: rastgele taban sayısı (hata olasılığı <= (1/4)^k)
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    # n - 1 = 2^s * d , d tek
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False   # tanık bulundu → bileşik
    return True            # tüm tabanlar geçti → asal


# Test
while True:
    girdi = input("Bir sayı giriniz (çıkmak için q): ")
    if girdi.lower() == 'q':
        break
    try:
        n = int(girdi)
    except ValueError:
        print("Girdiğiniz sayı tam sayı değildir")
        continue

    if miller_rabin(n):
        print(f"{n}, asal bir sayıdır")
    else:
        print(f"{n}, asal olmayan bir sayıdır")