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