[Cryptography] Introduction to EC that is actually an introduction?

Viktor Dukhovni cryptography at dukhovni.org
Wed Jan 28 21:56:20 EST 2015

```On Wed, Jan 28, 2015 at 05:42:03PM -0500, Phillip Hallam-Baker wrote:

> Might be interesting seeing the graphical effect of the modular arithmetic
> on the elliptic curve.

Pick a nice curve modulo a modestly sized prime, like

y^2 = x^3 + x + 20 (mod 41)

Then a base point g=(3,3) generates the following cyclic group of
(prime) order 53 (xn and yn are the coordinates of g^n or n*g if
you prefer):

n   xn yn
--   -- --
0   infty
1    3  3
2   34 30
3   24 25
4   23 19
5   14 21
6   26 19
7   30 21
8   13  4
9    0 26
10   33 22
11    9 26
12   38 20
13   16 27
14    6 23
15   40 10
16   19 25
17   10 13
18   20  2
19   39 16
20   32 15
21    7  1
22   21  6
23   25  7
24   11  3
25   27 38
26   29 24
27   29 17
28   27  3
29   11 38
30   25 34
31   21 35
32    7 40
33   32 26
34   39 25
35   20 39
36   10 28
37   19 16
38   40 31
39    6 18
40   16 14
41   38 21
42    9 15
43   33 19
44    0 15
45   13 37
46   30 20
47   26 22
48   14 20
49   23 22
50   24 16
51   34 11
52    3 38

Any of the 52 non-identity points is as good a generator (base-point)
as any other.  Just multiply all the logs by the reciprocal of the
new base-point's logarithm taken mod 53.  For example 15*46 is 1
mod 53, so if G is changed to (40,10) all the logarithms are
multiplied by 46 mod 53 (shuffling the table).  The sequence of x
values with non-zero logs is a palindrome, with the y value changing
sign as expected.

Each x-value appears twice, if we take only the first
half of the list, and sort by x we get:

log x    x  y
-----   -- --
9    0 26
1    3  3
14    6 23
21    7  1
11    9 26
17   10 13
24   11  3
8   13  4
5   14 21
13   16 27
16   19 25
18   20  2
22   21  6
4   23 19
3   24 25
23   25  7
6   26 19
25   27 38
26   29 24
7   30 21
20   32 15
10   33 22
2   34 30
12   38 20
19   39 16
15   40 10

Which shows a rather non-uniform mapping from x to log x.

--
Viktor.
```