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

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

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

```

• Prev by Date: RE: undocumented function: StringQ
• Next by Date: Re: Re: Programming style
• Previous by thread: Elliptic Curves and Cryptography Questions
• Next by thread: Re: Elliptic Curves and Cryptography Questions