====== Erweiterter Euklid'scher Algorithmus ======

TODO

===== Beispiel einer Implementierung =====

<code=c>
unsigned int mulInv (unsigned int e, unsigned int m)
{
	if (ggT(e,m) != 1) return 0; //ggT berechnet den größten gemeinsamen Teiler
	unsigned int r0, r1;
	unsigned int rmod;
	int x0, x1, xmod;
	x0 = 1; x1 = 0;
	r0 = e;
	r1 = m;
	rmod = r0;
	do {
		xmod = x0 - (r0/r1)*x1;
		x0 = x1;
		x1 = xmod;
		r0 = r1;
		r1 = rmod;
		rmod = r0 % r1;
	} while (rmod > 0);
	while (x1 < 0) x1 += m;
	return x1;
}
</code>

Anmerkung: Die Funktion ggT berechnet den [[theory:math:numbertheory:euklid_algorithm|größten gemeinsamen Teiler mit dem euklid'schen Algorithmus]].