On Prime Number Test Algorithms and Applications in Cryptology

Abstract

Bu tez çalışması beş ana bölümden oluşmaktadır. Birinci bölümde asal sayı testleri hakkında günümüze kadar olan çalışmalar ile ilgili bilgi verilmiş ve asal sayı testlerinin önemi vurgulanmıştır. İkinci bölümde asal sayı test algoritmaları hakkında kaynak taraması yapılmıştır. Üçüncü bölümde çalışmamız boyunca kullanabileceğimiz bilgiler ve asal sayılarla ilgili temel özellikler ile kuadratik rezidülerle ilgili temel tanım ve teoremlere yer verilmiştir. Bu bilgiler özellikle Slovay-Strassen testinin uygulanması için gereklidir. Dördüncü bölümde Fermat, Euler, Miller-Rabin ve Slovay-Strassen olasılıksal (probabilistic) ve AKS kesin (deterministic) asallık testlerine geniş yer verilmiş ve bazı açık anahtarlı şifreleme algoritmalarından kısaca bahsedilip somut örnekler verilmiştir. Son bölümde ise tezin değerlendirildiği tartışma ve sonuç kısmına yer verilmiştir.

This thesis consists of five chapters. In the first chapter, some information about the prime number test algorithms is given and the importance of prime numbers in cryptography is introduced. In the second chapter, the studies in the literature about probabilistic and deterministic primality test algorithms are given. In the third chapter, the fundamental definitions and properties about primes and quadratic residues used in the following chapters are given. These are necessary especially for the application of Slovay-Strassen probabilistic primality test. In the fourth chapter; Fermat, Euler, Miller-Rabin and Slovay-Strassen probabilistic primality tests and AKS deterministic primality test are mentioned in details, also some public key encryption schemes are briefly mentioned with concrete examples. Finally, the last chapter consists of discussion and conclusion which is an evalution of the thesis.