多倍長演算ライブラリ ルーチン１８

［ 簡単な説明 ］

法 n における逆数を求めます。アルゴリズムはユークリッドの互除法です。
数 ｘ に関して、(ｘ × ｙ) mod ｎ＝１ となる ｙ を、ｘ の法 ｎ における逆数と言います。
例えば、５の法１１における逆数は９です。（(５×９)mod１１＝１）
ｘ と ｎ が互いに素である（共通因数をもたないこと、必ずしも素数である必要はない）ならば、ｙ は唯一つ存在します。
（注：上記の例では、(５×２０)mod１１＝１ も成立しますが、法１１のもとでは、数値は０〜１０の有限の世界であり、２０もまた法１１のもとでは＝９となります。（２０mod１１＝９）

プログラム・ソース（"linv.c"） 　　　　　　　　　　top （トップに戻る） 
/*		linv.c		*/
#include "longint.h"

/* GCD(s, n) = 1  :  s * x = 1 (mod n) */

LINT linv(LINT s, LINT n)
{
	LINT q, t, u, v, w;

	t = n;
	u = lset(1);
	v.len = 0;
	while(s.len > 0)
	{
		q = ldivide(t, s, &w);
		t = s;
		s = w;
		w = lmul(q, u);
		w = lsub(v, w);
		v = u;
		u = w;
	}
	if(v.sign == -1)	v = ladd(v, n);
	return v;
}