Large sparse matrix-vector multiplication over finite fields

Abstract

Çarpanlara ayırma ve ayrık logaritma hesaplama gibi kriptografik işlemler sonlu cisimler üzerinde büyük ve seyrek denklem sistemlerinin çözümünü gerektirmektedir. Bu işlemler için Wiedemann ve Lanczos gibi yinelemeli yöntemler benimsenmektedir. Her iki algoritmada da matris-vektör çarpımlarının baskın olduğu hesaplamalar kullanılmaktadır. Bu tezde, sonlu cisimler üzerinde büyük seyrek matris-vektör çarpma işlemine yönelik bir algoritma önerilmiştir. Söz konusu algoritmanın performansı klasik yöntemle kıyaslanmış ve %34 ile %77 arasında hızlanma sağlanmıştır.

Cryptographic computations such as factoring integers and computing discrete logarithms require solving a large sparse system of linear equations over finite fields. When dealing with such systems iterative solvers such as Wiedemann or Lanczos algorithms are used. The computational cost of both methods is often dominated bysuccessive matrix-vector products. In this thesis, we introduce a new algorithm for computing a large sparse matrix-vector multiplication over finite fields. The proposed algorithm is implemented and its performance is compared with a classical method. Our algorithm exhibits a significant improvements between 34% and 77%.