Group arithmetic in \(C_{3,5}\) curves. (English) Zbl 1332.94074
Summary: In this paper we present a fast addition algorithm in the Jacobian of a \(C_{3,5}\) curve over a finite field \(\mathbb F_q\). We give formulae for \(D_1 \oplus D_2 = -(D_1 + D_2)\) which require \(2I + 264M + 10S\) when \(D_1 \neq D_2\) and \(2I + 297M + 13S\) when \(D_1 = D_2\); and for the computation of \(-D\) which require \(2I + 41M + 3S\). The \(\oplus\) operation is sufficient to compute scalar multiplications after performing a single (initial) \(-D\). Computing the scalar multiplication \([k]D\), based on the previous fact combined with our algorithm for computing \(D_1 \oplus D_2\), is to date the fastest one performing this operation for \(C_{3,5}\) curves. These formulae can be easily combined to compute the full group addition and doubling in \(3I + 308M + 13S\) and \(3I + 341M + 16S\) respectively, which compares favorably with previously presented formulae.
MSC:
| 94A60 | Cryptography |
| 11G20 | Curves over finite and local fields |
| 68W30 | Symbolic computation and algebraic computation |
References:
| [1] | Abu Salem, F.; Khuri-Makdisi, K., Fast Jacobian group operations for \(C_{3, 4}\) curves over a large field, J. Comput. Math., 10, 307-328 (2007) · Zbl 1221.14062 |
| [2] | Adleman, L.; DeMarrais, J.; Huang, M.-D., A subexponential algorithm for discrete logarithms in the rational subgroup of the Jacobian of a hyperelliptic curve over a finite field, (Algorithmic Number Theory Symposium - 1994. Algorithmic Number Theory Symposium - 1994, Lecture Notes in Comput. Sci., vol. 877 (1994), Springer), 28-40 · Zbl 0829.11068 |
| [3] | Arita, S., An addition algorithm in Jacobian of \(C_{3, 4}\) curve, (Information Security and Privacy, ACISP 2003. Information Security and Privacy, ACISP 2003, Lecture Notes in Comput. Sci., vol. 2727 (2003), Springer), 93-105 · Zbl 1044.94524 |
| [4] | Arita, S., An addition algorithm in Jacobian of \(C_{a b}\) curves, Discrete Appl. Math., 130, 13-31 (2003) · Zbl 1037.14010 |
| [5] | Arita, S.; Miura, S.; Sekiguchi, T., An addition algorithm on the Jacobian varieties of curves, J. Ramanujan Math. Soc., 19, 4, 235-251 (2004) · Zbl 1071.14030 |
| [6] | Avanzi, R., Aspects of hyperelliptic curves over large prime fields in software implementations, (Cryptographic Hardware and Embedded Systems - CHES 2004. Cryptographic Hardware and Embedded Systems - CHES 2004, Lecture Notes in Comput. Sci., vol. 3156 (2004), Springer), 148-162 · Zbl 1104.68463 |
| [7] | Avanzi, R.; Frey, G.; Lange, T.; Oyono, R., On using expansions to the base of −2, Int. J. Comput. Math., 81, 4, 403-406 (2004) · Zbl 1060.94013 |
| [8] | Avanzi, R.; Thériault, N., Effects of optimizations for software implementations of small binary field arithmetic, (WAIFI 2007. WAIFI 2007, Lecture Notes in Comput. Sci., vol. 4547 (2007), Springer), 69-84 · Zbl 1213.94079 |
| [9] | Avanzi, R.; Thériault, N.; Wang, Z., Rethinking low genus hyperelliptic Jacobian arithmetic over binary fields: interplay of field arithmetic and explicit formulae, J. Math. Cryptol., 2, 3, 227-256 (2008) · Zbl 1146.14032 |
| [11] | Basiri, A.; Enge, A.; Faugère, J.-C.; Gürel, N., Implementing the arithmetic of \(C_{3, 4}\) curves, (Algorithmic Number Theory Symposium - ANTS-VI. Algorithmic Number Theory Symposium - ANTS-VI, Lecture Notes in Comput. Sci., vol. 3076 (2004), Springer), 87-101 · Zbl 1148.14304 |
| [12] | Basiri, A.; Enge, A.; Faugère, J.-C.; Gürel, N., The arithmetic of Jacobian groups of superelliptic cubics, Math. Comp., 74, 389-410 (2005) · Zbl 1094.14049 |
| [13] | Cantor, D., Computing in the Jacobian of a hyperelliptic curve, Math. Comp., 48, 177, 95-101 (1987) · Zbl 0613.14022 |
| [14] | Cosset, R., Factorization with genus 2 curves, Math. Comp., 79, 270, 1191-1202 (2010) · Zbl 1227.11123 |
| [15] | Diem, C., An index calculus algorithm for plane curves of small degree, (Algorithmic Number Theory. Algorithmic Number Theory, Lecture Notes in Comput. Sci., vol. 4076 (2006), Springer), 543-557 · Zbl 1143.11361 |
| [16] | Diem, C.; Thomé, E., Index calculus in class groups of non-hyperelliptic curves of genus three, J. Cryptology, 21, 4, 593-611 (2008) · Zbl 1167.11047 |
| [17] | Flon, S.; Oyono, R., Fast arithmetic on Jacobians of Picard curves, (Public Key Cryptography - PKC 2004 (2004)). (Public Key Cryptography - PKC 2004 (2004)), Lecture Notes in Comput. Sci., vol. 2947, 55-68 (2004), Springer: Springer Berlin · Zbl 1198.94093 |
| [18] | Flon, S.; Oyono, R.; Ritzenthaler, C., Fast addition on non-hyperelliptic genus 3 curves, (Algebraic Geometry and Its Applications. Algebraic Geometry and Its Applications, Ser. Number Theory Appl., vol. 5 (2008), World Sci. Publ.: World Sci. Publ. Hackensack, NJ), 1-28 · Zbl 1151.14313 |
| [19] | Galbraith, S.; Paulus, S.; Smart, N., Arithmetic on superelliptic curves, Math. Comp., 71, 237, 393-405 (2002) · Zbl 1013.11026 |
| [20] | Gaudry, P.; Thomé, E.; Thériault, N.; Diem, C., A double large prime variation for small genus hyperelliptic index calculus, Math. Comp., 76, 475-492 (2007) · Zbl 1179.94062 |
| [21] | Harasawa, R.; Suzuki, J., Fast Jacobian group arithmetic on \(C_{a b}\) curve, (Algorithmic Number Theory - ANTS-IV. Algorithmic Number Theory - ANTS-IV, Lecture Notes in Comput. Sci., vol. 1838 (2000), Springer), 359-376 · Zbl 1032.11025 |
| [22] | Koblitz, N., Elliptic curve cryptosystems, Math. Comp., 48, 177, 203-209 (1987) · Zbl 0622.94015 |
| [23] | Koblitz, N., Hyperelliptic cryptosystems, J. Cryptology, 1, 139-150 (1989) · Zbl 0674.94010 |
| [24] | Nagao, K., Improving group law algorithms for Jacobians of hyperelliptic curves, (Algorithmic Number Theory - ANTS-IV. Algorithmic Number Theory - ANTS-IV, Lecture Notes in Comput. Sci., vol. 1838 (2000), Springer), 439-448 · Zbl 1023.68132 |
| [25] | Smith, B., Isogenies and the discrete logarithm problem in Jacobians of genus 3 hyperelliptic curves, J. Cryptology, 22, 4, 505-529 (2009) · Zbl 1182.94047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
