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.
- Dizinin ilk elemanı ve dolayısıyla kareleri olan diğer elemanların değeri 1’dir.
- 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;
}