1

While working with Charm-Crypto package, I need to do lots and lots of group element exponentiation. The group elements come from bi-linear pairing group. The Order of the group element is a 1024 bit integer. So to reduce the average cost of exponentiation, I wanted to use memoization.

But I came to know that List does not support long indices (which I need very much). So I went for dictionary which is taking a lot of time & space.

Could you suggest some other methods/data structure in python to reduce the exponentiation cost. I am using iterative square-multiply technique to do the exponentiation.

Artjom B.
  • 61,146
  • 24
  • 125
  • 222
mxant
  • 17
  • 3
  • You can't store them, because there are *lots and lots of group element*s. Provided that the exponentiations are somewhat unique, I would think you would never get a performance increase from memoization, but for that we need to see your algorithm. Another thing is that Charm provides exponentiation. So did you actually implement your own? I removed the last part of your question, because it asks for an off-site resource or library which is off-topic for StackOverflow (SO). – Artjom B. Dec 06 '14 at 08:24
  • Thanks for reply. The scenario is I have <=5000 polynomials (as a list ie [a,b,c] stands for a+bx+cx^2) each of length in between [200, 10000]. I need to evaluate each (P_i) of them for some predefined value(x) ( ie P_i(x)) and compute exponentiation (ie g^(P_i(x))). The exponentiation available in the Charm package is really efficient. But as I need to compute so many exponentiations, I went for memoization with sqaue-multiply technique as same exponentiation is being done several times. For the last part of my original question, should I create a new question? – mxant Dec 06 '14 at 09:26
  • The dictionary is probably the most efficient way to store the exponentiation results (and input value). Have you tried to put the hashcode of the group element as a key instead of the actual group element? Although, that might result in errors when a collision happens. – Artjom B. Dec 06 '14 at 09:33
  • Ok.Now I got your idea. But as a key, I am keeping the exponent that is from Zp where p is 1024 bit integer ie long. Also hashing will incur some extra computation cost. :/ – mxant Dec 06 '14 at 10:07

0 Answers0