On Sat, 25 Mar 2000, Bram Cohen wrote:
> Alice is capable of computing f(w) quickly using the formula
>
> f(n) = s^(2^n) + s^(-(2^n)) (mod p)
I neglected to point out that she does this by first computing
e = 2^n (mod p-1)
and then computing
s^e (mod p)
Which is equal to s^(2^n) mod p since
s^(p-1) (mod p) = 1
(One of the more basic theorems in number theory.)
Using that technique, s^(2^n) is computed using only two modular
exponentiations, and s^(-(2^n)) can be computed with no further
exponentiations by using
s^(-(2^n)) = 1/(s^(2^n)) (mod p)
(Apparently (p-1)/2 should be odd, to maximize the number of possibilities
for e, although I think that may already be a requirement to make square
roots difficult.)
-Bram Cohen
