使用欧拉Φ函数和欧拉定理计算模取幂的周期

2019-04-14 19:29发布生成海报

站内文章 / 模拟电子

17328 0

1. 模取幂问题

计算模取幂a^n mod m时，可使用如下算法（偷懒一下，直接给scheme代码），时间复杂度为log(n)，效率很高。

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))

但当指数n不直接给出，而是由其他函数定义时，上述算法可能不太适用。例如计算a^(b^n) mod m，无法按照上述算法直接对n进行降次。
按照一般的经验，序列a^n mod m, n=1,2,3...是具有周期性的，例如下面分别计算当a=2和3，m=7和11，序列的前20项如下，其周期分别为3和5 1 ]=> (map (lambda (x) (expmod 2 x 7)) (iota 20 1));Value 11: (2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4)1 ]=> (map (lambda (x) (expmod 3 x 11)) (iota 20 1));Value 12: (3 9 5 4 1 3 9 5 4 1 3 9 5 4 1 3 9 5 4 1)
假如能够计算出序列a^n mod m的周期t，则a^(b^n) mod m的问题可通过b^n mod t来间接计算。
寻找周期t的一个很自然的方法为，通过计算序列有限项数，在其中搜索循环部分的长度，但该方法不太准确，且周期t很大时，需要计算很多项，效率不高。
下面介绍一种使用数论中的欧拉Φ函数和欧拉定理计算模取幂序列周期的方法。

2. 欧拉Φ函数

欧拉Φ函数Φ(n)定义为不大于n且和n互素的正整数的个数，例如小于10且与其互素的正整数有1, 3, 7, 9，所以Φ(10)=4.
欧拉Φ函数有如下重要性质， (1) 对于任意素数p，有Φ(p) = p-1 (2) 欧拉Φ函数为乘性函数，即Φ(mn) = Φ(m)Φ(n)， m，n均为正整数 (3) 设n的素因数分解形式为 (p1^k1) * (p2^k2) *...* (ps^ks), pi均为素数，ki≥0，则 Φ(n) = n(1-1/p1)(1-1/p2)...(1-1/ps)

3. 欧拉定理

对于互素的正整数a和n，a^Φ(n) ≡ 1 (mod n)

4. 模取幂的周期

设序列a(n) = a^n mod m, a,n,m均为正整数, n≥1, a>1, m>1,
令d = gcd(a, m), d≥1
a = d*a',
n = (d^s)*q, s≥1, q≥1, 且gcd(d, q)=1,
有如下结论成立:

1. 如果d=1, 有a(k) = a(k+t), k≥1, t=Φ(m)，即序列a(n)从第1项开始, 以周期t循环;

2. 如果d>1, 有a(k) = a(k+t), k≥s, t=Φ(m)，即序列a(n)从第s项开始, 以周期t循环;

3. 如果d>1, 且q=1, 有a(k) = 0, k≥s，即序列a(n)从第s项开始全部为0
注1：上述t不一定是最小周期

5. 证明:

1. 根据欧拉定理, 如果gcd(a, m)=1, 则有a^Φ(m) ≡ 1 (mod m), 所以
a(k+t) = a^(k+Φ(m)) mod m
= (a^k mod m) * (a^Φ(m) mod m) mod m
= a^k mod m
= a(k)
结论1得证

2. 设序列d(n) = d^n mod m, a'(n) = a'^n mod m, 则
a(n) = a^n mod m = (d*a')^n mod m = ((d^n mod m) * (a'^n mod m)) mod m
= (d(n) * a'(n)) mod m
下面分别证明从第s项开始，序列d(n)和a'(n)有共同的周期t=Φ(m)
由于gcd(a', m)=1, 根据上述结论1, 对于序列a'(n), 有
a'(k) = a'(k+t), k≥1, t=Φ(m) 即序列a'(k)从第1项开始，以周期t循环，显然从第s项开始，循环周期依然为t。
由于gcd(d, q)=1, 根据结论1, 有
d^k mod q = d^(k+r) mod q, k≥1, r=Φ(q), 即
q | (d^(k+r) - d^k,
两边同时乘以d^s, 有
(d^s)*q | d^(s+k+r) - d^(s+k), 即
d^(s+k+r) mod m = d^(s+k) mod m, 即
d(k) = d(k+r), k≥s, r=Φ(q)
由于欧拉函数为乘性函数, 有Φ(m) = Φ(d^s)Φ(q), 所以Φ(q)|Φ(m), 即
r|t, 所以t也是上述序列d(k)的周期, 即
d(k) = d(k+t), k≥s, t=Φ(m) 即序列d(k)从第s项开始，已周期t循环。

根据上述分析, 当k≥s时, 序列d(n)和a'(n)有相同的周期t=Φ(m), 所以
a(k) = (d(k) * a'(k)) mod m
= (d(k+t) * a'(k+t)) mod m
= a(k+t)
结论2得证

3. 当q=1时, d(s) = d^s mod m = 0, 且对于任意k>0, 有
d(s+k) = (d(s) * d^k) mod m = 0
结论3得证