快速幂模的两种实现
虽然这个算法已经滥大街了,但我们离散数学课里讲的al-kachi算法与常见的二进制幂略有不同, 所以写篇笔记记录一下。伪代码通俗易懂,但具体实现比较让人不爽。
这里把两种算法的代码都写出来,另外附加一个脑袋被驴踢了的SB代码。
ALGORITHM 1.
常见的快速幂模求解形如 Result = a^e mod b, 将e转化为2进制,然后按二进制位从右到左:
INPUT: a, e, b;
INIT: Res = 1, a = a mod b
LOOP (e IS NOT 0):
IF e % 2 == 1:
Res = (Res * a) mod b
END IF
a = a * a
e = e / 2
ENDLOOP
OUTPUT: Res = a^e mod b
ALGORITHM 2.
我们老师说这叫Al-Kachi算法,同样将e转化为2进制,但按二进制位从左到右.
INPUT: a, e, b;
INIT: Res = 1, a = a mod b
LOOP (digit d in binary e, from left to right):
IF d == 1:
Res = Res * Res * a mod b
ELSE:
Res = Res * Res mod b
ENDIF
ENDLOOP
OUTPUT: Res = a^e mod b
CODE:
|
|
[+] click to leave a comment [+]
the comment system on this blog works via email. The button below will generate a mailto: link based on this page's url and invoke your email client - please edit the comment there! [optional] even better, encrypt the email with my public key - don't modify the subject field - specify a nickname, otherwise your comment will be shown as anonymous - your email address will not be disclosed - you agree that the comment is to be made public. - to take down a comment, send the request via email.>> SEND COMMENT <<