[curves] Introduction to ECC

[Brad Klee]

After: https://moderncrypto.org/mail-archive/curves/2018/000982.html
And: https://moderncrypto.org/mail-archive/curves/2018/000981.html

Hi Dominik,

I am not wrong. In this disagreement, you seem confused about solutions of
diophantine equations. You suggest that a curve will have as many distinct
solutions over Z^2 as over (Z/pZ)^2 with prime p. This counters common
sense, which states that there are not arbitrarily many solutions to any
particular diophantine equation, i.e. over Z^2.

So what is actually happening?

Take the example curve: 0 = -36 + 400*x^2 - 2000*x^2 y + 400*y^2 depicted
over a finite field in the left panel of [1]. This is another form of the
Jacobi quartic, but we might consider it  a "new curve" because the
addition rule on the cubic involves a linear intersection geometry,
different from the quartic. More heresy, the x=0 solution occurs at y=2.
Starting with P =[2/5,7/10], we calculate sequences over Q and GF[23],

nP        : [2/5, 7/10], [-(7/60), -(11/45)], [-(110/527), 3367/9610],
[184223/336840, 125521/804005], [172557142/149756395, 546265447/84739210] .
. .
nP%23 : [5, 3], [11, 11], [9, 15], [17, 6], [4, 18], [20, 10], [21, 20],
[0,2], [2, 20], [3, 10], [19, 18], [6, 6], [14, 15], [12, 11], [18,3], [
infty,0 ] . . . Repeats . . .

This example shows what actually happens. The Q-sequence visits infinitely
many //fractions// of increasing complexity. Introducing a finite field
such as GF[23], we find the subgroup structure used in ECC. Please realize
that the map from Q^2 ---> (Z/pZ)^2 //is not// a modulus-type map!

The other issue is evaluation of nP using the quartic rule. Apply shear
transform P=[2/5,7/10] ---> P' = [2/5, 3/10]. Then calculate via EFD
formulas:

nP'          : [2/5, 3/10], [-(36/35), 1203/490], [-(110/527),
670563/2777290], [202104/921115, 80558112963/339381137290] . . .
nP' % 23 : [5, 21], [20, 1], [9, 8], [17, 15], [4, 1], [11, 4], [21,10], [
infty,0], [2, 10], [12, 4], [19, 1], [6, 15], [14, 8], [3, 1], [18, 21],
[0, 21] . . . Repeats . . .
nP % 23  : [5, 3], [20, 12], [9, 15], [17, 13], [4, 18], [11, 19], [21,
20], [infty, 0], [2, 20], [12, 19], [19, 18], [6, 13], [14, 15], [3,12],
[18, 3], [0, 21] . . . Repeats . . .

Now compare cosets C_16/C_2. They are the same between iterations. The two
C_8 subgroups are different:

G1: [11, 11], [17, 6], [20, 10], [0, 2], [3, 10], [6, 6], [12, 11], [Infty,
0]
G2: [20, 12], [17, 13], [11, 19], [infty, 0], [12, 19], [6, 13], [3, 12],
[0, 21]

Maybe G1 and G2 such as these could lead to an interesting pairing scheme
[2] ? More on this question and evaluation over C & C^2 soon.

Cheers,

Brad


[1] https://ptpb.pw/AfTT.png
[2] http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20180313/d6913dee/attachment.html>