Geri Dön

Bölmeli asal sayı kalbur algoritmaları: Yeni ve pratik bir algoritma

Segmented prime number sieve algorithms: A new and efficient algorithm

  1. Tez No: 252642
  2. Yazar: GÖRKEM TOKATLI
  3. Danışmanlar: PROF. DR. MEHMET EMİN DALKILIÇ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Asal sayılar, Goldbach sanısı, kalbur algoritmaları, Prime numbers, Segmented prime sieve, Segmented Sieve of Pritchard, Goldbach Conjecture
  7. Yıl: 2009
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 124

Özet

Asal sayılar, sahip oldukları özel ve kuralsız yapılarıyla teorik olarak birçok bilim insanının ilgisini çekmiştir. Yıllar boyunca bütün asal sayıları bulan polinom yapıda tek bir formülün var olabileceğine inanılmış, fakat bulunamamıştır. Bunun yanı sıra bilgi güvenliği alanında özellikle açık anahtar şifrelemelerinde sıklıkla kullanılmaktadır.Tez çalışmamızın başlangıcında, asal sayıların özelliklerini, sayı sisteminde dağılımlarını, belirli bir sayı aralığındaki asal sayıları bulmaya yarayan kalbur algoritmalarını inceledik. Bunların paralelinde, dörtten büyük bütün çift sayının iki adet asal sayının toplamı olacağını öngören Goldbach sanısı üzerinde çalışıp, bu iddianın kanıtı veya çürütülmesi üzerinde istatistiksel incelemeler yapıp, deneme algoritmalarını inceledik.Sonrasında, günümüzün en popüler ve verimli bölmeli kalbur algoritmalarını inceleyip, bunlardan yola çıkarak teoride 33% `e kadar daha hızlı çalışabilen yeni bir algoritma geliştirdik. Bu aşamadan sonra çalışmalarımızı tamamen bu algoritma üzerine yoğunlaştırdık. Algoritmanın tek makine üzerinde implementasyonu beklenen sonuçları verince algoritmanın paralelleştirilmesi üzerine çalışmalara başladık. Verimli bir paralel algoritmanın geliştirilmesinden sonra İTÜ UYBHM grid sistemlerinde çalıştırarak karşılaştırmalı performans ölçümleri yapıp beklenen sonuçları elde ettik.

Özet (Çeviri)

Prime numbers have always been an interesting subject for mathematicians due to their irregular and different structures. It is believed that there is a universal polinomial formula that will extract all prime numbers directly, but that is proven wrong. Furthermore, prime numbers are needed and frequently used in information security, especially in public key cryptology.At the beginning of our thesis study, we have made research on prime number properties and distributions. Then we have examined prime number sieve algorithms. Simultaneously, we have studied the Goldbach Conjecture, which claims that any even number that is bigger than four can be shown as the sum of two prime numbers. We have worked on statistical approaches, and brute force algorithms which are used for proving or disproving the conjecture.Afterwards, we have studied the most populer segmented prime sieve algorithms, and developed a new algorithm which is up to 33% faster. At that point we have focused on this algorithm. After the successful implementation on single machine, we have worked on parallelizing the algorithm. We have developed the parallel version and run on ITU UYBHM grid system in compare with the most populer segmented sieve algorithm, and the results were similar to our expectations.

Benzer Tezler

  1. γ-Butson-Hadamard matrices and their cryptographic applications

    γ-Butson-Hadamard matrisleri ve onların kriptografik uygulamaları

    SİBEL KURT

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    MatematikHacettepe Üniversitesi

    Matematik Ana Bilim Dalı

    YRD. DOÇ. DR. OĞUZ YAYLA

  2. Бүтүн сандык факторизация алгоритмдери. эмпирикалык иш жүзүнө ашыруу жана иштөө убактысын анализдөө

    Tamsayı çarpanlara ayırma algoritmaları. Empirik uygulanması ve çalışma suresi analizi

    GULİDA KIMSANOVA

    Yüksek Lisans

    Kırgızca

    Kırgızca

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKırgızistan-Türkiye Manas Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. RAYIMBEK SULTANOV

  3. Sequence families with good correlation distribution

    İyi korelasyon dağılımlı dizi aileleri

    EDA TEKİN

    Doktora

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Kriptografi Ana Bilim Dalı

    PROF. DR. FERRUH ÖZBUDAK

  4. GaAs MESFET karıştırıcılarda AF geribeslemenin gürültü sayısı üzerine etkisi

    The Effect of if feedback on MESFET mixers noise figure

    RIZA SEZER

    Yüksek Lisans

    Türkçe

    Türkçe

    1991

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. OSMAN PALAMUTÇUOĞULLARI

  5. Oscillation problems of the closed seas

    Kapalı denizlerin salınım problemleri

    SİNAN ÖZEREN

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Jeoloji Mühendisliğiİstanbul Teknik Üniversitesi

    Meteoroloji Mühendisliği Ana Bilim Dalı

    PROF. DR. H. NÜZHET DALFES