Geri Dön

Automated linear algebra for modern integer factorization algorithms

Modern tamsayı faktorizasyon algoritmaları için otomatik lineer cebir

PDF İndir

  1. Tez No: 526612
  2. Yazar: FİLİNTA BEDİRHAN YILDIZ
  3. Danışmanlar: DR. ÖĞR. ÜYESİ HÜSEYİN HIŞIL
  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: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: Yaşar Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Bu tez, Magma dili ile yazılmış lineer cebir betiklerini optimize C kodlarına dönüştüren bir aracın geliştirilmesi üzerindedir. Kuadratik Elek (QS) ve Sayı Cismi Eleği (NFS) gibi tamsayıları çarpanlarına ayırma algoritmaları büyük bir seyrek (sparse) matris üretir. Bu matrisin çekirdeğinin (nullspace), hem QS'nin hem de NFS'nin ana adımlarından biri olarak hesaplanması gerekir. Çekirdeği (nullspace) hesaplayan en uygun algoritmalar (dağıtılmış) iedemann ve (paralel) Blok Lanczos algoritmalarıdır. Her iki algoritma, yüksek seviyeli bir bilgisayar cebiri aracı üzerinde örneğin Magma, oldukça kolay bir şekilde uygulanabilmektedir. te yandan, bu algoritmaların C dilinde işlemciler bilgisayarlar arasında paralellik sağlacak optimize bir sekilde uygulanması oldukça zahmetlidir. Bu tez çalışması, Block Lanczos ve Block Wiedemann algoritmaları bağlamında yazılmış bir Magma betiğini, TCP IP ağı üzerinden paralellik sağlayabilecek sekilde optimize edilmiş bir C kodu üreten bir araç sağlamaktadır.

Özet (Çeviri)

This thesis is on the development of a tool that can convert linear algebra scripts written in Magma language to optimized C codes. Integer factorization algorithms such as Quadratic Sieve (QS) and Number Field Sieve (NFS) produces a large sparse matrix. The nullspace of this matrix is computed as one of the main steps of both QS and NFS. The most convenient algorithms that compute the nullspace are: (distributed) Block Wiedemann and (parallel) Block Lanczos algorithms. Both algorithms are fairly easily implemented on a high level computer algebra tool e.g. Magma. On the other hand, implementing these algorithms in C language in an optimized fashion allowing parallelism between processors/computers is tedious. This thesis work provides a tool that inputs a Magma script written in the context of Block Lanczos and Block Wiedemann algorihtms and outputs an optimized C code which is capable of providing parallelism over a TCP/IP network.

Geri Dön