[Botan-devel] Multiplicative inverse in Botan?

Jack Lloyd lloyd at randombit.net
Mon Dec 13 08:09:47 EST 2010


On Sun, Dec 12, 2010 at 08:39:09PM +0000, Eugene N wrote:
> Greetings!
> 
> I was wondering, where is the class (method) to calculate
> multiplicative inverse modulo n in Botan?


Hi Eugene,

You can use inverse_mod from numthry.h:

BigInt inverse_mod(const BigInt& x, const BigInt& n);

returns x^-1 mod n, or 0 if no such inverse exists (using
extended gcd).

If n is prime, you can also use Fermat's little theorem to
compute the inverse. The theorem tells us that for any prime p
and any x, x^(p-1) == 1 mod p. Thus, x^(p-2) == x^-1 mod p.
You could compute this using power_mod (also from numthry.h),

  BigInt inv_x = power_mod(x, p-2, p); // x^(p-2) mod p

This is typically slower, but has the advantage that it is
possible to compute in constant time.

On your earlier message about point multiplication:

PointGFp (the class representing a point on a curve) has
operators * and *= for scalar multiplication. The curve to use is
implicit to the point, so you don't have to specify this
explicitly.

  PointGFp point;
  BigInt scalar;
  PointGFp result = scalar * point;
  point *= scalar;
  assert(result == point);

-Jack



More information about the botan-devel mailing list