Geri Dön

Polinom zamanlı bir asallık algoritması

A polynomial time primality algorithm

  1. Tez No: 530514
  2. Yazar: SÜLEYMAN SERKAN ÖZÇİM
  3. Danışmanlar: DOÇ. DR. MURAT ŞAHİN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Asal sayı, deterministik algoritma, polinom zamanlı algoritma, asallık testleri, AKS, Prime number, deterministic algorithm, polynomial time algorithm, primality tests, AKS
  7. Yıl: 2018
  8. Dil: Türkçe
  9. Üniversite: Ankara Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2019

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

    Bilişim Uygulamaları Ana Bilim Dalı

    DOÇ. DR. ENVER ÖZDEMİR

  2. 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

    Yüksek Lisans

    İngilizce

    İngilizce

    2008

    MatematikFatih Üniversitesi

    Matematik Bölümü

    PROF. DR. BARIŞ KENDİRLİ

  3. 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

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKadir Has Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ÖZNUR YAŞAR DİNER

  4. A Polyhedral approach to quadratic assignment problem

    Karesel atama problemine polyhedral bir yaklaşım

    AHMET SERTAÇ MURAT KÖKSALDI

    Yüksek Lisans

    İngilizce

    İngilizce

    1994

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

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

    DOÇ. DR. MUSTAFA AKGÜL

  5. Karmarkar iç nokta algoritması ve bir üretim işletmesinde uygulama denemesi

    Başlık çevirisi yok

    GÜLNUR KEÇEK

    Doktora

    Türkçe

    Türkçe

    2002

    İşletmeAnadolu Üniversitesi

    İşletme Ana Bilim Dalı

    YRD. DOÇ. DR. MAHMUT ATLAS