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

[Viktor Dukhovni]

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.