Geri Dön

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

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

  1. Tez No: 614829
  2. Yazar: GULİDA KIMSANOVA
  3. Danışmanlar: DOÇ. DR. RAYIMBEK SULTANOV
  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: Tam sayıları çarpanlarına ayırma, GMP, Deneme bölmesi, Fermat'ın çarpanlara ayırma metodu, Pollard'ın rho algoritması, Brent metodu algoritması
  7. Yıl: 2016
  8. Dil: Kırgızca
  9. Üniversite: Kırgızistan-Türkiye Manas Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 65

Özet

Көптөгөн ачык ачкычтуу криптосистемалардын негизи катары колдонулган натуралдык санды факторизациялоо проблемасы заманбап компьютерлер үчүн да оор маселе болуп саналат. Бул иште 4 алгоритмдин – Тривиалдык бөлүү, Ферма, Поллард rho, Брент алгоритмдеринин программасы 3 жол менен түзүлдү Алгач, С++ тилинде GMP китепканасын колдонуу менен, экинчи жолу графикалык процессорду колдонуу үчүн CUDA архитектурасына С тилинде жана акыркы учур, эч нерсе колдонулбастан С тилинде ар бир алгоритм үчүн программдык код жазылды. Андан соң, алынган программдык жабдыкты колдонуп, бул алгоритмдердин иштөө убактыларын салыштыруу анализин жүргүздүк. Алгоритмдер ар кандай өлчөмдөгү сандарды, ошондой эле факторлорунун ортосунда ар кандай аралык болгон сандарды факторизациялоо үчүн колдонулду. Биздин жыйынтыктар: GMP китепканасын колдонгон учурда 296 биттик санды факторлорго ажыратууда Поллард rho алгоритминин эң бат иштешин, ошол эле учурда, факторлордун ортосундагы аралык кичине болгон учурда Ферма алгоритминин эң бат иштешин көрсөттү. Мындай сандар үчүн Брент алгоритминин жай иштегени байкалды, бирок бул алгоритм Ферма алгоритми натыйжа бере албаган учурларда ийгиликтүү жыйынтык бере алды. CUDA архитектурасын колдонгон учурда параллель эсептөөдө Ферма жана Тривиалдык бөлүү алгоритмдеринин бат иштегенин байкай алдык. Ал эми эч нерсе колдонулбастан С тилинде жазылган программада Брент алгоритминин калган эки учурга салыштырмалуу бир канча эсе бат иштегени байкалды. vii Ачкыч Сөздөр: Натуралдык сандын факторизациясы, GMP,Тривиалдык бөлүү, Ферма алгоритми, Поллард rho алгоритми, Брент алгоритми

Özet (Çeviri)

Kriptoloji, kriptografik sistemler bilimidir. Kriptoloji bilimi kendi içerisinde iki farklı branşa ayrılır. Bunlar Kriptografi; şifreli yazı yazma ve Kriptoanaliz; şifreleri çözme ya da analiz etmedir. Neden Kriptografik sistemleri kullanıyoruz sorusunun cevabı aşağıdaki bilgilerde bulunuyordur: Gizlilik (confidentiality): Bilgiyi görme yetkisi olanlar dışındaki herkesten gizli tutmak. Kimlik denetimi (authentication): İletimi gerçekleştirilen bir mesajın göndericisinin gerçekten gönderen kişi olduğu garantisi.Bütünlük (integrity): Bütünlük bir bağlantının tamamı ya da tek bir veri parçası için, mesajın gönderildiği gibi olduğuna, üzerinde hiçbir değişiklik, ekleme, yeniden düzenleme yapılmadığı garantisi. Kriptoloji, çok eski ve renkli bir geçmişe sahiptir. Tarihten günümüze kadar, bazı şifreleme teknikleri şunlardır:  Sezar şifrelemesi  Rotor makinesi (Enigma)  Açık anahtarlı şifreleme  Çırpı fonksiyonları  Veri gizleme teknikleri Açık anahtarlı şifreleme tarihi 1976'den başlanıyor, yani 1997'de bir kaç insanın aynı fikirde olduğunu gösteren bilgi yayınlanana kadar öyle olduğuna inanılmıştır. 1976 yılında Whitfield Diffie ve Martin Hellman tarafından“New Directions in Cryptography”isimli makale yayımlanmıştır. Makale kriptografide bir devrim oluşturmakla birlikte, matematik alanında da yeni yöntemlerin oluşmasına ve gelişmesine neden olmuştur. Açık anahtarlı şifreleme, şifre ve deşifre işlemleri için farklı anahtarların kullanıldığı bir şifreleme sistemidir. Haberleşen taraflardan her birinde birer çift anahtar bulunur. Bu anahtar çiftlerini oluşturan anahtarlardan biri gizli xii anahtar diğeri açık (gizli olmayan) anahtardır. Bu anahtarlardan bir tanesiyle şifreleme yapılırken diğeriyle de şifre çözme işlemi gerçekleştirilir. Bu iki anahtar çifti matematiksel olarak birbirleriyle bağlantılıdır. Whitfield Diffie ve Martin Hellman gizli tek yönlü fonksiyon kullanarak açık anahtarlı şifreleme sistemini oluşturmuştur, ama onlar bu işlemi gerçekleştirebilmek için uygun bir fonksiyon teklif etmemiştir. Ancak, 1977 yılında amerikalı uzmanlar: Ron Rivest, Adi Shamir ve Leonard Adleman MIT'de böule bir fonksiyonu bulmuştur. O fonksiyon üzerine uygulanmış sistem 'RSA sistemi' adıyla bilinmiş bir sistemdir. RSA harfleri soyisimlerinin baş harflerini temsil etmektedir. RSA, güvenliği tam sayıları çarpanlarına ayrımanın algoritmik zorluğuna dayanan bir tür Açık anahtarlı şifreleme yöntemidir. Asal çarpanlarına ayırma zor bir problem olarak sayılır. Bu problemin bilinen bir çözümü yoktur. Sayılar çok büyük olduğunda, kuantum olmayan hızlı bir algoritma bilinmemektedir RSA gibi çok sayıda kriptografik protokol bu problemin veya bir benzerinin zorluğuna dayanmaktadır. Bir başka deyişle eğer bir sayıyı hızlı bir şekilde çarpanlara ayırma algoritması bulunsaydı, RSA tabanlı açık anahtar kriptografisi güvenliğini yitirirdi. Aşağıda çarpanlara ayırma algoritmalarının türleri gösterilmiştir:  Amaca özel  Genel amaçlı Amaca özel bir çarpanlara ayırma algoritmasının çalışma zamanı, çarpanlara ayrılmaya çalışan sayının veya bilinmeyen çarpanlarından birinin özelliklerine bağlıdır. Genel amaçlı çarpanlara ayırma algoritmalarının çalışma süreleri sadece çarpanlarına ayrılacak olan sayının büyüklüğüne bağlıdır. Amaca özel çarpanlara ayırma algoritmaları:  Deneme bölmesi  Tekerlek çarpanlara ayırma yöntemi  Pollard'ın rho algoritması  Cebirsel-grup çarpanlara ayırma algoritmaları:Pollard'ın p - 1 algoritması  Williams'ın p + 1 algoritması  Lenstra eliptik eğri çarpanlara ayırma yöntemi xiii  Fermat'ın çarpanlara ayırma metodu  Euler'in çarpanlara ayırma metodu  Özel sayı cismi eleme yöntemi Bu çalışmada, 4 tane sayıları çarpanlarına ayırma algoritmalarının; Deneme bölmesi, Fermat'ın çarpanlara ayırma metodu, Pollard'ın rho algoritması ve Brent metodu algoritmalarının uygulaması yapılmıştır. Uygulama hem CPU, hem de GPU için ayrı gerçekleştirilmiştir. İlk olarak, CPU üzerindeki uygulama herhangi bir kütüphaneler kullanılmadan, saf C kodu üzerinde yazılmıştır. İkinci, algoritmalar, C++ üzerinde GMP kütüphanesi kullanılarak uygulanmıştır. Son olarak, algoritmalar, GPU'de CUDA mimarisi kullanılarak uygulanmıştır. Uygulama aşamasından sonra, algoritmaların çalışma süreleri ölçülmüştür, karşılaştırılmıştır ve analiz edilmiştir. Algoritmalar, farklı boyutlardaki sayılar ve sayı çarpanlarının arasındaki mesafe farklı olan sayılar için kullanılmıştır. Sonuçlara göre, C++ üzerinde GMP kütüphanesi kullanılmış durumda, faktörler arasındaki mesafeler küçük sayılar için Fermat algoritmasının, aynı zamanda, boyutu 296 bit üzerindeki sayılar için de Pollard'ın rho algoritmasının hızlı çalıştığı gözlemlenmiştir. Brent algoritmasının yukarıda bahsedilen sayılar için yavaş çalışmasına rağmen, Fermat algoritmasının başarısız olduğu, sayıları çarpanlara ayırmada, başarılı olmuştur. Fermat ve Deneme bölmesi algoritmalarının, CUDA mimarisi üzerinde paralel uygulanmasında, hızlı çalışma süresi gözlemlenmiştir. Ancak, saf C uygulamasında, Brent algoritması, diğer uygulamalara göre birkaç kez hızlı çalışmıştır. xiv

Benzer Tezler

  1. Tez No

    615143

    Ideal olmayan ve izotermal olmayan reaktörlerin matlab ile perfomans simulasyonu

    Идеалдуу эмес жана изотермал эмес реакторлордун иштөөсүнүн матлабды колдонуу менен симуляциясы

    ALİMCAN KALBEKOV

    Yüksek Lisans

    Türkçe

    Türkçe

    2018

    Kimya MühendisliğiKırgızistan-Türkiye Manas Üniversitesi

    Kimya Mühendisliği Ana Bilim Dalı

    PROF. DR. SELAHATTİN GÜLTEKİN

  2. Tez No

    614902

    Bedreddîn ez-Zerkeşî'nin 'el-Burhân fî ulûmi'l kur'an' adlı eserinin ulûmu'l-kur'an bağlamında değerlendirilmesi

    Бадруддин аз-заркашийдин 'ал-бурхан фии улумил куран' аттуу эмгегинкуран илимдери жаатында баалоо

    ŞOHİMARDAN ORUNBEKOV

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    DinKırgızistan-Türkiye Manas Üniversitesi

    İslam Bilimleri Ana Bilim Dalı

    DOÇ. DR. HÜSEYİN ÇELİK

  3. Tez No

    896592

    Жогорку окуу жайларды санариптештирүүдө компьютер тармагынын өндүрүмдүүлүгүнүн ролу

    The role of computer networks productivity in the digitization of higher education institutions

    AYCARKIN SAIT KIZI

    Doktora

    Kırgızca

    Kırgızca

    2023

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. RİTA İSMAILOVA

  4. Tez No

    613365

    İlköğretim 8. sınıf fizik dersi programının Kırgızistan ve Türkiye eğitim sistemlerinde karşılaştırmalı olarak incelenmesi

    Сравнитель ный анализ учебных планов по предмету физика для 8-х классов вкыргызской и турецкой образовательных системах

    GÜRKAN AKBABA

    Yüksek Lisans

    Türkçe

    Türkçe

    2011

    Eğitim ve ÖğretimKırgızistan-Türkiye Manas Üniversitesi

    Eğitim Bilimleri Ana Bilim Dalı

    DR. KADİYA BOOBEKOVA

  5. Tez No

    615531

    Bağımsızlık sonrası Kırgız tarihi biyografik romanı

    Эгемендүүлүктөн кийинки кыргыз тарыхый биографиялык романдары

    HALİT AŞLAR

    Doktora

    Türkçe

    Türkçe

    2012

    Türk Dili ve EdebiyatıKırgızistan-Türkiye Manas Üniversitesi

    Türkoloji Ana Bilim Dalı

    PROF. DR. LAYLİ ÜKÜBAYEVA

    PROF. DR. ORHAN SÖYLEMEZ

Geri Dön