Re: [FWP] Counting bits from the other end

[Bennett Todd <bet@rahul.net>]

2000-05-02-19:27:26 Bernie Cosell:
> Indeed, as as another side effect of some math background, note that to 
> verify that you don't need to do 64-bit-arithmetic.
> 
>     if a mod b = c, then 2a mod b = 2c mod b

Also cool.

And for one of those weird coincidences, I learned just last night
that one of my coworkers is a real math dude, so I asked him this
one, and he was able to point out to me a simple proof; it all hangs
on the fact that arithmetic on positive integers modulo a prime has
all the groovy properties that make sense, that we expect when
doing normal arithmetic with integers. So if you start with:

	2**a == 2**b (mod prime N, N>a and N>b)

then you can just multiply both sides by 2**(-a) and reduce and it
dissolves right down to a==b. In other words, there are no
collisions. This is so spiffy.

-Bennett

PGP signature