A new method for decomposition in the Jacobian of small genus hyperelliptic curves

详细信息    查看全文

• 作者：Palash Sarkar ; Shashank Singh
• 关键词：Discrete logarithm ; Index calculus algorithms ; Hyperelliptic curves ; Cryptography
• 刊名：Designs, Codes and Cryptography
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：82
• 期：3
• 页码：601-616
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Coding and Information Theory; Data Structures, Cryptology and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Information and Communication, Circuits;
• 出版者：Springer US
• ISSN：1573-7586
• 卷排序：82

文摘

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of polynomials required in Gaudry’s method. Also, the total number of additions in the Jacobian required by the new method is less than that required by Gaudry’s method. The new method itself is quite simple and we present some example decompositions and timing results of our implementation of the method using Magma.