Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
    
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. – Maarten Bodewes Feb 10 at 9:02
    
@MaartenBodewes #ADD is supposed to be the number of additions. – CodesInChaos Feb 10 at 10:20
    
@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... – Maarten Bodewes Feb 10 at 10:23
    
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. – Maarten Bodewes Feb 10 at 10:26
    
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. – poncho Feb 10 at 14:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.