バレットの還元アルゴリズム
バレットはこのアルゴリズムをRSA暗号の実装のために考案した。しかし、RSA暗号においては入力値は基本的にワードサイズを超える。そのためバレットは上記のアルゴリズムのマルチワード版も与えた。詳細については Handbook of Applied Cryptography を参照のこと。
k = 7 {\displaystyle k=7} と k = 9 {\displaystyle k=9} において、アルゴリズムが正しい値を与える入力の範囲を考える。前者においては、 e = 1 / n − m / 2 k = 1 / 101 − 1 / 128 = 27 / 12928 {\displaystyle e=1/n-m/2^{k}=1/101-1/128=27/12928} なので、 a < 1 / e {\displaystyle a<1/e} すなわち a < 478.81 {\displaystyle a<478.81} である。 a {\displaystyle a} は整数なので、実質的な上限は 478 である。(実際は 504 まで正しく動く。)
k = 9 {\displaystyle k=9} においては、 e = 1 / 101 − 5 / 512 = 7 / 51712 {\displaystyle e=1/101-5/512=7/51712} なので a {\displaystyle a} の実質的な上限は 7387 である。(実際は 7473 まで正しく動く。)
近似がより良くなる次の k {\displaystyle k} は 13 であり、 81 / 8192 {\displaystyle 81/8192} を与える。もっとも、計算途中に現れる a x {\displaystyle ax} が 810 ≤ a {\displaystyle 810\leq a} でオーバーフローすることに注意すれば、この問題設定では k = 7 {\displaystyle k=7} とした方が良い。