On the computation of generalized division polynomials

Date

2015-01-01

Author

Küçüksakallı, Ömer

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

242
views

0
downloads

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.

Subject Keywords

Complex multiplication, Division polynomial, Hurwitz number

URI

https://hdl.handle.net/11511/39887

Journal

TURKISH JOURNAL OF MATHEMATICS

DOI

https://doi.org/10.3906/mat-1410-29

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

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...
On the Polynomial Multiplication in Chebyshev Form Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2012-04-01) We give an efficient multiplication method for polynomials in Chebyshev form. This multiplication method is different from the previous ones. Theoretically, we show that the number of multiplications is at least as good as Karatsuba-based algorithm. Moreover, using the proposed method, we improve the number of additions slightly. We remark that our method works efficiently for any N and it is easy to implement. To the best of our knowledge, the proposed method has the best multiplication and addition comple...
Value sets of Lattes maps over finite fields Küçüksakallı, Ömer (Elsevier BV, 2014-10-01) We give an alternative computation of the value sets of Dickson polynomials over finite fields by using a singular cubic curve. Our method is not only simpler but also it can be generalized to the non-singular elliptic case. We determine the value sets of Lattes maps over finite fields which are rational functions induced by isogenies of elliptic curves with complex multiplication.
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...
HYBRID ANALYSIS OF TMVP FOR MODULAR POLYNOMIAL MULTIPLICATION IN CRYPTOGRAPHY Efe, Giray; Cenk, Murat; Department of Cryptography (2022-3-07) Polynomial multiplication on the quotient ring Z[x]/<x^n+-1> is one of the most fundamental, general-purpose operations frequently used in cryptographic algorithms. Therefore, a possible improvement over a multiplication algorithm directly affects the performance of algorithms used in a cryptographic application. Well-known multiplication algorithms such as Schoolbook, Karatsuba, and Toom-Cook are dominant choices against NTT in small and ordinary input sizes. On the other hand, how these approaches are imp...

Citation Formats

Ö. Küçüksakallı, “On the computation of generalized division polynomials,” TURKISH JOURNAL OF MATHEMATICS, pp. 547–555, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/39887.