-
模逆运算快速算法——扩展的
Euclid
算法
与扩展的
Stein
算法
(1)
扩展的
Euclid
算法
求模逆的传统算法是扩展的
E
uclid
算法，
该算法是在用
Euc
lid
算法求取二个数的最大公因子时，
若最
< br>大公因子为
1
，说明二个数互素，则可同时得出二者的乘
法逆元。
算法描述如下：
输入：二个整数
a
、
b
，设
a
?
b<
/p>
输出：
a
与<
/p>
b
的最大公因子；若二者互素，同时得出乘法逆元
Step 1:
(
X
1
,
X
2
,
X
3
)
?
(
1
,
< br>0
,
a
)
，
(
Y
1
,
Y
2
,
Y
3
)
?
(
0
,
1
,
N
)
Step 2:
if
Y
3
?
0
then return
X
3
?
gcd(
a<
/p>
,
b
)
，
no inverse
Step 3: if
Y
3
?
1
then return
Y
3
?
gcd(
a
,
b
)
，
b
?
1
?
Y
2
mod
a
，
a
?
1
?
< br>(
Y
1
?
b
)
mod
b
Step 4:
Q
?
?
X
3
Y
3
?
Step 5:
(
T
1
,
T
2
,
T
3
)
?
(
< br>X
1
?
QY
1
,
X
2
?
QY
2
,
X
3
?
QY
3<
/p>
)
Step 6:
< br>(
X
1
,
X
2
,
X
3
)
?
(
Y
1
,
Y
2
,
Y
3
)
Step 7:
(
Y<
/p>
1
,
Y
2
,
Y
3
)
?
(
T
1
,
T
2
,
T
3
)
Step 8: goto Step 2
(2)
扩展的
Stein
算法
较之扩展的
Euclid
算法，扩展的
Stein
算法可以得到更高的执行效率。
Stein
算法基于以下求取二个数公因子的基本性质：
1)
若
a<
/p>
与
b
都是偶数，则
gcd(
a
,
b
)
?
2
gcd(
< br>a
2
,
b
2
)
2)
若
a
为偶数、
b
为奇数，则
gcd(
a
,
b
)
?
gcd(
a
2
,
b
)
3)
若
a
与
b
都是奇数，则
gcd(
a
,
b
)
?
gcd(
(
a
?
b
)
2
,
b
)
由于除
2
在二进制运算中
仅做一次移位操作，因此可以说
Stein
算法主要只用到了减
法，通过计算复
杂性分析可知，在最坏情况下，
Stein
算法所需减法次数为
lb
(
a
)
?
(
lb
3
?
1
)
。
使用扩展的
< br>Stein
算法处理模逆运算的流程如下图所示。
-
-
-
-
-
-
-
-
-
上一篇：了解SCI、SSCI与CSCI、CSSCI的区别
下一篇：ENVI影像增强处理