Re: Elliptic Curves and Cryptography Questions

*To*: mathgroup at smc.vnet.net*Subject*: [mg47646] Re: Elliptic Curves and Cryptography Questions*From*: jlgpardo at yahoo.es (Jose Luis Gomez Pardo)*Date*: Tue, 20 Apr 2004 03:18:51 -0400 (EDT)*References*: <c5tepb$hv0$1@smc.vnet.net> <c603fc$ce8$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Paul Abbott <paul at physics.uwa.edu.au> wrote in message news:<c603fc$ce8$1 at smc.vnet.net>... > 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 This is certainly an elegant solution and probably the best choice in your situation. However, if you were to work with larger elliptic curves you'll find that Reduce is rather slow and I would prefer a more conceptual solution, more or less as follows. The strategy is to use SqrtMod (in the package NumberTheory`NumberTheoryFunctions`), which implements Shanks algorithm to compute square roots module a prime p. Since the quadratic residues modulo p are precisely the integers modulo p which have Legendre (or Jacobi) symbol equal to one and, since the Legendre symbol can be calculed very quickly by using the law of quadratic reciprocity, one can first select all the values of the cubic polynomial defining the cubic which are quadratic residues and then compute their square roots the y-coordinates of the corresponding points. Then you could do as follows: S = Select[Range[23] - 1, JacobiSymbol[#^3 + # + 4, 23] ≠ -1 &]; gives the list of the x-coordinates of the points on the curve. Then: <<NumberTheory`NumberTheoryFunctions` EC = Flatten[MapThread[Outer[List, #1, #2] &, { Partition[S, 1], SqrtModList[#^3 + # + 4, 23] & /@ S}], 2]; gives the list of "finite" points on the curve (to which the point at infinity should be added). I computed the list of points of the curve that has the same Weierstrass equation as this one but is defined over GF(100003), which has 100413 points. Using this method, the list was computed in just over 3 seconds in my computer, while the method based on Reduce took about 6 minutes. Of course, this curve is still way too small for cryptographic use (most definitely, you would not want to compute the list of points of a cryptographically useful curve ... :) Cheers, Jose Luis.