Counting Points On Elliptic Curves

Counting Points On Elliptic Curves

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication (See elliptic curve cryptography and elliptic curve DSA). While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group, of elliptic curves over a finite field, where q = pk and p is a prime. The DLP, as it has come to be known, is a widely used approach to Public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p-adic methods exist.

Read more about Counting Points On Elliptic Curves:  Approaches To Counting Points On Elliptic Curves, Naive Approach, Baby-step Giant-step, Schoof's Algorithm, Schoof–Elkies–Atkin Algorithm, See Also, Bibliography

Famous quotes containing the words counting, points and/or curves:

    Is it not manifest that our academic institutions should have a wider scope; that they should not be timid and keep the ruts of the last generation, but that wise men thinking for themselves and heartily seeking the good of mankind, and counting the cost of innovation, should dare to arouse the young to a just and heroic life; that the moral nature should be addressed in the school-room, and children should be treated as the high-born candidates of truth and virtue?
    Ralph Waldo Emerson (1803–1882)

    PLAIN SUPERFICIALITY is the character of a speech, in which any two points being taken, the speaker is found to lie wholly with regard to those two points.
    Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    For a hundred and fifty years, in the pasture of dead horses,
    roots of pine trees pushed through the pale curves of your ribs,
    yellow blossoms flourished above you in autumn, and in winter
    frost heaved your bones in the ground—old toilers, soil makers:
    O Roger, Mackerel, Riley, Ned, Nellie, Chester, Lady Ghost.
    Donald Hall (b. 1928)