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
An improved algorithm for iterative matrix-vector multiplications over finite fields
Date
2018-11-09
Author
Mangır, Ceyda
Cenk, Murat
Manguoğlu, Murat
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
135
views
0
downloads
Cite This
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 proposed algorithm consists of two stages. The first stage (preprocessing) sorts the elements of the matrix row by row in ascending order and produces permutation tables. After preprocessing, many consecutive multiplications can be performed by the second stage of the algorithm using sequential additions on vector elements by the guidance of the permutation tables. We show that the preprocessing cost of the proposed algorithm can easily be amortized after several matrix-vector multiplications are performed. We implemented the algorithm using the C++ programming language and compared the performance with a classical method. The proposed algorithm exhibits significant improvement between 35% and 67% .
Subject Keywords
Matrix-vector multiplication
,
Index calculus algorithm
,
Wiedemann
,
Lanczos
URI
https://hdl.handle.net/11511/31437
DOI
https://doi.org/10.1007/978-3-030-12942-2_27
Collections
Graduate School of Applied Mathematics, Conference / Seminar
Suggestions
OpenMETU
Core
A New Algorithm for Residue Multiplication Modulo 2(521)-1
Ali, Shoukat; Cenk, Murat (2016-12-02)
We present a new algorithm for residue multiplication modulo the Mersenne prime p = 2(521) - 1 based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison - according to the best of our knowledge with respect to the well-known algori...
On the arithmetic complexity of Strassen-like matrix multiplications
Cenk, Murat (2017-05-01)
The Strassen algorithm for multiplying 2 x 2 matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension n yields a total arithmetic complexity of (7n(2.81) - 6n(2)) for n = 2(k). Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 x 2 matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Stras...
Large sparse matrix-vector multiplication over finite fields
Mangır, Ceyda; Cenk, Murat; Manguoğlu, Murat; Department of Cryptography (2019)
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 im...
On the computation of generalized division polynomials
Küçüksakallı, Ömer (2015-01-01)
We give an algorithm to compute the generalized division polynomials for elliptic curves with complex multiplication. These polynomials can be used to generate the ray class fields of imaginary quadratic fields over the Hilbert class field with no restriction on the conductor.
An interactive algorithm for multiobjective ranking for underlying linear and quasiconcave value functions
TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (Wiley, 2019-07-29)
We develop interactive algorithms to find a strict total order for a set of discrete alternatives for two different value functions: linear and quasiconcave. The algorithms first construct a preference matrix and then find a strict total order. Based on the ordering, they select a meaningful pair of alternatives to present the decision maker (DM) for comparison. We employ methods to find all implied preferences of the DM, after he or she makes a preference. Considering all the preferences of the DM, the pre...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
C. Mangır, M. Cenk, and M. Manguoğlu, “An improved algorithm for iterative matrix-vector multiplications over finite fields,” 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31437.