Elliptic Curves Modulo $p$

Definition, arithmetic, point enumeration, elliptic curve cryptography (discrete log problem; diffie-hellman).

• COMPUTATION:
  • Compute with elliptic curves modulo a prime $p$ . Here is an example to get you started.

    sage: E = EllipticCurve(FiniteField(43), [-36,0])
    sage: E
    Elliptic Curve defined by y^2  = x^3 + 7*x over Finite Field of size 43
    sage: P = E([-3,9])
    sage: P + P
    (17 : 1 : 1)
    

  • Graph some elliptic curves modulo $p$ :

    sage: E = EllipticCurve(FiniteField(13), [-36,0])
    sage: P = plot(E,rgbcolor=(0,0,1),pointsize=100)
    sage: P.show(dpi=200)
    

• THEORY:
  • Given $P$ and a positive integer $n$ , it is fairly straightforward to compute $nP = P + P + \cdots + P$ . Given $P$ and $Q$ where you know that $Q=nP$ for some $n$ (even though you don't know $n!$ ), invent a way to find $n$ (it doesn't have to be fast).