Jacobians of Hyperelliptic Curves over ℤn and Factorization of n

• Autorzy: Dryło Robert , Pomykała Jacek

Identyfikatory

DOI

10.3233/FI-2019-1847

• Języki publikacji: EN

Abstrakty

EN

E. Bach showed that factorization of an integer n can be reduced in probabilistic polynomial time to the problem of computing exponents of elements in ℤ_n* (in particular the group order of ℤ*_n). It is also known that factorization of square-free integer n can be reduced to the problem of computing the group order of an elliptic curve E/ℤ_n. In this paper we describe the analogous reduction for computing the orders of Jacobians over ℤ_n of hyperelliptic curves C over ℤ_n using the Mumford representation of divisor classes and Cantor’s algorithm for addition. These reductions are based on the group structure of the Jacobian. We also propose other reduction of factorization to the problem of determining the number of points |C(ℤ_n)|, which makes use of elementary properties of twists of hyperelliptic curves.

Słowa kluczowe

EN

factoring algorithm; abelian varieties; Jacobian; hyperelliptic curves

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 4
• Strony: 275--283
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Dryło Robert

• Warsaw School of Economics, Aleja Niepodległości 162, 02-554 Warsaw, Poland

autor

Pomykała Jacek

• Faculty of Mathematics Informatics and Mechanics, ul. Banacha 2, 02-097 Warsaw, Poland

Bibliografia

• [1] Adleman LM., McCurley KS. Open problems in number theoretic complexity II. In: Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, 291-322 (1994), Springer-Verlag. ISBN:3-540-58691-1.
• [2] Bach E. Discrete logarithms and factoring. Berkeley: Computer Science Division, University of California, 1984.
• [3] Cantor DG. Computing in the Jacobian of a hyperelliptic curve. Mathematics of computation 1987; 177(48):95-101.
• [4] Cohen H, and Frey G. Handbook of Elliptic and Hyperelliptic Curve Cryptography; written with Roberto M. Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen and Frederik Vercauteren. Discrete Mathematics and its Applications. Chapman & Hall/CRC, 2005. ISBN:9781584885184-CAT#C5181.
• [5] Demytko N. A new elliptic curve based analogue of RSA. In: Workshop on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1993. pp. 40-49. doi:10.1007/3-540-48285-7_4.
• [6] Dryło R, Pomykała J. Integer factoring problem and elliptic curves over the ring Zn (to appear in Colloquium Mathematicum).
• [7] Dryło R, and Pomykała J. Factoring n and the number of points of Kummer hypersurfaces mod n In: Number-Theoretic Methods in Cryptology, J. Kaczorowski, J. Pieprzyk, J. Pomykała (Eds.), LNCS 10737, Springer 2018, pp. 163-177. doi:10.1007/978-3-319-76620-1_10.
• [8] Durnoga K, and Pomykała J. Large sieve, Miller-Rabin compositness witnesses and integer factoring problem, Fundamenta Informaticae, 2017; 156(2):179-185. doi:10.3233/FI-2017-1603.
• [9] Koblitz N. Algebraic aspects of cryptography: with an appendix on hyperelliptic curves. Algorithms and Computation in Mathematics, Volume 3, Springer (1998). ISBN:3540634460 9783540634461.
• [10] Kunihiro N, and Koyama K. Equivalence of counting the number of points on elliptic curve over the ring Zn and factoring n. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 1998. pp. 47-58. doi:10.1007/BFb0054116.
• [11] Lenstra HW Jr. Elliptic curves and number-theoretic algorithms, in: Proceedings of the International Congress of Mathematicians, Berkeley, American Mathematical Society, Providence. 1986 pp. 99-120. URL https://www.math.leidenuniv.nl/ hwl/PUBLICATIONS/.../art.pdf.
• [12] Martin S, Morillo P, and Villar JL. Computing the order of points on an elliptic curve modulo N is as difficult as factoring N. Applied Mathematics Letters, 2001; 14(3):341-346. URL https://doi.org/10.1016/S0893-9659(00)00159-2.
• [13] Okamoto T, and Uchiyama S. Security of an identity-based cryptosystem and the related reductions. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 1998. pp. 546-560. doi:10.1007/BFb0054153.
• [14] Pomykała J. Small generating sets and DLPC problem, Fundamenta Informaticae, 2016; 145(2):143-150. doi:10.3233/FI-2016-1351.
• [15] Pomykała J, and Radziejewski M. Integer factoring and compositeness witnesses, Number-Theoretic Methods in Cryptology 2019, Paris, URL http://nutmic2019.imj-prg.fr/contributed.php.
• [16] Dąbrowski A, and Pomykała J. On a Linnik problem for elliptic curves, Proc. Amer. Math. Soc., vol 147, No 9, Sept. 2019, pp. 3759-3763. doi:10.1090/proc/14589.
• [17] Pomykała J, and Źrałek B. On reducing factorization to the discrete logarithm problem modulo a composite, Comput. Complex 2012; 21(3):421-429. doi:10.1007/s00037-012-0037-5.
• [18] Pila J. Frobenius maps of abelian varieties and finding roots of unity in finite fields. Mathematics of Computation, 1990; 55(192):745-763. doi:10.2307/2008445.
• [19] Rabin M. Digitalized Signatures and Public-Key Functions as Intractable as Factorization. MIT Laboratory for Computer Science, January 1979.
• [20] Źrałek B. A deterministic version of Pallard’s p — 1 algorithm, Math. of Comp. 2010; 79(269):513-533. URL https://www.jstor.org/stable/40590414.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).