Hi Brad,

I will try to keep this short.

*Post by 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.

No, I am stating that all solutions over R^2 mapped as repetitions with

coordinate translation x'=x+mp, y=y+np for all m,n\in Z contain all

curve solutions over (Z/pZ)^2. That means, that "infinitely wrapping a

smooth curve over a torus" is the right projection if we want to depict

the repetitive nature of GF(p) in two dimensions (circle would work in

one dimension) for any given curve f(x,y)=0.

*Post by Brad Klee*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],

Assuming f(x,y)= -36 + 400*x^2 - 2000*x^2 y + 400*y^2 we see that there

are smooth curves drawn in the form of f(x+mp,y+np)=0 for some chosen

values of m and n. And of course, the values are chosen in a way that

shows only parts of infinitely-wrapped smooth curve (or a distinct

number of "new curves" with aforementioned coordinate translation) that

actually hit some interesting points in the (Z/pZ)^2 domain. That is

fine - of course you cannot work with the rest of the points I always

draw and I am talking about. They are there just to help the reader

think about the very nature of the underlying field.

*Post by Brad Klee*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!

Ok, I am not going into big detail here, but let me show you, that it

may be a modulus-type map after all.

\frac{2}{5}\equiv 2\frac{1}{5}\mod 23

So we find a multiplicative inverse of 5 over GF(23), which is 14 as

14\cdot 5\equiv 1\mod 23

Therefore \frac{2}{5}\equiv 2\cdot 14\mod 23, which gives us

\frac{2}{5}\equiv 28\mod 23 which yields (unsurprisingly) 5.

The same applies for 7/10 which translates to 3 using the same modular

arithmetic.

We surely confirm that both f(5,3)\equiv 0\mod 23 as it is -136436\mod

23=0, what about the rational notation then? It actually is the case

that f(2/5,7/10)=0 so both solutions are apparently valid over GF(23).

Now let's find f(5+23m,3+23n) to prove that my hypothesis might be

right. If we are unable to find m,n\in Z, I am wrong, if we can find it,

I might be right after all.

And for example f(5+23,3)\equiv 0\mod 23 (looks like infinitely many

repetitions hit this point actually).

I think I understand your point, but that does not invalidate my

hypothesis (which I think can be really easily proven, because if there

exist particular solutions in m and n, those solutions are present in

the set of all m,n\in Z). So again, the curve depicted in the left panel

of [1] can be drawn over a area of R^2 which covers the (Z/pZ)^2 domain

and if we select only those points that fall into (Z/pZ)^2 from the

infinite wrapping around this part of R^2, they do indeed contain all

solutions of such curve over given (Z/pZ)^2 - that is GF(23) in our case.

Please mind that I am primarily talking about finding rational points

over GF(p) now. You are slightly mixing it with the group addition law

used with given curve. Those are not the same things, although you may

typically use the group addition law to generate the rational points

over GF(p) - but sometimes not all. Take Ed25519 for example. You have

to chose generators from all subgroups in order to generate all points

of Ed25519 this way. This is why you need to zero out specified bits

when you are using Ed25519 as a building block of some cryptosystem

(typically for signatures here). If you fall into a small subgroup, you

are screwed in case of signatures. In case of finding all rational

points, you just do not find them all.

I didn't study the addition law used with the curve you posted (but I

have put it on my TODO list) - but if you are saying that it involves

linear intersections, I can also state that such linear intersection

rule would also work by wrapping the line infinitely around the torus

and it would eventually hit the given rational point which maps to the

same rational point over Q you mention above. This is no coincidence,

but again it is a feature of the underlying field. I hope I can show

this in the next video (it is getting tricky). And to add more

confusion, for every line over R^2 (or Q^2 thereof) you can draw two

different lines on the torus having the same properties when it comes to

explaining the group law. It is not in my writing plan (yet), but it can

be really easily shown in Weierstrass simple form (and that is another

reason I started with creating visualizations using the Weierstrass

simple form - it really helps you develop the necessary tools).

*Post by Brad Klee*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

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

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.

Now we are talking about something completely different. The generated

subgroups are an interesting feature of given curve and it is nice that

it can be shown on GF(p) with reasonably small p. About the pairing -

well ... I would love to read about that if you find anything

interesting there. Right now I am knee-deep in Ed25519 and Curve25519

embedded implementations and making nice pictures and videos makes me

breath easier :)

And I am really curious about your work over C^2 here. Just writing

about that makes me want to get back to academia :)

Cheers and keep up the good work!

Dominik

P.S.: It wasn't short after all ... my apologies for that.

*Post by Brad Klee* Cheers,

Brad

[1] https://ptpb.pw/AfTT.png

[2] http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf