[6846] in cryptography@c2.net mail archive
Re: A non-parellelizable form of hashcash
daemon@ATHENA.MIT.EDU (Bram Cohen)
Sat Mar 25 18:30:57 2000
Date: Sat, 25 Mar 2000 15:11:29 -0800 (PST)
From: Bram Cohen <bram@gawth.com>
To: cryptography@c2.net
In-Reply-To: <Pine.LNX.4.10.10003251345300.9678-100000@ultra.gawth.com>
Message-ID: <Pine.LNX.4.10.10003251459180.9678-100000@ultra.gawth.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
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
