桁上げ保存加算器
次の和を考える: 12345678 + 87654322 =100000000
算術では、右から左に、"8+2=0, 桁上げ1"、"7+2+1=0, 桁上げ1"、"6+3+1=0, 桁上げ1"、のように和の最後まで計算を続ける。この方法では、右端の桁の結果はすぐにわかるものの、左端の桁の結果は、各桁の桁上げをその左に伝えていきながら、すべての桁の計算が終わるまでわからない。したがって、2個の n {\displaystyle n} 桁の数の加算には、たとえ並列処理のできる機械を用いたとしても、 n {\displaystyle n} に比例した時間がかかる。
電子工学的に2進数のビットを用いて言えば、このことは、 n {\displaystyle n} 個の1ビット加算器が自由に使えるとしても、桁上げが数の端から端まで伝播する可能性があるので、 n {\displaystyle n} に比例した時間が必要であることを意味する。この伝播が終わるまで、
加算の結果はわからない。
加算の結果がある値より大きいか小さいか(例えば正か負か)はわからない。
この遅延は、桁上げ先見加算器により緩和することができる。原理的には、この遅延を log  n {\displaystyle \log n} に比例する程度にまで減少させることはできるが、非常に大きな数に対しては当てはまらない。それは、桁上げ先見を実装しても、信号がチップ上を移動する距離が n {\displaystyle n} に比例して増加し、伝播遅延も同じ比率で増加するためである。公開鍵暗号に必要とされるような512ビットから2048ビットのような大きな数に対しては、桁上げ先見は力不足である。