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
A New Algorithm for Residue Multiplication Modulo 2(521)-1
Date
2016-12-02
Author
Ali, Shoukat
Cenk, Murat
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
164
views
0
downloads
Cite This
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 algorithms and to show the robustness of our algorithm for this 521-bit Mersenne prime modulus. Each version is having less number of operations than its counterpart. On our machine, Intel Pentium CPU G2010 @ 2.80 GHz machine with gcc 5.3.1 compiler, we find that for each version of our algorithm modulus p is more efficient than modulus 2p. Hence, by using Granger and Scott code, constant-time variable-base scalar multiplication, for modulus p we find 1, 251, 502 clock cycles for P-521 (NIST and SECG curve) and 1, 055, 105 cycles for E-521 (Edwards curve). While, on the same machine the clock cycles counts of Granger-Scott code (modulus 2p) for P-521 and E-521 are 1, 332, 165 and 1, 148, 871 respectively.
Subject Keywords
Residue multiplication
,
Toeplitz matrix-vector product
,
Mersenne prime
,
Elliptic curve cryptography
URI
https://hdl.handle.net/11511/32521
DOI
https://doi.org/10.1007/978-3-319-53177-9_9
Collections
Graduate School of Applied Mathematics, Conference / Seminar
Suggestions
OpenMETU
Core
Faster Residue Multiplication Modulo 521-bit Mersenne Prime and an Application to ECC
Ali, Shoukat; Cenk, Murat (2018-08-01)
We present faster algorithms for the residue multiplication modulo 521-bit Mersenne prime on 32- and 64-bit platforms by using Toeplitz matrix-vector product. The total arithmetic cost of our proposed algorithms is less than that of existing algorithms, with algorithms for 64- and 32-bit residue multiplication giving the best timing results on our test machine. The transition from 64- to 32-bit implementation is full of challenges because the number of limbs doubles and the limbs' bitlengths are cut in half...
Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication
Taskin, Halil Kemal; Cenk, Murat (2018-01-24)
This paper proposes a new multiplication algorithm over F-2(255)-19 where the de-facto standard Curve25519 [2] algorithm is based on. Our algorithm for the underlying finite field multiplication exploits the Toeplitz matrix-vector multiplication and achieves salient results. We have used a new radix representation that is infeasible when used with schoolbook multiplication techniques but has notable advantages when used with Toeplitz matrix-vector multiplication methods. We present the new algorithm and dis...
Faster residue multiplication modulo 521-bit mersenne prime and application to ECC
Ali, Shoukat; Cenk, Murat; Department of Cryptography (2017)
We present faster algorithms for the residue multiplication modulo 521-bit Mersenne prime on 32- and 64-bit platforms by using Toeplitz Matrix-Vector Product (TMVP). The total arithmetic cost of our proposed algorithms is less than the existing algorithms and we select the ones, 32- and 64-bit residue multiplication, with the best timing results on our testing machine(s). For the 64-bit residue multiplication we have presented three versions of our algorithm along with their arithmetic cost and from impleme...
Some new results on binary polynomial multiplication
Cenk, Murat (2015-11-01)
This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein's 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein's 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials ...
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...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
S. Ali and M. Cenk, “A New Algorithm for Residue Multiplication Modulo 2(521)-1,” 2016, vol. 10157, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32521.