Geri Dön

The evaluation and comparison of primality testing algorithms

Asallık testi algoritmalarının incelenmesi ve karşılaştırılması

PDF İndir

  1. Tez No: 641566
  2. Yazar: GÖZDE SARIKAYA
  3. Danışmanlar: DOÇ. DR. ENVER ÖZDEMİR
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Bilişim Enstitüsü
  11. Ana Bilim Dalı: Bilişim Uygulamaları Ana Bilim Dalı
  12. Bilim Dalı: Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
  13. Sayfa Sayısı: 110

Özet

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şme protokol tasarımlarında yüzlerce ve hatta binlerce rakamdan oluşan asal sayılar kullanılmaktadır. Örnek vermek gerekirse, popüler ve çok bilinen algoritmalardan biri olan RSA [22] algoritması, 150'den fazla rakam içeren iki asal sayının çarpımından oluşmaktadır. Bu sebeple, tüm asal sayılar için geçerli olabilecek genel formüller ve testler geliştirilmesi, araştırmacılar tarafından halen çalışmaları devam eden bir alan olmuştur. 1960'lı yıllardan öncesinde teorik olarak kanıtlanan bir asallık testi olmamasına rağmen, o yıllardan itibaren bu konuda birden fazla pratik metotlar bulunmuştur [7–10, 16, 17]. Çok büyük sayılar için kullanılması uygun olan algoritmalar vardır ve bunlar genel olarak olasılıksal testler ve deterministik testler olarak iki gruba ayrılabilir. Olasılıksal testler birkaç gruptan oluşan matematiksel denklemleri içerir ve diğer testlerle 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) bir hata payı içermesidir. Test edilmek üzere verilen bir n sayısı için, sayı eğer asal değil ise, olasılıksal testler bunu tespit etmekte %100 gerçek sonuç verir. Fakat diğer yö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ılar vardır ki; bu testi asal bir sayıymış gibi geçebilirler. Bu yüzden, olasılıksal testlerin doğruluğunu ve geçerliliğini artırmak için, test aynı sayı için farklı rastgele tabanlar seçilerek t defa tekrar edilir. Bu tekrar, aynı zamanda test sonucunda oluşan hata payının düşmesini sağlar. Aynı sayının defalarca tekrar edilmesi sebebiyle, olasılıksal bir sonuç elde edilir. Olasılıksal testlere örnek olarak; Euler ve Fermat testleriyle birlikte, Solovay-Strassen [10] ve Miller-Rabin [16, 17] tarafından geliştirilen testleri de verilmiştir. Olasılıksal testler bölümünde görüldüğü üzere; bazı yalancı asallar vardır ki, rastgele seçilen baz değerine göre asal sayılar gibi testin tüm şartlarını sağlarlar. Tarihsel olarak sı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 sadece 5'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ğer küçü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ğini kapatmak üzere, deterministik testler geliştirilmiştir. Deterministik testlerin temel özelliği, çok yüksek bir doğruluk payı içermeleridir. Diğer bir deyimle, deterministik testler verilen sayı için sonuç olarak asal tanımlaması yaptığında, verilen sayının gerç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 testlerin doğruluk özelliğinin net olmasının yanında, pratik uygulamalarda sıklıkla kullanmak için olasılıklar testler kadar hızlı sonuç vermezler. Deterministik testlere örnek vermek gerekirse, Agrawal-Kayal-Saxena (AKS) algoritması ve analizi örneklerle beraber incelenmiştir. Bu test, polinom zamanlı deterministik bir test olmasına rağmen, çalışma zamanı bakımından değerlendirildiğinde olasılıklsal ve elliptik eğri testlerine nazaran çok yavaş kalmaktadır. Bu sebeple, tez içinde karşılaştırılmaya dahil edilmemiştir. Bu testlerin dışında, eliptik eğriler ve türevleri kullanılarak geliştirilen asallık testi algoritmaları da günümüzde yaygınca kullanılmaktadır. Bazı eliptik eğri asallık testi algoritmaları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ık ispatlama algoritması incelenmiştir. Öncelikle, Shafi-Killian [9] ve Atkin-Morain [8] tarafından geliştirilen algoritmaların baz aldığı temel işleyiş metodolojisi verilmiştir. Ayrıca; her iki algoritmanın da ana temelini oluşturan Pocklington Teoremi'nden bahsedilmiştir. Her iki algoritma da benzer metodolojiye farklı bir bakış açısı sunduğundan ve birebir bir karşılaştırma sunulması açısından, bu algoritmalar 5 temel adımda incelenmiştir. Shafi-Killian tarafından geliştirilen algoritmada, ilk aşamada Miller-Rabin testi gibi olasılıksal bir test kullanılır. Bu aşama sayesinde, sadece olasılıksal testin asal olmadığını ispatlayamadığı sayılar için denenmiş olur. Daha sonra, rastgele bir a ve b değeri seçilerek eliptik eğri denklemi oluşturulur. Bu eğrinin üzerindeki tüm noktaların sayısını bulmak için, nokta sayma algoritmalarından olan Schoof metodu [11] kullanılır. Bu metot ile bulunan değerin çarpanlara ayrılması gerekir ve 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ımlar tekrarlanır. Bu ilk 3 aşamanın zaman maliyetli olması sebebiyle, Atkin-Morain eliptik eğri algoritması geliştirilmiştir. Atkin-Morain algoritmasında kullanılacak eliptik eğri rastgele değil, belli bir ön aş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ılan değer bulunduğunda, eliptik eğri bu değere göre yine rastgele a ve b değerleri seçilerek oluş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 algoritma da, belirlenen eğri üzerinde, yani eğri denklemini sağlayan, bir nokta seçer. Daha sonra bu nokta üzerinde grup operasyonu uygular. Bu testler, ilk aşamada verilen sayının asal olduğunu kabul edip, grup operasyonu sırasında asal olmadığını bir hata ile bulma mantığına dayalı olduğu için, grup operasyonunda hata olana kadar testler devam eder. Bu sebeple, bu testlerin çalışma zamanını net olarak ölçmek mümkün değ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ılan genel matematiksel altyapılar için tanımlamalar ve teoremler verilmiştir. Daha sonra devam 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 testler okuyucuya daha açık bir anlatım sunabilmek için örneklerle beraber pekiştirilmiştir. Bilinen algoritmaların kendilerine dair özellikleri dışında, diğer algoritmalarla karşı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ık testi önermesine [35] yer verilmiştir. Bu önermenin algoritma olarak detayları verilerek, neden asallık testi olabileceğine dair detaylardan bahsedilmiştir. Bu algoritmanın bilgisayar ortamında C++ dili ile yazılım tabanlı gerçeklenmesi yapılıp pratik ortamda kanıtlanması sa˘glanmıştır. Testler Miller-Rabin algoritmasının doğru olarak yakalayamadığı sayılardan olan“baz 2”sayıları seçilmiştir. Baz 2'ye göre yalancı olan sayılar gerçekte asal olmamasına rağmen, Miller-Rabin algoritmasından asal 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ın gerçekte asal olmadığını tanımladığını göstermektedir. Aynı zamanda, çok büyük rakam içeren ve yüksek hassaslıktaki rastgele sayılar denenmiş ve bu testin doğru sonuçlara kısa zamanda ulaştığı görülmüştür. Bu testin gerçekliğinin pratikte denenmesinin yanında; testin diğer algoritmalar ile çalışma zamanı karşılaştırılmıştır. Teorik karşılaştırma ve çalışma zamanına dair sonuçlar göstermektedir ki; bu test olasılıklar testler kadar hızlı ve pratikte kullanılabilecek kadar az algoritma karmaşıklığına sahiptir.

Özet (Çeviri)

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. For example, one of the most popular public key cryptosystems, RSA [22], uses prime integers with more than 150 digits. Thus, it has been an interest of researchers to give a generic formula for defining all prime numbers. Although, there was no initial concern to detect prime integers theoretically, from the beginning of late 60's, several researches have presented a practical method for the primality test. Currently, there are methods [7–10, 16, 17] to decide the primality of the big numbers. These methods can be divided into two categories: probabilistic and deterministic primality tests. Probabilistic tests are very fast and consist of some set of mathematical equations and procedures. The common property of these tests is having error probability with some composite numbers. For a given integer n to determine whether it is prime, the test is 100% accurate if it labels that number as a composite. However, the other case where the test output is prime is not always true, that is to say, there is always a probability that a composite number passes the test and is labeled as prime. To decrease this probability and increase the accuracy of the test, we always need to repeat the test for several times. As examples of probabilistic tests, we provide explanations on Euler's Test, 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 a given number n as composite, the number is, in fact, composite. Additionally, deterministic tests also guarantee the primality of numbers. However, the running time of 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, its accuracy and drawbacks. Moreover, elliptic curve primality testing methods and theorems are widely used. Although some algorithms require very long execution time for several-million digit integers, the results are deterministic. Thus, we include Shafi-Killian and Atkin's elliptic curve primality proving algorithms into our analyses. In this thesis, general mathematical theorems which are very fundamental in number theory are explained to the reader. Then, their applications on primality testing are given by commonly used primality test algorithms. The current algorithms analyzed in terms of computational complexity, illustrated with examples to make the algorithms clearer and finally evaluated with its advantages and disadvantages. This literature review 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 for comparison. Finally, the theoretical and experimental comparison results are provided in the last chapter. Known primality tests are compared to the singular cubic primality test by using the same dataset which includes both primes and composites with different number of digits. Implementation and testing phrases show that the singular cubic curve algorithm catches all composite number up to 1021 which were strong pseudoprimes to base 2 according to commercially used Miller-Rabin test. Additionally, it successfully detects the compositeness of large integers that have several hundred digits. Thus, singular cubic curve algorithm is a candidate to be a primality testing algorithm with running time of O(log^{2+e}n).

Benzer Tezler

  1. Tez No

    851605

    Ritim becerisinin ölçülmesi bağlamında ritmik kompleksite ölçekleri üzerine karşılaştırmalı bir inceleme

    Rhythmic complexity and a comparative study on rhythmic complexity measures in the context of measuring rhythm skills

    CİHAN YAYGIN

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Müzikİstanbul Teknik Üniversitesi

    Müzikoloji ve Müzik Teorisi Ana Bilim Dalı

    DOÇ. DR. OZAN BAYSAL

  2. Tez No

    849728

    Enhancing follow the gap method with memory aid and with prediction component

    Boşluğu takip et yönteminin hafıza desteği ile ve öngörü bileşeni ile geliştirilmesi

    EMRE CAN CONTARLI

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    DOÇ. DR. VOLKAN SEZER

  3. Tez No

    219690

    Türkiye'de seramik eğitimi veren yüksek öğrenim kurumlarına öğrenci seçmede uygulanan sınavların yeterliliği

    The proficiency of special ability tests for the üniversities choosing students for ceramic education

    NESİME EMEL ORTAÇ ARI

    Yüksek Lisans

    Türkçe

    Türkçe

    2008

    Eğitim ve ÖğretimGazi Üniversitesi

    Eğitim Bilimleri Bölümü

    YRD. DOÇ. DR. OLCAY BORATAV

  4. Tez No

    310655

    Çok kriterli karar verme yöntemi ile yazılım geliştirme metodolojisi seçimi

    Software development methodologies selection with multi criteria decision making

    FURKAN ANARAL

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. TUFAN VEHBİ KOÇ

  5. Tez No

    103525

    Romatoid artritli hastalarda akciğer tutulumunun yüksek rezolüsyonlu bilgisayarlı tomografi ve solunum fonksiyon testleri ile değerlendirilmesi ve bulguların diğer hastalık parametreleri ile karşılaştırılması

    Assessment of pulmonary invovement in patients with rheumatoid arthritis by using high resolution computerized tomography and pulmonary function testing and comparison of the findings with other disease parameters

    NECİP GÜDER

    Tıpta Uzmanlık

    Türkçe

    Türkçe

    2001

    Fiziksel Tıp ve RehabilitasyonSüleyman Demirel Üniversitesi

    Fiziksel Tıp ve Rehabilitasyon Ana Bilim Dalı

    Y.DOÇ.DR. SELAMİ AKKUŞ

Geri Dön