バレットの還元アルゴリズム
a mod n = { r if r < n r − n otherwise {\displaystyle a\,{\bmod {\,}}n={\begin{cases}r&{\text{if }}r<n\\r-n&{\text{otherwise}}\end{cases}}}
このとき、 r < 2 n {\displaystyle r<2n} であることが以下のように示せる。
a ≤ 2 k {\displaystyle a\leq 2^{k}} なら
a 2 k ⋅ ( 2 k mod n ) < n {\displaystyle {\frac {a}{2^{k}}}\cdot (2^{k}\mod n)<n}
である。 n ⋅ m a mod 2 k 2 k < n {\displaystyle n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<n} が a {\displaystyle a} にかかわらず成立するので、以下の式変形を得る。
a ⋅ ( 2 k mod n ) 2 k + n ⋅ m a mod 2 k 2 k < 2 n {\displaystyle {\frac {a\cdot (2^{k}\mod n)}{2^{k}}}+n\cdot {\frac {ma\mod 2^{k}}{2^{k}}}<2n}