Re: fast modular multiplication inverse

Wei Dai (weidai@eskimo.com)
Wed, 6 May 1998 14:19:32 -0700

• Next message: Bill Stewart: "ANNOUNCE Bay Area Cypherpunks Meeting - May 9, 12-6pm"
• Previous message: Pete Klammer: "Comment on Science News article re: Rivest's Chaffing and Winnow ing"

On Sat, May 02, 1998 at 04:06:24PM -0600, staym@accessdata.com wrote:
> Never mind. Odds don't have unique inverses either. Sorry for the
> trouble.

Odds do have unique inverses mod 2^m. Remember that the units in Z_n form
a group under multiplication, and every element of a group has a unique
inverse.

This algorithm takes 8 multiplications to compute an inverse mod 2^32. You
can shave off 4 of them by using a table to compute A^-1 mod 2^8 and then
starting i at 8.

// derived from a function in Crypto++, but not tested
// computes inverse of A mod 2^(sizeof(word)*8)
word InverseModPower2(word A)
{
        assert(A%2==1);

        word R=A%8;

        for (unsigned i=3; i<sizeof(word)*8; i*=2)
                R = R*(2-R*A);

        assert(R*A==1);

        return R;
}

• Next message: Bill Stewart: "ANNOUNCE Bay Area Cypherpunks Meeting - May 9, 12-6pm"
• Previous message: Pete Klammer: "Comment on Science News article re: Rivest's Chaffing and Winnow ing"