バレットの還元アルゴリズム

合同算術において、バレットの還元アルゴリズムは P.D. バレットによって 1986 年に開発されたアルゴリズムである。以下の式を計算することを考える。
愚直な方法は、高速な除算アルゴリズムを使用する方法である。バレットの還元アルゴリズムは、除算を乗算に置き換えることにより、formula_2 が定数で formula_3 であるときにこの計算を高速化する。
着想.
formula_2 の浮動小数点数としての逆数を formula_5 とおくと、formula_6 を床関数として
となる。formula_8 が十分な精度で計算される限り、これは誤差なく成り立つ。
1ワード版のバレットの還元アルゴリズム.
バレットが最初に考案したのは、上記のアルゴリズムの整数版であり、特に値がマシンのワードに収まる場合に適用できる。
上記の方法で formula_9 を整数の範囲内で計算する場合、自明に対応するのは formula_2 による除算を用いる方法である。
func reduce(a uint) uint {
 q := a / n // 小数部分は暗黙に切り捨てられる
 return a - q * n
しかし、除算の計算には時間がかかり、CPUによっては定数時間で完了しない命令が使用されうる。そこで、バレットの方法では formula_11 による除算なら低コストな右シフトとして実現できることに注目し、formula_12 を formula_13 で近似する。
formula_11 が与えられたとき、最良の formula_15 を見つけるために以下の式を考える。
formula_15 を整数にするために、formula_18 をどうにか整数に丸める必要がある。最も近い整数に丸めるのが最適だが、formula_13 が formula_12 より大きくなるとアンダーフローを生じうるため、一般には formula_21 を用いる。
すると、前述の関数は以下のように書き換えられる。
func reduce(a uint) uint {
 q := (a * m) » k // "» k" は k ビットの右シフト
 return a - q * n
ここで、formula_22 なので、この関数における codice_1 は小さめに評価される。これによりcodice_2は formula_23 に必ずしも収まらず、formula_24 の値を取りうる。そのため、値が formula_2 を超えた場合は formula_2 を引くことによってこれを補正する。
func reduce(a uint) uint {
 q := (a * m) » k
 a -= q * n
 if n <= a {
 a -= n
 return a
formula_13 は近似にすぎないので、近似が正当となる formula_28 の範囲を考える必要がある。formula_12 の近似誤差は
なので、codice_1の誤差はformula_31である。formula_32、すなわち formula_33 である限り、この還元は正当である。formula_34 である場合も必ずしもこの関数が誤った値を返すわけではないが、formula_28 を先述の範囲内に収めることで一般の場合においての正当性を保証できる。
formula_36 を大きく取ると、還元が正当となる formula_28 の範囲は広がる一方、他の計算においてオーバーフローを生じる可能性がある。
例.
16 ビット整数のシステム上で formula_38 としたときを考える。
アルゴリズムが意味をなすためには、少なくとも formula_36 は formula_40 以上である必要がある。さもなくば、剰余を必要としない小さい値に対してしか還元が正しく動作しなくなってしまう。formula_41 のときは、formula_42 であり、formula_43 のときは formula_44 である。後者においては formula_45 を formula_46 で近似することになるので、前者における formula_47 による近似と全く等価になる。formula_48 とすれば formula_49 となり、よりよい近似を得る。
formula_41 と formula_48 において、アルゴリズムが正しい値を与える入力の範囲を考える。前者においては、formula_52 なので、formula_33 すなわち formula_54 である。formula_28 は整数なので、実質的な上限は 478 である。（実際は 504 まで正しく動く。）
formula_48 においては、formula_57 なので formula_28 の実質的な上限は 7387 である。（実際は 7473 まで正しく動く。）
近似がより良くなる次の formula_36 は 13 であり、formula_60 を与える。もっとも、計算途中に現れる formula_61 が formula_62 でオーバーフローすることに注意すれば、この問題設定では formula_41 とした方が良い。
特定の k に対する証明.
formula_64 なる最小の整数 formula_65 をとり、formula_36 を formula_67 とすると、これは上記の式で説明した「意味をなす」formula_36 である。前述のコードに対応して次の値を定義する。
床関数の定義から、formula_71 は整数で、formula_72 である。また、formula_73 なら formula_74 となる。このとき、前述のコードを数式で表すと
このとき、formula_74 であることが以下のように示せる。
formula_73 なら
である。formula_79 が formula_28 にかかわらず成立するので、以下の式変形を得る。
マルチワード版のバレットの還元アルゴリズム.
バレットはこのアルゴリズムをRSA暗号の実装のために考案した。しかし、RSA暗号においては入力値は基本的にワードサイズを超える。そのためバレットは上記のアルゴリズムのマルチワード版も与えた。詳細については "Handbook of Applied Cryptography" を参照のこと。
多項式に対するバレットのアルゴリズム.
バレットのアルゴリズムは多項式除算に対しても適用できる。これは、多項式を反転して X 進数を用いることで計算される。