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)