A Mathematica Package
 for Elliptic Curves

John McGee, Radford University

Initialization

Needs["EllipticCurves`"];

Join the Conversation #WolframTechConf

Background

Conic sections have been well understood since antiquity.
	
       Apollonius of Perga Conics
    
    Solutions to the quadratic equation were also known in the distant past
    	 a (x^2)+b x+c=0=> x=((-b ± (Sqrt[(b^2)-4 a c]))/(2 a))

We can even find all the rational points!

Shortly after Decarte married algebra with geometry the story of quadratics was completed:  
       a (x^2)+b x y+c (y^2)+e x+d y+e=0

    ({{Rational Parameterization of the Circle}, {(x,y)=(((1-(t^2))/(1+(t^2))),((2t)/(1+(t^2))))}})

Cubic curves are much more interesting

The general cubic equation generates a curve with much more complex structure

	a (x^3)+b (x^2)y+c x (y^2)+d (y^3)+f (x^3)+g x y+h (y^2)+r x+s y+t =0
	
	“Gerolamo Cardano published with attribution the solution of Scipione del Ferro
	 to the cubic equation and the solution of his student Lodovico Ferrari to the quartic
	 equation in his 1545 book Ars Magna. The solution to one particular case of the 
	 cubic equation a (x^3)+b x+c=0, had been communicated to him by Niccolò Fontana Tartaglia.”

Note that we cannot find the rational points with the strategy used for quadratics!

Clear[a,b,c,d];Solve[a (x^3)+b (x^2)+c x+d==0,x]//TableForm

Elliptic Curves

An elliptic curve is a non-singular cubic curve in two variables over a field E(𝔽)=𝒵(f)|f∈𝔽[x,y]
Under a suitable change of variables the general cubic equation can be transformed to:
	
		(y^2)=(x^3)+A x +B  (short Weierstrass form)

What Makes Elliptic Curves Interesting

Motivate a study of interesting mathematics:

	analytic geometry, algebra, number theory, complex variables,
	topology, algebraic geometry, algebraic topology, ...
	
Illuminate deep connections between these diverse branches of mathematics

Have wide-ranging use in both pure and applied mathematics

	Cryptography, Integer Factoring, proof of Fermat’s Last Theorem
	
Active area of current research (BSD conjecture, ...)

Cord and Tangent Point Addition

The sum of two points A,B on the curve E(K):(y^2)=(x^3)+a x+b, is the third point of intersection of the line containing A,B, reflected about the axis of symmetry, the tangent line when A=B

Projective Space, Homogeneous Polynomials, the group identity 𝒪

To complete the group structure, we consider the curve in homogeneous coordinates with solution points in (ℙ^2)
	
		(y^2)z=(x^3)+a x (z^2)+b (z^3)
		
In (ℙ^2) the solutions [x:y:1] correspond to the real solution points (x,y)∈(ℝ^2), whereas the solution 𝒪=[0:1:0], called the point at infinity acts as the identity in the group.  With these definitions we add the following special cases to the geometric definition above.  For all P∈E(ℝ) P⊕𝒪=P=𝒪⊕P.  If Q=-P, that is, if P=(x,y) and Q=(x,-y) then P⊕Q=𝒪.  In this way E(ℝ)⋃{𝒪} is an abelian group under ⊕.  The proof of associativity is non-trivial.

The Algebraic Group Law

On the elliptic curve:  (y^2)=(x^3)+a x+b  given  P=((Subscript[x, 1]),(Subscript[y, 1])),Q=((Subscript[x, 2]),(Subscript[y, 2]))

	then P⊕Q=((Subscript[x, 3]),(Subscript[y, 3])) where
 
	λ=((Subscript[y, 2])-(Subscript[y, 1]))/((Subscript[x, 2])-(Subscript[x, 1]))      or     λ=(3 ((Subscript[x, 1])^2)+a (Subscript[x, 1]))/ (2 (Subscript[y, 1]))
	
	(Subscript[x, 3])=(λ^2)-(Subscript[x, 1])-(Subscript[x, 2])	           (Subscript[y, 3])=λ ((Subscript[x, 1])-(Subscript[x, 3]))+(Subscript[y, 1])
	
Surprisingly, with this operation, the set of points on the curve form an abelian group.

	Closed, Identity, Inverses, Associativity

The identity in this group is the point at infinity 𝒪, corresponding to the vertical direction in projective space [0:1:0]

The Purpose of this Package

Provide a set of Mathematica functions to support (over ℚ,ℝ,ℂ,(Subscript[𝔽, p]),(Subscript[𝔽, (p^n)])):

	* Elliptic Curve Point Addition:  A⊕B
	
	* Elliptic Curve Integer Multiplication:  k⊗A
	
	* Determination of Point Order:   |A| =min n ∈(SuperPlus[ℤ])∍n A=𝒪
	
	* Solution of the Discrete Logarithm Problem:  given P,Q=k P, determine k
	
	* Cryptographic and number theory applications

Mathematica’s ability to do field arithmetic, modular polynomial arithmetic and algebra
	makes it well-suited for computational research in this area.

The Design

Data Types
	ecCurve[a,b,f]    	represents the curve (y^2)=(x^2)+a x+b over f
	
	ecPnt[(Subscript[x, 0]),(Subscript[y, 0])]           	represents the point with coordinates ((Subscript[x, 0]),(Subscript[y, 0]))
	
Functions
	setEC[ec_ecCurve]	establishes the currently active curve
	
	⊕, ⊗, ecPointOrder	work over any supported field
	
				private field-specific functions are called where necessary				Design Choice

	used code based on Mod, PowerMod for (Subscript[𝔽, p]),  FiniteFields` only for (Subscript[𝔽, (p^n)])

Point Arithmetic Examples over (Subscript[𝔽, p])

Define the curve (y^2)≡(x^3)+269 x+119 over (Subscript[𝔽, 709]) and verify that it is non-singular

ec1=ecCurve[269,119,{709,1}];setEC[ec1];isECQ[ec1]

Define two points and verify that they lie on the curve

pntA=ecPnt[2,92];pntB=ecPnt[38,116];isECPointQ/@{pntA,pntB}

Determine the order of the points

ecPointOrder/@{pntA,pntB}

29⊗pntB

Generate a linear combination of the two points

(5⊗pntA)⊕(3⊗pntB)

Determine the j-Invariant of the curve.

jInvariant[ec1]

Determine the Group Order

ecHasseBounds[]

ecGroupOrder[]

Bachet’s Duplication Formula (over ℚ)

Define the curve (y^2)-(x^3)=-2  (the difference between a square and a cube is a rational)

ec2=ecCurve[0,-2,ℚ];setEC[ec2];

Define a rational point on this curve

pntA=ecPnt[3,5];

The first three doublings of the rational point.
Note the sum of rational points a rational point, as is the double

NestList[2⊗#&,pntA,3]//TableForm

Use point doubling to derive a form of Bachet’s duplication formula (1621) for c=-2

Together/@(2⊗ecPnt[x,y])

Cryptography Example (the ElGamal method)

ElGamal Encode and Decode using elliptic curve operators

ElGamalEncode[m_Integer,{pntP_ecPnt,pntB_ecPnt}]:=Module[{k,pntM},
pntM=findECPoint[m*100];
k=RandomInteger[{Floor[n/4],n-1}];
Return[{k⊗pntP,pntM⊕(k⊗pntB)}];]

ElGamalDecode[s_Integer,{pntM1_ecPnt,pntM2_ecPnt}]:=Module[{pntM,pntS,m},
pntS=-s⊗pntM1;
pntM=pntM2⊕pntS;
m=Quotient[First[pntM],100];
Return[m];
]

Define the curve and the order of the group

p=Prime[10001];ec3=ecCurve[78656,63203,{p,1}];setEC[ec3];n=ecGroupOrder[]

Generate the public key (P,B=s⊗P)

s=RandomInteger[{Floor[n/4],n-1}];pntP=randomECPoint[n];pntB=s⊗pntP;{s,pntP,pntB}

Read in a hidden message and convert it to character codes

plntxt=Import["SecretMsg.txt"];plncds=ToCharacterCode@plntxt;

Alice performs ElGamal encryption using the public key to convert the character codes
  to sets of point pairs (Subscript[M, 1]),(Subscript[M, 2]).  Transmit these point pairs to Bob.

cphcds=ElGamalEncode[#,{pntP,pntB}]&/@plncds;Take[cphcds,6]\[Transpose]

Eve tries to work here using only the public key and the point pairs
She needs to solve the elliptic curve DLP to determine the private key s
	⋮
Bob receives the point pairs.

Decode the point pairs using the private key, returning a set of character codes

dcdcds=ElGamalDecode[s,#]&/@cphcds;Take[dcdcds,25]

Reveal the decoded message

FromCharacterCode@dcdcds

Future Work

I have version 1.0 here at the conference.  Future plans include:

	* Richer support for elliptic curves over ℂ using ℘(z),℘'(z)
	
	* Computation of the Weil Pairing (P,Q)↦(e^(i  2k π/n))
	
	* Implementation of the Schoof-Elkies-Atkins algorithm for |E((Subscript[𝔽, q]))|

References

[1] L. Washington Elliptic Curves, Chapmann & Hall 2003

[2] J. Silverman, J. Tate Rational Points on Elliptic Curves, Springer 1992

Thanks!

I would be happy to try to answer any questions you have.