バレットの還元アルゴリズム
a − ( a − a ⋅ ( 2 k mod n ) 2 k ) + n ⋅ ( m a mod 2 k ) 2 k < 2 n {\displaystyle a-\left(a-{\frac {a\cdot (2^{k}\mod n)}{2^{k}}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}
a − a 2 k ⋅ ( 2 k − ( 2 k mod n ) ) + n ⋅ ( m a mod 2 k ) 2 k < 2 n {\displaystyle a-{\frac {a}{2^{k}}}\cdot \left(2^{k}-(2^{k}\mod n)\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}
a − n a 2 k ⋅ ( 2 k − ( 2 k mod n ) n ) + n ⋅ ( m a mod 2 k ) 2 k < 2 n {\displaystyle a-{\frac {na}{2^{k}}}\cdot \left({\frac {2^{k}-(2^{k}\mod n)}{n}}\right)+{\frac {n\cdot (ma\mod 2^{k})}{2^{k}}}<2n}