Hi Brad, I will try to keep this short.
On 03/13/2018 09:07 PM, Brad Klee wrote: > 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. > > 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. > > 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). > > 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. 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. > > Cheers, > > Brad > > > [1] https://ptpb.pw/AfTT.png > [2] http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf > > _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves