2

Which exponent(s) d will require this many?

Would greatly appreciate any advice as to how to go about solving this problem.

bullprog
  • 144
  • 2
  • 11
tang
  • 33
  • 1
  • 7
  • What are you ideas about a solution? – nbro Mar 17 '17 at 21:26
  • You could experiment to gain intuition. – John Coleman Mar 17 '17 at 21:30
  • @nbro From reading I have determined that the multiply-and-square algorithm performs log2(d) number of multiplications - which I am assuming is determined from the height or run time of its recursion tree? – tang Mar 17 '17 at 21:33
  • That sounds like big-O of the number of multiplications. Your question isn't the sort of question for which a big-O solution is appropriate. For one thing, it has a number-theoretic component. – John Coleman Mar 17 '17 at 21:37
  • @JohnColeman yes, which is why I am stuck. I don't understand how to get the ceiling value. – tang Mar 17 '17 at 21:39
  • Experiment. Write a program which keeps track. Run it for all 1-bit numbers, then all 2-bit, 3-bit, ... up to a given size. Do you see a pattern? If so, then prove it. – John Coleman Mar 17 '17 at 21:43
  • @JohnColeman now I'm on the same page, thanks – tang Mar 17 '17 at 21:49
  • It seems a good first start would be to write down the algorithm, and then a recurrence relation defining the number of multiplications. – Paul Hankin Mar 17 '17 at 21:50

2 Answers2

1

assuming unsigned integers and simple power by squaring algo like:

DWORD powuu(DWORD a,DWORD b)
    {   
    int i,bits=32;
    DWORD d=1;
    for (i=0;i<bits;i++)
        {
        d*=d;
        if (DWORD(b&0x80000000)) d*=a;
        b<<=1;
        }
    return d;
    }

You need just replace a*b with modmul(a,b,n) or (a*b)%n so the answer is:

  1. if exponent has k bits and l from them are set you need k+l multiplications
  2. worst case is 2k multiplications for exponent (2^k)-1

For more info see related QAs:

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
1

For a naive implementation, it's clearly the exponent with the largest Hamming weight (number of set bits). In this case (2^k - 1) would require the most multiplication steps: (k).

For k-ary window methods, the number of multiplications can be made independent of the exponent. e.g., for a fixed window size: w = 3 we could compute {m^0, m^1, m^2, m^3, .., m^7} group coefficients (all mod n in this case, and probably in Montgomery representation for efficient reduction). The result is ceil(k/w) multiplications. This is often preferred in cryptographic implementations, as the exponent is not revealed by simple timing attacks. Any k-bit exponent has the same timing. (The reality is a bit more complex if it is assumed the attacker has 'fine-grained' access to things like cache performance, etc.)

Sliding window techniques are typically more efficient, and only slightly more difficult to implement than fixed-window methods. however, they also leak side channel data, as timing will be dependent on the exponent. Furthermore, the 'best' sequence to use is known to be a hard problem.

Brett Hale
  • 21,653
  • 2
  • 61
  • 90