桁上げ保存加算器
桁上げ保存加算器(けたあげほぞんかさんき、Carry-save adder)は加算器の一種で、計算機などで3個以上の二進法 n {\displaystyle n} ビットの数の和を計算するのに使用される。他の加算器とは異なり、入力と同じサイズの二つの数(部分和ビットの列と桁上げビットの列)を出力する。
桁上げ保存加算の各ステージでは、
加算の結果はすぐにわかる。
加算の結果がある値より大きいか小さいか(例えば正か負か)は、やはりわからない。
後者については、モジュラ乗算(乗算後に除算を行い、その剰余のみを用いる演算)の実装に桁上げ保存加算器を用いる際に欠点となる。中間結果がその法より大きいか小さいかがわからなければ、法を引くかどうかが決まらないためである。
モンゴメリ乗算は、結果の右端の桁に依存する演算で、この解の一つである。とはいえ、桁上げ保存加算そのものと同様、固定的なオーバヘッドがあるので、連続したモンゴメリ乗算なら時間の節約になるが、1回だけであればそうはならない。幸い、冪乗は、事実上連続した乗算で、公開鍵暗号で最も頻繁に利用される演算である。