[tromp]

About 1/4 down the page the author summarizes a sequence of optimizations of the basic ElGamal scheme.

I don't quite understand the "Eliminate divisions" step, which transforms

B^H(R,M) = A R^S

into

B^S = R A^H(R,M)

How are these two related?

[fryguy]

I don't think they are related per se. Given A = B^a and R = B^r (not explicitly said in the first paragraph about El-Gamal, S is calculated by S = (H(R,M) - a)/r at the "Merge the hashes" step.

At the next step, he's giving a completely new formula that looks similar: B^S = R * A^H(R,M) = B^r * B^a^H(R,M). However, this one is solved by S = r+a*H(R,M), which is a much easier thing to calculate, since there are no divisions.