Elliptic Curves and Cryptography Questions

• To: mathgroup at smc.vnet.net
• Subject: [mg47624] Elliptic Curves and Cryptography Questions
• From: "flip" <flip_alpha at safebunch.com>
• Date: Sun, 18 Apr 2004 04:15:27 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

Hello (sorry for the long question),

I am working on a presentation with Elliptic Curves/Cryptography and had a
few questions I was hoping someone could answer.  I use Mathematica version 4.0
(wish I could afford 5.0).

The elliptic curve I am using is E: y^2 == x^3 + x + 4 mod 23 (defined over
F{23}, that is p = 23).

Questions:

1.  There are 29 solution set points ((x, y) pairs plus the point at
infinity) to this elliptic curve.

{{0,2},
{0,21},{1,11},{1,12},{4,7},{4,16},{7,3},{7,20},{8,8},{8,15},{9,11},{9,12},{1
0,5},{10,18},{11,9},{11,14},{13,11},{13,12},{14,5},{14,18},{15,6},{15,17},{1
7,9},{17,14},{18,9},{18,14},{22,5},{22,19}}

Manually, one can check the quadratic residues and then determine if y^2 is
in that set (a cumbersome approach).

Is there a command in Mathematica to find this solution set?

2.  These points are typically labeled P and one does point addition for
P1+P2, etc, until you reach the point order.

There are basically three operations one needs to do on E: check for a point
at infinity, point addition and point doubling.

a.  If P = (x, y) E F{p}, then (x,y)+(x,-y) = O (that is, P = -P and that is
the point at infinity).  So we would just check for this condition on the
current set of points we wanted to add.

b.  Point Addition:  Let P = (x1, y1) and Q = (x2, y2) (obviously both are
elements of F{23}), where P != +/- Q.

Then P +Q = (x3, y3), where

x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2
y3 = ((y2-y1)/(x2-x1))(x1 - x3) - y1

c.  Pont Doubling: Let P = (x1, y1), where P != -P (that is x, -y).

Then 2P = (x3, y3), where

x3 = ((3 x1^2 + a)/(2 y1))^2 -2 x1
y3 = ((3 x1^2 + a)/(2 y1))(x1-x3) - y1

Is there an easy way to code this in Mathematica  so I can just pass the curve E, the
prime p, and the two points to add?  The module will determine if I have
reached a. (the point at infinity), if this is b (just adding P+ Q) or c
(point doubling to get 2P).

3.  When I do ListPlot[a], I get the scatter plot that I want, but is there
a way to show the grid, the points (x,y pairs) and to make the points a
little larger?

4.  When I do,

<< Graphics`ImplicitPlot`

ImplicitPlot[y^2 == x^3+x+4, {x, -2,2}]

I am wondering if there is a way to show the elliptic curve E and to
superimpose the points above and their values so the points are visible and
the plot is useable in a powerpoint slide?

Thank you, Flip

My email is alpha_flip at nethere.com_alpha (remove the _alpha's)

• Prev by Date: Re: Incidence/frequency of numbers in lists
• Next by Date: Re: DSOLVE in 5.01 ??
• Previous by thread: Plotting 3-trees in 6 vertices and evaluating their Prufer codes.
• Next by thread: Re: Elliptic Curves and Cryptography Questions