1
$\begingroup$

I am using double and add method for point multiplication in affine coordinates. How we compute 1PM in double and method?

Di Wang said one point multiplication consists of repeated addition and doubling operations, so the calculated time of point multiplication

#ADD*1ADD + #DBL*1DBL

more less equals 1PM. But when I calculate with the formula show different result:

#ADD*1ADD + #DBL*1DBL = 127#ADD*2ms + 256#DBL*3ms = 766ms

Actual 1PM = 421ms.

This is a huge difference. Can anyone explain this difference?

Double and add algorithm requires log2(n) iterations of point doubling and addition to compute the full-point multiplication.

So I think that: $2^y = n$ where $y$ is number point addition or doubling

Edited:

Double and Add Method d=11=(1011) Example : 11P= 2.((2.(2P))+P) + P, it consist of 3DBL + 2ADD. So 1PM less equal to #ADD*1ADD + #DBL*1DBL = 2ADDtimeof1ADD + 3DBLtimeof1ADD = time of 1PM.

If i have d lenghth = 256 bit, and i use Double-and-Method, How many #ADD and #DOUBLE iterations in there? DiWang said 127#ADD and 256#DOUBLE, can somebody explain how get this number?

$\endgroup$
  • $\begingroup$ I've formatted your question. Please do not use '#' for formulas but use Latex (or ask for help). I'm not sure about your equations to I've turned them into code fragments. Please edit your question again to clear things up. What do you mean with ADD*ADD? Please reread your question before hitting the post button. $\endgroup$ – Maarten Bodewes Feb 10 '16 at 9:02
  • $\begingroup$ @MaartenBodewes #ADD is supposed to be the number of additions. $\endgroup$ – CodesInChaos Feb 10 '16 at 10:20
  • $\begingroup$ @CodesInChaos ok, the original showed it as caption instead. Glad I at least edited that out. We can leave it as preformatted code then I suppose, unless somebody knows the correct Latex tags for this... $\endgroup$ – Maarten Bodewes Feb 10 '16 at 10:23
  • $\begingroup$ Alfred, if you post a time in ms then I suppose that is for a specific runtime. Could you post that runtime configuration ? Chances are that somebody here knows about the implementation specifics. $\endgroup$ – Maarten Bodewes Feb 10 '16 at 10:26
  • 1
    $\begingroup$ How certain are you on the timings of the double and add routines? If they are moderately faster than you think, that'd explain the performance difference. $\endgroup$ – poncho Feb 10 '16 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.