![](https://csdnimg.cn/release/download_crawler_static/85393565/bg4.jpg)
.....
word 格式 .整理版
对于 C=A/B,由于无法将 B 对 A“试商”,我们只能转换成 B[q] 对 A[p] 的试商
来得到一个近似值,所以无法直接通过计算 C来获得 C,只能一步步逼近 C。由
于: B*(A[p]/B[q]-1)*0x100000000**(p-q)<C ,令: X=0,重复 A=A-X*B,
X=X+(A[p]/B[q]-1)*0x100000000**(p-q) ,直到 A<B则:X=A/B,且此时的 A=A%B,
注意对于任意大数 A*0x100000000**k ,都等价于将 A 的数组中的各元素左移 k
位,不必计算;同样, A/0x100000000**k 则等价于右移。
( 三) 欧几里得方程
在 RSA 算法中,往往要在已知 A、N的情况下,求 B ,使得 (A*B)%N=1。即
相当于求解 B、M都是未知数的二元一次不定方程 A*B-N*M=1 的最小整数解。 而
针对不定方程 ax-by=c 的最小整数解,有著名的欧几里德算法,即辗转相除法。
事实上二元一次不定方程有整数解的充要条件是 c 为 a、b 的最大公约数。即当
c=1 时,a、b 必须互质。而在 RSA算法里由于公钥 d 为素数,素数与任何正整数
互质,所以可以通过欧几里德方程来求解私钥 e。
欧几里德算法是一种递归算法,比较容易理解:
例如: 11x-49y=1,求 x
(a) 11 x - 49 y = 1 49%11=5 ->
(b) 11 x - 5 y = 1 11%5 =1 ->
(c) x - 5 y = 1
令 y=0 代入( c)得 x=1
令 x=1 代入( b)得 y=2
令 y=2 代入( a)得 x=9
同理可使用递归算法求得任意 ax-by=1 (a、b 互质)的解。实际上通过分
析归
纳将递归算法转换成非递归算法就变成了大衍求一术:
x=0,y=1
WHILE a!=0
i=y
y=x-y*a/b
x=i
i=a
a=b%a
b=i
IF x<0 x=x+b
RETURN x
( 四) 模幂运算
模幂运算是 RSA 的核心算法,最直接地决定了 RSA 算法的性能。针对快速
模幂运算这一课题, 西方现代数学家提出了大量的解决方案, 通常都是先将幂模
运算转化为乘模运算。例如求 D=C**15 % N,由于: a*b % n = (a % n)*(b % n) %
n,所以:
C1 =C*C % N =C**2 % N
C2 =C1*C % N =C**3 % N
C3 =C2*C2 % N =C**6 % N
C4 =C3*C % N =C**7 % N
C5 =C4*C4 % N =C**14 % N