常用算法设计方法5

图6-3 大整数X和Y的分段



    我们将

n位的二进制整数

X和

Y各分为

2段，每段的长为

n/2位（为简单起见，假设

n是

2的幂），如图

6-3所示。



由此，

X=A2^n/2+B，

Y=C2^n/2+D。这样，

X和

Y的乘积为：

XY=(A2^n/2+B)(C2^n/2+D)=AC2ⁿ+(AD+CB)2^n/2+BD    （

1）



    如果按式（

1）计算

XY，则我们必须进行

4次

n/2位整数的乘法

(AC，

AD，