On Aug 15, 2007, at 2:37 AM, Michel wrote:
> I think repeated squaring is not more efficient in all cases. For > example over Z it is only > more efficient if your multiplication algorithm is faster than the > naive one (which is O(n^2) in the number of bits). > > So in the case of elliptic curves it really depends on the efficiency > of the addition steps and on how fast > the numerators/denominators grow. I am sure the elliptic curve experts > on this forum can say more about this. Ah yes I had hadn't thought through that. SAGE uses GMP for the multiplications, which is quasi-linear time; on the other hand, the integer GCD code in GMP is still quadratic (as of GMP 4.2.1), so in effect what you're saying is still relevant since it is really doing arithmetic over Q. If you take a non-torsion point P on E(Q), then the bitsize of the numerators/denominators of kP grow like k^2. So bitsize of 2^m P is about 4^m. Say we compute 2^m P by repeated doubling. If the arithmetic is quadratic time then computing 2^m P costs about 1 + 4^2 + 16^2 + ... + (4^m)^2 which is about 4^(2m) = 16^m. If the arithmetic is linear time (including the GCDs) then computing 2^m P costs about 1 + 4 + 16 + ... + 4^m which is about 4^m (ignoring log factors). Now say we compute 2^m P as (P + (P + (P + ( ... (P + P))...))). Well I'm not sure exactly what happens here, it's a bit more complicated since at each stage you're adding something "small" to something "big". I guess to keep it simple we can pretend the small thing is a constant, since we're assuming P is fixed. In the linear-time arithmetic case, at step N you have to do at least N^2 work, so it's 1 + 2^2 + 3^2 + ... + (2^m)^2 = about 8^m, so definitely loses to repeated doubling. In the quadratic time arithmetic case, it's more complicated. I'm looking at the formula for elliptic curve addition, and it looks like to compute P+Q you have to multiply coordinates of Q by coordinates of Q. Maybe there's a way of rewriting it, I don't know. If this is true, it means step N needs at least N^4 work, so it's 1 + 2^4 + 3^4 + ... + (2^m)^4 = about 32^m, so this still loses out to repeated doubling. If on the other hand, you can get away with multiplying coordinates of Q by coordinates of P (which is assumed to be constant), then it's still 8^m, so it beats repeated doubling. So if my analysis is wrong, we need an elliptic curve expert; and if it's right, we need an elliptic curve expert! (and in all cases it would be great if someone could address this ticket: http://www.sagemath.org:9002/sage_trac/ticket/424) david --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
