[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