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)

**Re: Incidence/frequency of numbers in lists**

**Re: DSOLVE in 5.01 ??**

**Plotting 3-trees in 6 vertices and evaluating their Prufer codes.**

**Re: Elliptic Curves and Cryptography Questions**