Re: Elliptic Curves and Cryptography Questions

*To*: mathgroup at smc.vnet.net*Subject*: [mg47635] Re: Elliptic Curves and Cryptography Questions*From*: Paul Abbott <paul at physics.uwa.edu.au>*Date*: Mon, 19 Apr 2004 04:33:05 -0400 (EDT)*Organization*: The University of Western Australia*References*: <c5tepb$hv0$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <c5tepb$hv0$1 at smc.vnet.net>, "flip" <flip_alpha at safebunch.com> wrote: > 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? The last point in your solution set is not correct. Here is the correct answer: Reduce[y^2 == x^3 + x + 4, {x, y}, Modulus -> 23] pts = {x, y} /. {ToRules[%]} {{0, 2}, {0, 21}, {1, 11}, {1, 12}, {4, 7}, {4, 16}, {7, 3}, {7, 20}, {8, 8}, {8, 15}, {9, 11}, {9, 12}, {10, 5}, {10, 18}, {11, 9}, {11, 14}, {13, 11}, {13, 12}, {14, 5}, {14, 18}, {15, 6}, {15, 17}, {17, 9}, {17, 14}, {18, 9}, {18, 14}, {22, 5}, {22, 18}} Checking the solution is straighfoward: f = Function[{x, y}, Mod[y^2 - (x^3 + x + 4), 23] == 0]; f @@@ pts // Union > ... text omitted ... > > 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 Actually, because you want to show a family of curves, ContourPlot is probably better: ContourPlot[y^2 - ( x^3 + x + 4), {x, 0, 12}, {y, 0, 23}, Contours -> 23 Range[-60, 20], ContourShading -> None, Epilog -> {Hue[1], AbsolutePointSize[5], Point /@ pts}]; > and the plot is useable in a powerpoint slide? Others will tell you how to do this, and it has appeared in this group previously: do a google search on powerpoint at http://groups.google.com/groups?hl=en&lr=&group=comp.soft-sys.math.mathem atica Personally, I prefer to use the Mathematica SlideShow mechanism, especially if you have a number of Mathematica graphics and equations. You can obtain the SlideShow tools for free for Mathematica 4.2 from the Wolfram website. Cheers, Paul -- Paul Abbott Phone: +61 8 9380 2734 School of Physics, M013 Fax: +61 8 9380 1014 The University of Western Australia (CRICOS Provider No 00126G) 35 Stirling Highway Crawley WA 6009 mailto:paul at physics.uwa.edu.au AUSTRALIA http://physics.uwa.edu.au/~paul