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 n>=3 pozitif bir n tek sayısı n-1 = 2^kq şeklinde ifade edilebilir. Burada k>0 ve q tek bir sayıdır. Örnek olarak n = 29 için 29-1 = 2^27 verilebilir. n = 7 için 7-1 = 2^13 vs.. Buradan, n-1 sayısını k defa 2 ile bölersek, bölüm olarak q sayısını elde edeceğimiz açıktır. Eğer 28 sayısını binary olarak ele alırsak  11100, en sağdaki bit 1 oluncaya kadar sağa doğru k defa shift yaparsak q = 7 sayısını binary olarak( 00111) elde ederiz.

Asıl konuya geçmeden önce bize yardımcı olacak bir teoremden bahsetmek gerekiyor. Fermat Teoremine göre, a^{p-1}}\equiv 1\: mod\:p‘dir, eğer p bir asal sayı ve a p 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 p bir asal sayı ve a p‘den küçük pozitif bir tamsayı ise, aşağıdaki şartlardan herhangi biri doğru ise a^2 \:mod \:p = 1 olur.

  • a\:mod \:p = 1 veya,
  • a\:mod\:p = -1\:mod\:p = p-1. Modüler aritmetik kurallarına göre, (a \:mod \:p) (a \:mod \:p ) = a^2 \:mod \:p ‘dir. Buna göre a \:mod \:p = 1\: veya -1 olsa da, sonuç olarak a^2 \:mod \:p = 1 olur.

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

  • a^q \equiv 1 (mod\:p), diğer ifadeyle a^q \:mod\:p = 1
  • a^q,\:a^{2q},\:a^{4q}...a^{2^{k-1}q} sayılarından biri \equiv -1 (mod\:p). Burada 1<=j<=k şeklinde bazı j sayıları vardır ve a^{2^{j-1}q}\equiv -1\: mod\:p‘dir. Fermat teoremine göre a^{p-1}}\equiv 1\: mod\:p‘dir, eğer p bir asal sayı ise, şeklinde belirtmiştik. Elimizde p-1 = 2^kq olduğuna göre,
    • a^q\:mod\:p,\:a^{2q}\:mod\:p,\:a^{4q}\:mod\:p\:...\:a^{2^{k-1}q}\:mod\:p,\:a^{2^{k}q}\:mod\:p 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 mod\:p‘de 1’dir.

Sonuç olarak p bir asal sayı ise (a^q,\:a^{2q},\:a^{4q}...a^{2^{k-1}q}\:mod\:p,a^{2^{k}q}\:mod\:p)} dizideki sayılar 1 değerindedir, veya dizideki bazı sayılar p-1‘e eşittir. Aksi durumda p asal değildir. Bu şartları sağlaması p sayısını asal olarak seçmemizi sağlar ancak bu p sayısının kesin olarak asal olduğu anlamına gelmez.

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

  • k>0 ve q tek sayı olacak şekilde k ve q sayılarını bul, (n-1 = 2^kq)
  • 1<a<n-1 olacak şekilde rastgele bir a sayısı seç,
  • Eğer a^q \equiv 1 (mod\:n) ise return n sayısı asal olabilir,
  • j=0‘dan k-1‘e bir for döngüsü kur,
  • Eğer a^{2^{j-1}q}\:mod\n=n-1 ise return n sayısı asal olabilir,
  • return n sayısı asal değildir.

Birden fazla a sayısı seçilerek n 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;
}

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir