s********0
发帖数: 71 | 1 在RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重
复平方算法来实现，提高效率。
其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出
很罗嗦的过程），还专门写了代码放在Blog空间里考试的时候用—……
同样O(log(n))的递归算法其实很容易理解：
/* C */
int fast_mod(int x, int n, int m)
{
if (n == 0)
return 1;
else if (n % 2 == 0)
return square(fast_mod(x, n / 2, m)) % m;
else
return x * fast_mod(x, n - 1, m) % m;
}
#Python
fast_mod = lambda x, n, m: 1 if n == 0 else fast_mod(x, n / 2, m) ** 2 % m
if n % 2 == 0 else x * fast_mod(x, n - 1, m) % m
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast x n m)
(define (square x) (* x x))
(cond ((= n 0) 1)
((even? n) (remainder (square (mod-fast x (/ n 2) m)) m))
(else (remainder (* x (mod-fast x (- n 1) m)) m))))
(mod-fast 79 24 33)
;16
但是SICP要求写一个迭代版的。印象中我是记得可以把 n 写成二进制（比如n=13，
1101），然后一位一位地推。
试推了一下从高位到低位，倒是挺简单的，记B[i]为第 i 位的值，通过A[i] = A[i+1]
^2 * x^B[i] 从高到低计算出A[0]，就得到结果了。但是问题是，为了从高到低计算，
又得一次递归，似乎不能满足要求。
于是只好反过来，从低位往高位推。这个过程其实也挺简单的，举例来说：
当n=13，即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时，最终结果
ans = x^n % m
= x^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) % m
= [x^(1 * 2^3)] * [x^(1 * 2^2)] * [(x ^ (0 * 2^1)] * [x ^ (1 * 2^0)] % m
也就是说，从低到高，在第 i 位的时候，将 x^(Bit[i] * 2^i) % m 乘到结果中即可
。这里可以稍微变换一下：仅当Bit[i] == 1的时候，将x^(2^i) % m乘进去即可。所以
这里可以用一个辅助的变量 b 来保存 x^(2^i) % m，在每次迭代的过程中 b = b^2 %
m 。
于是实现就容易了：
/* C */
int fast_mod_iter(int x, int n, int m)
{
int a = 1, b = x; //i=0的时候b = x^(2^0) = x
while (n)
{
if (n % 2 == 1)
a = a * b % m;
b = b * b % m;
n /= 2;
}
return a;
}
#Python
def fast_mod(x, n, m):
a = 1
b = x
while True:
if n == 0:
return a
if n % 2 == 1:
a = a * b % m
b = b * b % m
n /= 2
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast-iter x n m)
(define (iter a b n)
(cond ((= n 0) a)
((even? n)
(iter a (remainder (* b b) m) (/ n 2)))
(else
(iter (remainder (* a b) m) (* b b) (/ (- n 1) 2)))))
(iter 1 x n))
(mod-fast-iter 79 24 33)
;16
//网上搜了下模重复平方算法，居然没有靠谱的算法解释，看来可能还是这个算法太简
单了吧。。。 | r*****g
发帖数: 434 | 2 这么学术的东东放错地方了吧
在RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重
复平方算法来实现，提高效率。
其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出
很罗嗦的过程），还专门写了代码放在Blog空间里考试的时候用—……
同样O(log(n))的递归算法其实很容易理解：
/* C */
int fast_mod(int x, int n, int m)
{
if (n == 0)
return 1;
else if (n % 2 == 0)
return square(fast_mod(x, n / 2, m)) % m;
else
return x * fast_mod(x, n - 1, m) % m;
}
#Python
fast_mod = lambda x, n, m: 1 if n == 0 else fast_mod(x, n / 2, m) ** 2 % m
if n % 2 == 0 else x * fast_mod(x, n - 1, m) % m
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast x n m)
(define (square x) (* x x))
(cond ((= n 0) 1)
((even? n) (remainder (square (mod-fast x (/ n 2) m)) m))
(else (remainder (* x (mod-fast x (- n 1) m)) m))))
(mod-fast 79 24 33)
;16
但是SICP要求写一个迭代版的。印象中我是记得可以把 n 写成二进制（比如n=13，
1101），然后一位一位地推。
试推了一下从高位到低位，倒是挺简单的，记B[i]为第 i 位的值，通过A[i] = A[i+1]
^2 * x^B[i] 从高到低计算出A[0]，就得到结果了。但是问题是，为了从高到低计算，
又得一次递归，似乎不能满足要求。
于是只好反过来，从低位往高位推。这个过程其实也挺简单的，举例来说：
当n=13，即二进制的 1101 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0时，最终结果
ans = x^n % m
= x^(1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0) % m
= [x^(1 * 2^3)] * [x^(1 * 2^2)] * [(x ^ (0 * 2^1)] * [x ^ (1 * 2^0)] % m
也就是说，从低到高，在第 i 位的时候，将 x^(Bit[i] * 2^i) % m 乘到结果中即可
。这里可以稍微变换一下：仅当Bit[i] == 1的时候，将x^(2^i) % m乘进去即可。所以
这里可以用一个辅助的变量 b 来保存 x^(2^i) % m，在每次迭代的过程中 b = b^2 %
m 。
于是实现就容易了：
/* C */
int fast_mod_iter(int x, int n, int m)
{
int a = 1, b = x; //i=0的时候b = x^(2^0) = x
while (n)
{
if (n % 2 == 1)
a = a * b % m;
b = b * b % m;
n /= 2;
}
return a;
}
#Python
def fast_mod(x, n, m):
a = 1
b = x
while True:
if n == 0:
return a
if n % 2 == 1:
a = a * b % m
b = b * b % m
n /= 2
;Scheme
(define (even? n) (= (remainder n 2) 0))
(define (mod-fast-iter x n m)
(define (iter a b n)
(cond ((= n 0) a)
((even? n)
(iter a (remainder (* b b) m) (/ n 2)))
(else
(iter (remainder (* a b) m) (* b b) (/ (- n 1) 2)))))
(iter 1 x n))
(mod-fast-iter 79 24 33)
;16
//网上搜了下模重复平方算法，居然没有靠谱的算法解释，看来可能还是这个算法太简
单了吧。。。
【在 s********0 的大作中提到】
: 在RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重
: 复平方算法来实现，提高效率。
: 其实这是大二学的《信息安全数学基础》里面的内容，那时为了考试需要（手算+写出
: 很罗嗦的过程），还专门写了代码放在Blog空间里考试的时候用—……
: 同样O(log(n))的递归算法其实很容易理解：
: /* C */
: int fast_mod(int x, int n, int m)
: {
: if (n == 0)
: return 1;
|
|
