Abstract
We give a deterministic polynomial-time algorithm that computes a nontrivial rational point on an elliptic curve over a finite field, given a Weierstrass equation for the curve. For this, we reduce the problem to the task of finding a rational point on a curve of genus zero.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bach, E., Shallit, J.: Algorithmic Number Theory. The MIT Press, Cambridge (1996)
Berlekamp, E.R.: Algebraic coding theory. McGraw-Hill Book Co., New York (1968)
Bourbaki, N.: Algebra II. In: Elements of Mathematics, ch. 4–7, pp. 4–7. Springer, Berlin (2003); Translated from the 1981 French edition by P. M. Cohn and J. Howie, Reprint of the 1990 English edition
Bumby, R.T.: Sums of four squares. In: Number theory (New York, 1991–1995), pp. 1–8. Springer, New York (1996)
Cohen, H.: A course in computational algebraic number theory. Graduate Texts in Mathematics, vol. 138. Springer, Berlin (1993)
Reid, M.: Undergraduate algebraic geometry. London Mathematical Society Student Texts, vol. 12. Cambridge University Press, Cambridge (1988)
Schicho, J.: Proper parametrization of surfaces with a rational pencil. In: Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (St. Andrews), pp. 292–300. ACM Press, New York (2000)
Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44(170), 483–494 (1985)
Shafarevich, I.R.: Basic algebraic geometry, 2nd edn., vol. 1. Springer, Berlin (1994); Varieties in projective space, Translated from the 1988 Russian edition and with notes by Miles Reid
Silverman, J.H.: The arithmetic of elliptic curves. Graduate Texts in Mathematics, vol. 106. Springer, New York (1992); Corrected reprint of the 1986 original
Skałba, M.: Points on elliptic curves over finite fields. Acta Arith. 117(3), 293–301 (2005)
van de Woestijne, C.: Deterministic equation solving over finite fields. PhD thesis, Universiteit Leiden (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shallue, A., van de Woestijne, C.E. (2006). Construction of Rational Points on Elliptic Curves over Finite Fields. In: Hess, F., Pauli, S., Pohst, M. (eds) Algorithmic Number Theory. ANTS 2006. Lecture Notes in Computer Science, vol 4076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11792086_36
Download citation
DOI: https://doi.org/10.1007/11792086_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36075-9
Online ISBN: 978-3-540-36076-6
eBook Packages: Computer ScienceComputer Science (R0)