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.