Abstract
For composite n, we prove that counting the number of points on elliptic curves over the ring Zn is randomly computationally equivalent to factoring n. That is, we prove that if we can count it, we can easily factor n. Furthermore, we also prove that if we can solve the elliptic curve discrete logarithm problem modulo n, we can easily factor n.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
E. Bach. Discrete logarithm and factoring. Technical Report UCB/CSD 84/186, Computer Science Division (EECS), University of California, Berkley, Calfornia, 1984.
L. Charlap, R. Coley and D. Robbins. Enumerate of rational points on elliptic curves over finite fields, preprint, 1991.
N. Demytko. A new elliptic curve based analogue of RSA. Proc. of EUROCRYPT'93, LNCS765: pp.40–49, 1994.
N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48: pp.203–209, 1987.
K. Koyama, U. Mauer, T. Okamoto and S. Vanstone. New public-key schemes based on elliptic curves over the ring Zn. Proc. of CRYPT0'91, LNCS576: pp.345–357, 1992.
K. Koyama. Fast RSA-type scheme based on singular curves y2 + axy ≡ x3 (mod n). Proc. of EUROCRYPT'95, LNCS921: pp.329–340, 1995.
H. Lenstra. Factoring integer with elliptic curves. Ann. of Math., 126: pp.649–673, 1987.
D. L. Long. Random equivalence of factorization and computation of orders. Technical Report 284, Princeton University, Department of Electrical Engineering and Computer Science, April 1981.
A. Menezes. Elliptic curve public key cryptosystems. Kluwer academic publishers, 1993.
G. L. Miller. Riemann's hypothesis and tests for primality. Journal of Computer and System Sciences, 13: pp.300–317, 1976.
V. S. Miller. Use of elliptic curves in cryptography. Proc. of CRYPTO'85, LNCS218: pp.417–426, 1986.
P. Riebenboim. The little book of big primes. Springer-Verlag, 1991.
R. Schoof. Elliptic curve over finite fields and the computation of square roots mod p. Mathematics of Computation, 44: pp.483–494, 1985.
J. Silverman. The Arithmetic of Elliptic Curves. Springer-Verlag, New York, 1986. GTM 106.
H. Woll. Reductions among number theoretical problems. Information and Computation, 72: pp.167–179, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kunihiro, N., Koyama, K. (1998). Equivalence of counting the number of points on elliptic curve over the ring Zn and factoring n . In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054116
Download citation
DOI: https://doi.org/10.1007/BFb0054116
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive