Asallık Testi

Birçok şifreleme algoritması bir veya daha fazla asal sayıya ihtiyaç duymaktadır. Peki büyük bir asal sayısı nasıl seçebiliriz? Büyük bir sayının asal olup olmadığı gibi zor bir soruya nasıl cevap verebiliriz? Bu soruya cevap veren bazı alogirtmalardan biri olan Miller-Rabin algoritmasını hep beraber inceleyelim. Bu algoritmanın bir asal sayı dönebileceği gibi, asal sayı dönmesine gerek olmadığını da belirtmek gerekir. İnceleyelim.

Miller-Robin algoritması büyük bir sayının asal olup olmadığını test eder. Algoritmayı açıklamadan önce ön bilgi olarak modüler aritmetik bilginizin olduğunu varsayıyorum.

Öncelikle pozitif bir tek sayısı şeklinde ifade edilebilir. Burada ve tek bir sayıdır. Örnek olarak için verilebilir. için vs.. Buradan, sayısını defa ile bölersek, bölüm olarak sayısını elde edeceğimiz açıktır. Eğer 28 sayısını binary olarak ele alırsak , en sağdaki bit 1 oluncaya kadar sağa doğru defa shift yaparsak sayısını binary olarak() elde ederiz.

Asıl konuya geçmeden önce bize yardımcı olacak bir teoremden bahsetmek gerekiyor. Fermat Teoremine göre, ‘dir, eğer bir asal sayı ve tarafından bölünemeyen bir tamsayı olduğu şartları sağlanıyorsa(devrik cümle maalesef). Konumuzla devam edelim..

Asal sayıların özelliklerinden birini şu şekilde açıklayabiliriz: Eğer bir asal sayı ve ‘den küçük pozitif bir tamsayı ise, aşağıdaki şartlardan herhangi biri doğru ise olur.

• veya,
• . Modüler aritmetik kurallarına göre, () ( ) = ‘dir. Buna göre olsa da, sonuç olarak olur.

Asal sayıların diğer bir özelliğini şu şekilde açıklayabiliriz: ‘den büyük bir asal sayı ise, şeklinde ifade edilebilir. Burada ve tek bir sayıdır (3. paragrafta değişnmiştik). şeklinde herhangi bir tamsayısını ele aldığımızda aşağıdaki şartlardan biri doğrudur.

• , diğer ifadeyle
• sayılarından biri . Burada şeklinde bazı sayıları vardır ve ‘dir. Fermat teoremine göre ‘dir, eğer bir asal sayı ise, şeklinde belirtmiştik. Elimizde olduğuna göre,
  • dizisinin son elemanının değeri 1’dir. Her dizi elemanı bir öncekinin karesidir aynı zamanda. Bundan dolayı aşağıdaki olasılıklar mevcuttur.
    1. Dizinin ilk elemanı ve dolayısıyla kareleri olan diğer elemanların değeri 1’dir.
    2. Dizideki bazı sayılar 1değildir ancak kareleri ‘de 1’dir.

Sonuç olarak bir asal sayı ise dizideki sayılar 1 değerindedir, veya dizideki bazı sayılar ‘e eşittir. Aksi durumda asal değildir. Bu şartları sağlaması sayısını asal olarak seçmemizi sağlar ancak bu sayısının kesin olarak asal olduğu anlamına gelmez.

Bir sayısının asallık testi için izlememiz gereken algoritmanın adımları şu şekildedir:

• ve tek sayı olacak şekilde ve sayılarını bul, ()
• olacak şekilde rastgele bir sayısı seç,
• Eğer ise sayısı asal olabilir,
• ‘dan ‘e bir for döngüsü kur,
• Eğer ise sayısı asal olabilir,
• sayısı asal değildir.

Birden fazla sayısı seçilerek sayısının test edilmesi asal olma ihtimalini güçlendirir.

Aşağıda örnek kodlar verilmiştir. Kodlar örnek amaçlıdır. Herhangi bir üründe kullanılmak için tamamen hazır halde (production-ready) değildir.

Bir sonraki yazımızda görüşmek üzere..

using System.Numerics;
using System.Security.Cryptography;

Console.WriteLine("***Miller-Rabin Primality Test***");
Console.WriteLine();
string isGameOver = "";
while (isGameOver.ToLower() != "y")
{
    Console.Write("Please write a number for primality test: ");
    if (!BigInteger.TryParse(Console.ReadLine(), out BigInteger n))
    {
        Console.WriteLine("This is not a Number!");
        continue;
    }
    Console.Write("How many times do you want to test this number? : ");
    if (!int.TryParse(Console.ReadLine(), out int numberOfTest))
    {
        Console.WriteLine("This is not a Number!");
        continue;
    } 
    Console.WriteLine($"Is {n} prime? : {IsPrime(n, numberOfTest)}");
    Console.Write("Is game over? (Quit?) [y] [n]: ");
    isGameOver = Console.ReadLine();
}
static bool IsPrime(BigInteger n, int numberOfTest)
{
    if ((n < 3) || (n % 2 == 0))
    {
        return false;
    }
    BigInteger q = n - 1;
    int k = 0;
    while (q % 2 == 0)
    {
        q >>= 1;
        k++;
    }
    Console.WriteLine($"k: {k}");
    Console.WriteLine($"q: {q}");

    RandomNumberGenerator rng = RandomNumberGenerator.Create();
    byte[] bytes = new byte[n.ToByteArray().LongLength];
    BigInteger a;
    for (int i = 0; i < numberOfTest; i++)
    {
        do
        {
            rng.GetBytes(bytes);
            a = new BigInteger(bytes);
        }
        while (a < 2 || a >= n - 2);
        if (BigInteger.ModPow(a, q, n) == 1)
        {
            return true;
        }
        for (int j = 0; j < k; j++)
        {
            if (BigInteger.ModPow(a, BigInteger.Pow(2, j) * q, n) == n - 1)
            {
                return true;
            }
        }
    }
    return false;
}