Large sparse matrix-vector multiplication over finite fields

Download

index.pdf

Date

2019

Author

Mangır, Ceyda

Metadata

Show full item record

Item Usage Stats

299
views

129
downloads

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 by successive 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%.

Subject Keywords

Logarithms., Cryptography., Sparse matrices., Data encryption (Computer science).

URI

http://etd.lib.metu.edu.tr/upload/12623107/index.pdf
https://hdl.handle.net/11511/28018

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

An improved algorithm for iterative matrix-vector multiplications over finite fields Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat (2018-11-09) Cryptographic computations such as factoring integers and computing discrete logarithms over finite fields require solving a large system of linear equations. When dealing with such systems iterative approaches such as Wiedemann or Lanczos are used. Both methods are based on the computation of a Krylov subspace in which the computational cost is often dominated by successive matrix-vector products. We introduce a new algorithm for computing iterative matrix-vector multiplications over finite fields. The pro...
Modular exponentiation methods in cryptography Yünüak, Hasan Bartu; Cenk, Murat; Department of Cryptography (2017) Modular exponentiation has an important role in many cryptographic algorithms. These exponentiation methods differ in the bases used and their representations, the repeating aspect, and for which algorithms they are used for: fixed or variable base. Our research aims to compare the efficiencies and implementation timings for some selected algorithms. Also, we look at the options for using a dedicated cubing algorithm, and compare them with the current algorithms.
Solving Constrained Optimal Control Problems Using State-Dependent Factorization and Chebyshev Polynomials Gomroki, Mohammad Mehdi; Topputo, Francesco; Bernelli-Zazzera, Franco; Tekinalp, Ozan (2018-03-01) The present work introduces a method to solve constrained nonlinear optimal control problems using state-dependent coefficient factorization and Chebyshev polynomials. A recursive approximation technique known as approximating sequence of Riccati equations is used to replace the nonlinear problem by a sequence of linear-quadratic and time-varying approximating problems. The state variables are approximated and expanded in Chebyshev polynomials. Then, the control variables are written as a function of state ...
Sparse polynomial multiplication for lattice-based cryptography with small complexity Akleylek, Sedat; Alkim, Erdem; Tok, Zaliha Yuce (2016-02-01) In this paper, we propose efficient modular polynomial multiplication methods with applications in lattice-based cryptography. We provide a sparse polynomial multiplication to be used in the quotient ring (Z/pZ)[x]/(x(n) + 1). Then, we modify this algorithm with sliding window method for sparse polynomial multiplication. Moreover, the proposed methods are independent of the choice of reduction polynomial. We also implement the proposed algorithms on the Core i5-3210M CPU platform and compare them with numbe...
Character sums of quadratic forms over finite fields and the number of rational points for some classes of artin-schreier type curves Coşgun, Ayhan; Doğanaksoy, Ali; Department of Mathematics (2017) Exponential sums of quadratic forms over finite fields have many applications to various areas such as coding theory and cryptography. As an example to these applications, there is an organic connection between exponential sums of quadratic forms and the number of rational points of algebraic curves defined over finite fields. This connection is central in the application of algebraic geometry to coding theory and cryptography. In this thesis, different facts and techniques of theory of finite fields are co...

Citation Formats

C. Mangır, “Large sparse matrix-vector multiplication over finite fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2019.