Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
273
views
115
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
C. Mangır, “Large sparse matrix-vector multiplication over finite fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2019.