The evaluation and comparison of primality testing algorithms

Abstract

Asal sayılar, kendisi ve 1 dışında herhangi bir böleni olmayan sayılardır.Günümüzde yaygın olarak kullanılan kriptolojik tekniklerde ve güvenilir haberleşmeprotokol tasarımlarında yüzlerce ve hatta binlerce rakamdan oluşan asal sayılarkullanılmaktadır. Örnek vermek gerekirse, popüler ve çok bilinen algoritmalardan biriolan RSA [22] algoritması, 150'den fazla rakam içeren iki asal sayının çarpımındanoluşmaktadır. Bu sebeple, tüm asal sayılar için geçerli olabilecek genel formüllerve testler geliştirilmesi, araştırmacılar tarafından halen çalışmaları devam eden biralan olmuştur. 1960'lı yıllardan öncesinde teorik olarak kanıtlanan bir asallık testiolmamasına rağmen, o yıllardan itibaren bu konuda birden fazla pratik metotlarbulunmuştur [7–10, 16, 17]. Çok büyük sayılar için kullanılması uygun olanalgoritmalar vardır ve bunlar genel olarak olasılıksal testler ve deterministik testlerolarak iki gruba ayrılabilir.Olasılıksal testler birkaç gruptan oluşan matematiksel denklemleri içerir ve diğertestlerle karşılaştırıldığında daha hızlı olduğu kanıtlanmıştır. Bu testlerin ortaközelliği; asal sayıları tanımlamakta (çok küçük ve önemsiz düzeyde de olsa) birhata payı içermesidir. Test edilmek üzere verilen bir n sayısı için, sayı eğer asaldeğil ise, olasılıksal testler bunu tespit etmekte %100 gerçek sonuç verir. Fakat diğeryönden, verilen sayıya algoritmanın döndüğü tanımlama, sayının asal olduğu ise,bu sonuç tam olarak güvenilir değildir. Çünkü bilinen bazı asal olmayan sayılarvardır ki; bu testi asal bir sayıymış gibi geçebilirler. Bu yüzden, olasılıksal testlerindoğruluğunu ve geçerliliğini artırmak için, test aynı sayı için farklı rastgele tabanlarseçilerek t defa tekrar edilir. Bu tekrar, aynı zamanda test sonucunda oluşan hatapayının düşmesini sağlar. Aynı sayının defalarca tekrar edilmesi sebebiyle, olasılıksalbir sonuç elde edilir. Olasılıksal testlere örnek olarak; Euler ve Fermat testleriylebirlikte, Solovay-Strassen [10] ve Miller-Rabin [16, 17] tarafından geliştirilen testleride verilmiştir.Olasılıksal testler bölümünde görüldüğü üzere; bazı yalancı asallar vardır ki, rastgeleseçilen baz değerine göre asal sayılar gibi testin tüm şartlarını sağlarlar. Tarihsel olaraksıralandığında, günümüz gelişmelerine doğru testlerin yarı asal oluşturma olasılığıgitgide azalmıştır. Örneğin; 10^4 limitinden az Fermat testi için (baz 2 alındığında)yalancı asalların sayısı 22 iken; Euler testiyle birlikte bu sayı 12'ye düşmüştür.Miller-Rabin olasılıksal testi aynı baz de˘geri için de˘gerlendi˘ginde, bu toplam sadece5'tir. Ancak; en az hata veren Miller-Rabin testinin hata oranı incelendiğinde;testin t defa tekrar etmesi sonucunda hata oranı (1/4)^t değerinden azdır. Bu değerküçük ve önemsiz olsa da, asal sayıların yaygınca kullanıldığı günümüz algoritmalarıdüşünüldüğünde, net sonuçlar veren asallık testlerine olan ihtiyaç görülmektedir.Olasılıksal testlerin defalarca tekrarlanarak olasılıksal bir sonuç dönmesinin eksikliğinikapatmak üzere, deterministik testler geliştirilmiştir. Deterministik testlerin temel özelliği, çok yüksek bir doğruluk payı içermeleridir. Diğer bir deyimle, deterministiktestler verilen sayı için sonuç olarak asal tanımlaması yaptığında, verilen sayınıngerçekte asal olması doğrulanmış olur. Aynı şekilde; verilen sayının tanımlamasıasal olmadığı şeklinde ise, sayı gerçekte de asal değildir. Ancak, bu testlerindoğruluk özelliğinin net olmasının yanında, pratik uygulamalarda sıklıkla kullanmakiçin olasılıklar testler kadar hızlı sonuç vermezler. Deterministik testlere örnekvermek gerekirse, Agrawal-Kayal-Saxena (AKS) algoritması ve analizi örneklerleberaber incelenmiştir. Bu test, polinom zamanlı deterministik bir test olmasınarağmen, çalışma zamanı bakımından değerlendirildiğinde olasılıklsal ve elliptik eğritestlerine nazaran çok yavaş kalmaktadır. Bu sebeple, tez içinde karşılaştırılmaya dahiledilmemiştir.Bu testlerin dışında, eliptik eğriler ve türevleri kullanılarak geliştirilen asallık testialgoritmaları da günümüzde yaygınca kullanılmaktadır. Bazı eliptik eğri asallık testialgoritmalarının, çok büyük sayıda rakamdan oluşan sayıların asal olup olmadığınıtespit etmeleri çok uzun zaman alsa da, dönülen sonuç deterministiktir. Bu testlereörnek olarak Shafi-Killian ve Atkin-Morain olmak üzere, iki eliptik eğri asallıkispatlama algoritması incelenmiştir.Öncelikle, Shafi-Killian [9] ve Atkin-Morain [8] tarafından geliştirilen algoritmalarınbaz aldığı temel işleyiş metodolojisi verilmiştir. Ayrıca; her iki algoritmanın da anatemelini oluşturan Pocklington Teoremi'nden bahsedilmiştir. Her iki algoritma dabenzer metodolojiye farklı bir bakış açısı sunduğundan ve birebir bir karşılaştırmasunulması açısından, bu algoritmalar 5 temel adımda incelenmiştir.Shafi-Killian tarafından geliştirilen algoritmada, ilk aşamada Miller-Rabin testi gibiolasılıksal bir test kullanılır. Bu aşama sayesinde, sadece olasılıksal testin asalolmadığını ispatlayamadığı sayılar için denenmiş olur. Daha sonra, rastgele bira ve b değeri seçilerek eliptik eğri denklemi oluşturulur. Bu eğrinin üzerindekitüm noktaların sayısını bulmak için, nokta sayma algoritmalarından olan Schoofmetodu [11] kullanılır. Bu metot ile bulunan değerin çarpanlara ayrılması gerekirve bu aşamada Lenstra'nın çarpanlara ayırma metoduna yer verilmiştir. Eğer değerçarpanlara ayrılmazsa, en başa dönülerek yeni bir eğri seçilir ve diğer adımlartekrarlanır. Bu ilk 3 aşamanın zaman maliyetli olması sebebiyle, Atkin-Morain eliptikeğri algoritması geliştirilmiştir.Atkin-Morain algoritmasında kullanılacak eliptik eğri rastgele değil, belli bir önaşamadan sonra oluşturulur. Bu metodun temel farkı olarak karışık çarpım (CM)yöntemine yer verilmiştir. CM sayesinde, eğri üzerindeki nokta sayısı için olasıdeğerler elde edilir ve bu sayıların çarpanlara ayrılması denenir. Çarpanlara ayrılandeğer bulunduğunda, eliptik eğri bu değere göre yine rastgele a ve b değerleri seçilerekoluşturulur.Eliptik eğri oluşturma aşamasında farklılaşan Shafi-Killian ve Atkin-Morain algoritmaları,eliptik eğri seçildikten sonra aynı operasyonları uygular. Her iki algoritmada, belirlenen eğri üzerinde, yani eğri denklemini sağlayan, bir nokta seçer. Dahasonra bu nokta üzerinde grup operasyonu uygular. Bu testler, ilk aşamada verilensayının asal olduğunu kabul edip, grup operasyonu sırasında asal olmadığını bir hataile bulma mantığına dayalı olduğu için, grup operasyonunda hata olana kadar testlerdevam eder. Bu sebeple, bu testlerin çalışma zamanını net olarak ölçmek mümkündeğildir. Bu tezde, eliptik eğriler ve grup operasyonları hakkında temel bilgilere değinilmiştir. Aynı zamanda, çalışma zamanı olarak verimli grup operasyonu ve skalerçarpım algoritmalarına yer verilmiştir.Genel olarak, bu tezde, öncelikle sayılar teorisinde temel olarak bilinen ve kullanılangenel matematiksel altyapılar için tanımlamalar ve teoremler verilmiştir. Daha sonradevam eden bölümlerde eliptik eğrilere dair detaylar anlatılmıştır. Literatür taramasıolarak, bilinen asallık testi algoritmaları altyapılarıyla birlikte verilerek, bu testlerokuyucuya daha açık bir anlatım sunabilmek için örneklerle beraber pekiştirilmiştir.Bilinen algoritmaların kendilerine dair özellikleri dışında, diğer algoritmalarlakarşılaştırıldığında oluşan avantajlar ve dezavantajları değerlendirilmiştir.Bilinen algoritmaların yanına ek olarak, önceden teorik olarak geliştirilen bir asallıktesti önermesine [35] yer verilmiştir. Bu önermenin algoritma olarak detaylarıverilerek, neden asallık testi olabileceğine dair detaylardan bahsedilmiştir. Bualgoritmanın bilgisayar ortamında C++ dili ile yazılım tabanlı gerçeklenmesi yapılıppratik ortamda kanıtlanması sa˘glanmıştır. Testler Miller-Rabin algoritmasının doğruolarak yakalayamadığı sayılardan olan `baz 2` sayıları seçilmiştir. Baz 2'ye göreyalancı olan sayılar gerçekte asal olmamasına rağmen, Miller-Rabin algoritmasındanasal olarak geçebilen sayılardır. Bu testin gerçeklenmesinden elde edilen sonuçlar,önerilen asallık testinin 2^64'e kadar olan tüm baz 2'ye göre yalancı asal olan sayılarıngerçekte asal olmadığını tanımladığını göstermektedir. Aynı zamanda, çok büyükrakam içeren ve yüksek hassaslıktaki rastgele sayılar denenmiş ve bu testin doğrusonuçlara kısa zamanda ulaştığı görülmüştür.Bu testin gerçekliğinin pratikte denenmesinin yanında; testin diğer algoritmalarile çalışma zamanı karşılaştırılmıştır. Teorik karşılaştırma ve çalışma zamanınadair sonuçlar göstermektedir ki; bu test olasılıklar testler kadar hızlı ve pratiktekullanılabilecek kadar az algoritma karmaşıklığına sahiptir.

A prime number is an integer without a non-trivial divisor. In modern cryptography,several secure digital communication methods need to use large prime numbers. Forexample, one of the most popular public key cryptosystems, RSA [22], uses primeintegers with more than 150 digits. Thus, it has been an interest of researchers togive a generic formula for defining all prime numbers. Although, there was no initialconcern to detect prime integers theoretically, from the beginning of late 60's, severalresearches have presented a practical method for the primality test. Currently, there aremethods [7–10, 16, 17] to decide the primality of the big numbers. These methods canbe divided into two categories: probabilistic and deterministic primality tests.Probabilistic tests are very fast and consist of some set of mathematical equations andprocedures. The common property of these tests is having error probability with somecomposite numbers. For a given integer n to determine whether it is prime, the test is100% accurate if it labels that number as a composite. However, the other case wherethe test output is prime is not always true, that is to say, there is always a probabilitythat a composite number passes the test and is labeled as prime. To decrease thisprobability and increase the accuracy of the test, we always need to repeat the test forseveral times. As examples of probabilistic tests, we provide explanations on Euler'sTest, Fermat's Test, Solovay-Strassen Primality Test and Miller-Rabin Test.To overcome the drawback of probabilistic tests, deterministic tests are invented.Besides probabilistic tests, deterministic tests guarantee that if the test labels agiven number n as composite, the number is, in fact, composite. Additionally,deterministic tests also guarantee the primality of numbers. However, the running timeof deterministic tests is not satisfactory for frequent use in commercial applications.As an example of deterministic test, we give details of Agrawal-Kayal-Saxena (AKS)primality testing algorithm with a pseudocode, examples, running time analysis, itsaccuracy and drawbacks.Moreover, elliptic curve primality testing methods and theorems are widely used.Although some algorithms require very long execution time for several-million digitintegers, the results are deterministic. Thus, we include Shafi-Killian and Atkin'selliptic curve primality proving algorithms into our analyses.In this thesis, general mathematical theorems which are very fundamental in numbertheory are explained to the reader. Then, their applications on primality testing aregiven by commonly used primality test algorithms. The current algorithms analyzed interms of computational complexity, illustrated with examples to make the algorithmsclearer and finally evaluated with its advantages and disadvantages. This literaturereview is given to increase the knowledge required for the singular cubic curve test[35]. Then, known primality tests and their analyses are given to provide a base forcomparison.Finally, the theoretical and experimental comparison results are provided in thelast chapter. Known primality tests are compared to the singular cubic primalitytest by using the same dataset which includes both primes and composites withdifferent number of digits. Implementation and testing phrases show that thesingular cubic curve algorithm catches all composite number up to 1021 which werestrong pseudoprimes to base 2 according to commercially used Miller-Rabin test.Additionally, it successfully detects the compositeness of large integers that haveseveral hundred digits. Thus, singular cubic curve algorithm is a candidate to be aprimality testing algorithm with running time of O(log^{2+e}n).