15.2.6 完全剰余

完全除算アルゴリズムの各ステージで，フル減算が実行され，割られる数が割る数の倍数ではない時には， 低い桁にはゼロリムが生成され，高いリムには剰余が生成されます。割られる数がa, 割る数が d, 商が qとすると， b = 2^mp_bits_per_limb,より，剰余 r は次の形になります。

a = q*d + r*b^n

nは減算で生成されるゼロリムの数を表わしており，qに対して生成されるリムの数になります。 rは 0<=r<dの範囲の数で，剰余とみなすことができますが，b^nの倍数でシフトすると得ることができます。

各ステージでフル減算を行って桁の借り上げを行うと，通常の除算として同数の交差積が実行されますが， いくつかの単一リム除算が節約できます。 dが単一リムの時は，複数の簡易化が起き，プロセッサの数だけスピードアップできます。

mpn_divexact_by3関数, mpn_modexact_1_odd関数，内部関数のmpn_redc_X はそれぞれ微妙にrの返し方が違っており，上記の式における符号反転処理を先行して行っていたりしますが， 基本的には同じ処理を行っています。

aがdの倍数であれば当然rはゼロになるので，通常の除算よりも，割り切れるかどうかのテストや合同かどうかのテストは高速になります。

rの因数 b^nは dが奇数の時にはGCD内で無視できます。従ってmpn_gcd_1や mpz_kronecker_ui等の関数をmpn_modexact_1_odd で利用できます(see Greatest Common Divisor Algorithms)。

Montgomeryの REDC法は，モジュラ乗算を行う手法で，x*b^-n や y*b^-n という形のオペランドを利用します。(x*b^-n)*(y*b^-n)を計算する際には，b^nの倍数を完全剰余計算で利用し， (x*y)*b^-n(see Modular Powering Algorithm)と同じ形の積を得ます。

rは一般的に通常の剰余a mod dについての情報を得るには役立ちません，というのも b^n mod dは何にでもなり得るからです。しかしながらb^n ≡ 1 mod dであれば， rは通常の剰余の負数になります。 これはdがb^n-1の因数であれば必ずそうなります。例えば3の場合はmpn_divexact_by3で起こります。 32bitリムや64bitリムでは，この因数が5, 17，257を含むので，このような場合に対する応用は効きません。