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