shithub: sl

ref: 12c9d2fc728b51aa1eb9a70d0d331eb9464912d9
dir: /3rd/mp/mpinvert.c/

View raw version 
#include "platform.h"
#include "mp.h"

// use extended gcd to find the multiplicative inverse
// res = b**-1 mod m
void
mpinvert(mpint *b, mpint *m, mpint *res)
{
	mpint *v;

	v = mpnew(0);
	mpextendedgcd(b, m, v, res, nil);
	if(mpcmp(v, mpone) != 0){
		fprintf(stderr, "mpinvert: impossible\n");
		exit(2);
	}
	mpfree(v);
	mpmod(res, m, res);
}