0

In most texts, the BSGS Algorithm solves $$g^x = b \bmod p$$ for x by rewriting the expression to $$g^{jm+i} = b \bmod p$$

then do:

$$g^i = b(g^{-m})^j \bmod p$$

This requires to compute the inverse of $g$. Whats wrong if I transform it this way?: $$g^{jm+i} = b \bmod p$$ to $$g^{jm} + g^{i} = b \bmod p$$ and then lastly: $$g^{i} = \frac{b}{g^{jm}} \bmod p$$

This division of $g^{jm}$ should be possible, when p is prime right? Why can't I compute the Giant Steps, with the expression I got on the right? Thanks for your help.

taomii
  • 1
  • It's the same exact thing: $bg^{-mj} = \frac{b}{g^{jm}}$ by laws of exponents. We just hate writing "division" in modular arithmetic. – Randall Jul 13 '21 at 17:18
  • Also, you are missing that $i$ and $j$ run independently over the same index set. You have to compute lots of terms with $i$ and separately lots of terms for $j$ and search for a match. When you argue your way, you are assuming you already have the match in hand. – Randall Jul 13 '21 at 17:25
  • Let's assume $p = 29, g = 11$ and $b = 3$

    , m is ceil(sqrt(p)) = 6 .

    If I do it by the texts, I calculate inverse of g first -> 8 .

    Then lets take j = 2 for example. I do $3*(8^{6})^2 \bmod 29$, which is 14 .

    If I do it my proposed way for j = 2: $\frac{3}{11^{6*2}} \bmod 29$, which is some very small number and not 18.

     – taomii Jul 13 '21 at 17:48
  • That's my whole point. You do not know ahead of time the particular values of $i$ and $j$ that will make a match. Why should they be equal for $j=2$? – Randall Jul 13 '21 at 17:56
  • Im not talking about the indexes $i$ at all in the moment, just the expressions on the right side, that you said were the exact same thing. It appears they are not. – taomii Jul 13 '21 at 18:01
  • You are doing something wrong on your calculator: they are equal. I just checked. – Randall Jul 13 '21 at 18:04
  • I have a guess that you are accidentally calculating $\left( \frac{b}{g^j}\right)^m$, committing an order-of-operations error. – Randall Jul 13 '21 at 18:05
  • I also get the same numbers, when I don't take the modular inverse for $g$ in $g^{-m}$ and just calculate it the "normal" way. I have a guess that you are not calculating the inverse $g^{-1}$ ? – taomii Jul 13 '21 at 18:17
  • I don't understand. You either calculate $g^{-m}$ or you calculate $h^m$ where $h=g^{-1}$ (because they are the same thing). Are you by chance accidentally computing $h^{-m}$, thereby killing the inverse by accident? – Randall Jul 13 '21 at 18:19

0 Answers0