バレットの還元アルゴリズム
2 k 0 > n {\displaystyle 2^{k_{0}}>n} なる最小の整数 k 0 {\displaystyle k_{0}} をとり、 k {\displaystyle k} を k 0 + 1 {\displaystyle k_{0}+1} とすると、これは上記の式で説明した「意味をなす」 k {\displaystyle k} である。前述のコードに対応して次の値を定義する。
q = ⌊ m a 2 k ⌋ {\displaystyle q=\left\lfloor {\frac {ma}{2^{k}}}\right\rfloor }
r = a − q n {\displaystyle r=a-qn} .
床関数の定義から、 q {\displaystyle q} は整数で、 r ≡ a ( mod n ) {\displaystyle r\equiv a{\pmod {n}}} である。また、 a ≤ 2 k {\displaystyle a\leq 2^{k}} なら r < 2 n {\displaystyle r<2n} となる。このとき、前述のコードを数式で表すと