Automated linear algebra for modern integer factorization algorithms

Abstract

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.

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.