<p>The Shamir's algorithm is depicted as follows (cited from
<br>
<a href="http://cacr.uwaterloo.ca/hac/" rel="nofollow noreferrer">Handbook of Applied Cryptography</a>, chapter 14, algorithm 14.88, page 618)</p>

<h2>Shamir's algorithm</h2>

<p><strong>INPUT</strong>: group elements $g_0,g_1,\dots, g_{k-1}$ and non-negative $t$-bit integers $e_0,e_1,\dots, e_{k-1}$.</p>

<p><strong>OUTPUT</strong>:$g_0^{e_0}g_1^{e_1}\dots g_{k-1}^{e_{k-1}}$</p>

<ol>
<li><em>Precomputation</em>. For $i$ from 0 to $2^k-1$: $G_i \gets \Pi_{j=0}^{k-1}g_j^{i_j}$ where $i=(i_{k-1}\dots i_0)_2$.</li>
<li>$A\gets1$</li>
<li>For $i$ from 1 to $t$ do : $A \gets A$, $A \gets A \cdot G_{I_i}$</li>
<li>Return($A$)</li>
</ol>

<p>I wonder; how many exponentiations can the Shamir algorithm reduce? That's to say, usually it needs $k$ exponentiations to compute $g_0^{e_0}g_1^{e_1}\dots g_{k-1}^{e_{k-1}}$; however if we use the algorithm in the above, then how many exponentiations does it amount to when calculating $g_0^{e_0}g_1^{e_1}\dots g_{k-1}^{e_{k-1}}$?</p>

<p>P.S. Actually, this question appears in <a href="https://crypto.stackexchange.com/questions/17758/how-many-exponentiations-can-the-shamir-algorithm-reduce">here</a>. I think it's more proper to ask in this section. However, as I'm a newer I cannot flag or delete this same question from <a href="https://crypto.stackexchange.com/">https://crypto.stackexchange.com/</a>.  I'm sorry to do this..</p>

CC BY-SA 3.0
2014-06-23T23:36:41.733Z
Cross-posted on Crypto.SE: http://crypto.stackexchange.com/q/17758/351.  Please don't cross-post on multiple SE sites; that is [prohibited by site rules](http://meta.stackexchange.com/q/64068/160917).  If you need to move a question to a different site, you can click "flag" underneath the question to flag it for moderator attention and ask them to migrate it -- but don't cross-post or re-post the same thing on multiple SE sites.  Thank you!
D.W.
CC BY-SA 3.0
2014-06-24T04:21:35.047Z
I tried to flag this question, but it doesn't work, I don't know why
T.B
CC BY-SA 3.0
2014-06-25T02:06:13.210Z
What is $I_i$ in step 3 of the algorithm? Also, it seems like the "A<-A" step in 3 would not affect the output...
Abel Molina
CC BY-SA 3.0
2014-06-25T04:21:34.917Z
@Abel Molina: you can refer the link that I give for details
T.B
<cc.complexity-theory><ds.algorithms>
How many exponentiations can the Shamir algorithm reduce?
T.B
# How many exponentiations can the Shamir algorithm reduce?

(Asked by: username_0 on 2014-06-23)

The Shamir's algorithm is depicted as follows (cited from
  
[Handbook of Applied Cryptography](http://cacr.uwaterloo.ca/hac/), chapter 14, algorithm 14.88, page 618)

## Shamir's algorithm

**INPUT**: group elements $g\_0,g\_1,\dots, g\_{k-1}$ and non-negative $t$-bit integers $e\_0,e\_1,\dots, e\_{k-1}$.

**OUTPUT**:$g\_0^{e\_0}g\_1^{e\_1}\dots g\_{k-1}^{e\_{k-1}}$

1. *Precomputation*. For $i$ from 0 to $2^k-1$: $G\_i \gets \Pi\_{j=0}^{k-1}g\_j^{i\_j}$ where $i=(i\_{k-1}\dots i\_0)\_2$.
2. $A\gets1$
3. For $i$ from 1 to $t$ do : $A \gets A$, $A \gets A \cdot G\_{I\_i}$
4. Return($A$)

I wonder; how many exponentiations can the Shamir algorithm reduce? That's to say, usually it needs $k$ exponentiations to compute $g\_0^{e\_0}g\_1^{e\_1}\dots g\_{k-1}^{e\_{k-1}}$; however if we use the algorithm in the above, then how many exponentiations does it amount to when calculating $g\_0^{e\_0}g\_1^{e\_1}\dots g\_{k-1}^{e\_{k-1}}$?

P.S. Actually, this question appears in [here](https://crypto.stackexchange.com/questions/17758/how-many-exponentiations-can-the-shamir-algorithm-reduce). I think it's more proper to ask in this section. However, as I'm a newer I cannot flag or delete this same question from <https://crypto.stackexchange.com/>. I'm sorry to do this..

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: Cross-posted on Crypto.SE: http://crypto.stackexchange.com/q/17758/351.  Please don't cross-post on multiple SE sites; that is [prohibited by site rules](http://meta.stackexchange.com/q/64068/160917).  If you need to move a question to a different site, you can click "flag" underneath the question to flag it for moderator attention and ask them to migrate it -- but don't cross-post or re-post the same thing on multiple SE sites.  Thank you!  
> **username_0**: I tried to flag this question, but it doesn't work, I don't know why  
> **username_2**: What is $I_i$ in step 3 of the algorithm? Also, it seems like the "A<-A" step in 3 would not affect the output...  
> **username_0**: @username_2: you can refer the link that I give for details  

---

## 0 answers

