Akademik Veri Yönetim Sistemi
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Ankara Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye
Tezin Onay Tarihi: 2018
Tezin Dili: Türkçe
Öğrenci: SÜLEYMAN SERKAN ÖZÇİM
Danışman: MURAT ŞAHİN
Özet:Bir n pozitif tamsayısının 1 ve kendisinden başka pozitif böleni yoksa bu sayıya asal sayı denir. Asal sayıların sonsuz çoklukta olduğu ve her pozitif tam sayının asal sayıların çarpımı şeklinde tek türlü yazıldığı Euclid tarafından ispatlanmıştır. Ayrıca bir n pozitif tamsayısının asal olup olmadığını anlamak için çok eski çağlardan bu yana birçok yöntem geliştirilmiştir ve bu konu sayılar teorisinin temel problemlerinden birisidir. Bu tez altı bölümden oluşmaktadır. Giriş bölümünde Antik Yunan'dan (M.Ö. 300) Hindistan'a (2004) uzanan süreçte bir sayının asal olup olmadığını anlamak için ortaya çıkartılan algoritmalardan bahsedilmiştir ve tezin amacı açıklanmıştır. İkinci bölümde tez boyunca kullanılacak temel bilgiler verilmiştir. Tezin üçüncü bölümünde Lucas tarafından bulunan n-1 testine yer verilmiş ve Lucas'ın fikri açıklanmıştır (Özetle: Öyle büyük bir grup inşa et ki n asal olsun). Dördüncü bölümde ise Lucas dizileri yardımıyla elde edilen n+1 testinden bahsedilmiş ve özel olarak sadece Mersenne sayılarının asallığını belirleyen Lucas-Lehmer testi anlatılmıştır. Beşinci bölümde Lenstra tarafından bulunan sonlu cisimlerde asallık testi verilmiştir. Son bölümde ise diğer asallık algoritmalarının arkasındaki fikir geliştirilerek elde edilen, Agrawal, Kayal ve Saxena tarafından bulunan deterministik ve polinom zamanlı bir algoritma AKS verilmiştir. Anahtar Kelimeler: Asal sayı, deterministik algoritma, polinom zamanlı algoritma, asallık testleri, AKS A Positive integer is called prime if it has no positive factor except 1 and itself. There are infinitely many primes and any positive integer can be written uniquely as a product of primes. Euclid proved these two theorems. To determine whether n is a prime or a composite number many algorithms developed over the years and this subject became one of the main problems of the number theory. This thesis consist of six chapters. In the first chapter, the aim of the thesis is explained and the introduction mentioned some algorithms from Ancient Greek (B. C. 300) to India (2004). In the second chapter some basic concepts are given that will be used later. In the third chapter, Lucas's the n-1 test explained the idea of Lucas (build up a group so large that n must be prime). In the fourth section, there is an algorithm known as n+1 test which includes Lucas sequences and is useful for Mersenne numbers. The fifth section is for finite field primality test which found by Lenstra. In the last section, showed deterministic and polynomial time primality algorithm AKS which is obtained from the idea that behind the other primality tests. Key Words: Prime number, deterministic algorithm, polynomial time algorithm, primality tests, AKS