Polinom zamanlı bir asallık algoritması
A polynomial time primality algorithm
- Tez No: 530514
- Danışmanlar: DOÇ. DR. MURAT ŞAHİN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Asal sayı, deterministik algoritma, polinom zamanlı algoritma, asallık testleri, AKS, Prime number, deterministic algorithm, polynomial time algorithm, primality tests, AKS
- Yıl: 2018
- Dil: Türkçe
- Üniversite: Ankara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 55
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- The evaluation and comparison of primality testing algorithms
Asallık testi algoritmalarının incelenmesi ve karşılaştırılması
GÖZDE SARIKAYA
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
DOÇ. DR. ENVER ÖZDEMİR
- A research on the variations of the quadratic sieve integer factoring algorithm
Tamsayıları çarpanlara ayırma yöntemi kuadratik elek algoritmasının varyasyonlarının araştırılması
SUAT KARADENİZ
- Computational complexity of list coloring and ıts variants for particular graph classes
Liste renklendirme probleminin ve varyantlarının belirli çizge sınıfları için hesaplama karmaşıklığı
BANU BAKLAN ŞEN
Doktora
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKadir Has ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ÖZNUR YAŞAR DİNER
- A Polyhedral approach to quadratic assignment problem
Karesel atama problemine polyhedral bir yaklaşım
AHMET SERTAÇ MURAT KÖKSALDI
Yüksek Lisans
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA AKGÜL
- Karmarkar iç nokta algoritması ve bir üretim işletmesinde uygulama denemesi
Başlık çevirisi yok
GÜLNUR KEÇEK