幂模m与逐次平方法

  • 时间:
  • 来源:互联网
  • 文章标签:

文章目录

1 计算幂模 m m m

  如何计算:
5 100   000   000   000   000   ( m o d   12   830   603 ) 5^{100\ 000\ 000\ 000\ 000}\ (mod\ 12\ 830\ 603) 5100 000 000 000 000 (mod 12 830 603)
呢?这么大的数字显然是不能硬算的,如果 12830603 12830603 12830603是素数,我们可以使用费马小定理简化计算,即便不是素数,也可以使用欧拉公式。但即便简化了计算,剩余的计算量依旧大的离谱:
5 6   546   640   ( m o d   12   830   603 ) 5^{6\ 546\ 640}\ (mod\ 12\ 830\ 603) 56 546 640 (mod 12 830 603)

  进行这样的大数计算是很实用的,它可以用来做加密,而且产生的密码使用目前最先进的破译技术也不能破译。用来计算 a k   ( m o d   m ) a^k\ (mod\ m) ak (mod m)的一个巧妙想法叫做逐次平方法。在叙述一般方法之前,先用一个例子体现它的思想。

7 327   ( m o d   853 ) 7^{327}\ (mod\ 853) 7327 (mod 853)

  第一步创建表格,给出 7 , 7 2 , 7 4 , 7 8 , 7 16 , ⋯ ( m o d   853 ) 7,7^2,7^4,7^8,7^{16},\cdots (mod\ 853) 7,72,74,78,716,(mod 853)的值。注意,要得到表中的每个项,我们仅仅需要平方前面的数。由于在平方前总是模 853 853 853进行简化,所以从未使数大于 85 3 2 853^2 8532,下面是 7 2 k   ( m o d   853 ) 7^{2^k}\ (mod\ 853) 72k (mod 853)的列表

7 1 ≡ 7 ≡ 7   ( m o d   853 ) 7 2 ≡ ( 7 1 ) 2 ≡ 7 2 ≡ 49 ≡ 49   ( m o d   853 ) 7 4 ≡ ( 7 2 ) 2 ≡ 4 9 2 ≡ 2401 ≡ 695   ( m o d   853 ) 7 8 ≡ ( 7 4 ) 2 ≡ 69 5 2 ≡ 483025 ≡ 227   ( m o d   853 ) 7 16 ≡ ( 7 8 ) 2 ≡ 22 7 2 ≡ 51529 ≡ 349   ( m o d   853 ) 7 32 ≡ ( 7 16 ) 2 ≡ 34 9 2 ≡ 121801 ≡ 675   ( m o d   853 ) 7 64 ≡ ( 7 32 ) 2 ≡ 67 5 2 ≡ 455625 ≡ 123   ( m o d   853 ) 7 128 ≡ ( 7 64 ) 2 ≡ 12 3 2 ≡ 15129 ≡ 628   ( m o d   853 ) 7 256 ≡ ( 7 128 ) 2 ≡ 62 8 2 ≡ 394384 ≡ 298   ( m o d   853 ) \begin{aligned} &7^1\equiv7\equiv7\ (mod\ 853)\\ &7^2\equiv(7^1)^2\equiv7^2\equiv 49\equiv 49\ (mod\ 853)\\ &7^4\equiv(7^2)^2\equiv49^2\equiv 2401\equiv 695\ (mod\ 853)\\ &7^8\equiv(7^4)^2\equiv695^2\equiv 483025\equiv 227\ (mod\ 853)\\ &7^{16}\equiv(7^8)^2\equiv227^2\equiv 51529\equiv 349\ (mod\ 853)\\ &7^{32}\equiv(7^{16})^2\equiv349^2\equiv 121801\equiv 675\ (mod\ 853)\\ &7^{64}\equiv(7^{32})^2\equiv675^2\equiv 455625\equiv 123\ (mod\ 853)\\ &7^{128}\equiv(7^{64})^2\equiv123^2\equiv 15129\equiv 628\ (mod\ 853)\\ &7^{256}\equiv(7^{128})^2\equiv628^2\equiv 394384\equiv 298\ (mod\ 853) \end{aligned} 7177 (mod 853)72(71)2724949 (mod 853)74(72)24922401695 (mod 853)78(74)26952483025227 (mod 853)716(78)2227251529349 (mod 853)732(716)23492121801675 (mod 853)764(732)26752455625123 (mod 853)7128(764)2123215129628 (mod 853)7256(7128)26282394384298 (mod 853)

  下一步,将指数 327 327 327表成 2 2 2的幂次和:

327 = 256 + 71 = 256 + 64 + 7 = 256 + 64 + 4 + 3 = 256 + 64 + 4 + 2 + 1 327 = 256+71=256+64+7=256+64+4+3=256+64+4+2+1 327=256+71=256+64+7=256+64+4+3=256+64+4+2+1
现在使用 327 327 327的二进制展开式计算
7 327 = 7 256 + 64 + 4 + 2 + 1 = 298 ∗ 123 ∗ 695 ∗ 49 ∗ 7   ( m o d   853 ) 7^{327} = 7^{256+64+4+2+1} = 298*123*695*49*7\ (mod\ 853) 7327=7256+64+4+2+1=298123695497 (mod 853)
要完成 7 327   ( m o d   853 ) 7^{327}\ (mod\ 853) 7327 (mod 853)的计算,我们只需要程这 5 5 5个数,然后用模 853 853 853进行简化。如果所有 5 5 5个数的乘积对我们来说尝试太大,则可以乘前两个数简化,再与第三个数相乘简化,以这种方式,我们就不需要对任何大于 85 3 2 853^2 8532的数进行计算,因此:
298 ∗ 123 ∗ 695 ∗ 49 ∗ 7   ( m o d   853 ) = 828 ∗ 695 ∗ 49 ∗ 7   ( m o d   853 ) = 538 ∗ 49 ∗ 7   ( m o d   853 ) = 772 ∗ 7   ( m o d   853 ) ≡   286   ( m o d   853 ) \begin{aligned} 298*123*695*49*7\ (mod\ 853) &= 828*695*49*7\ (mod\ 853) \\ &= 538*49*7\ (mod\ 853)\\ &= 772*7\ (mod\ 853)\equiv\ 286\ (mod\ 853) \end{aligned} 298123695497 (mod 853)=828695497 (mod 853)=538497 (mod 853)=7727 (mod 853) 286 (mod 853)

2 逐次平方法

  算法(逐次平方计算 a k   ( m o d   m ) a^k\ (mod\ m) ak (mod m):用下述步骤计算 a k   ( m o d   m ) a^k\ (mod\ m) ak (mod m)的值:

  1. k k k表成 2 2 2的幂次和:
    k = u 0 + u 1 ∗ 2 + u 2 ∗ 2 2 + u 3 ∗ 2 3 + ⋯ + u r ∗ 2 r k = u_0 + u_1*2+u_2*2^2+u_3*2^3+\cdots +u_r*2^r k=u0+u12+u222+u323++ur2r
    其中 u i u_i ui 0 0 0 1 1 1
  2. 使用逐次平方法制作模 m m m a a a的幂次表
    a 1 ≡ A 0   ( m o d   m ) a 2 ≡ ( a 1 ) 2 ≡ A 0 2 ≡ A 1   ( m o d   m ) a 4 ≡ ( a 2 ) 2 ≡ A 1 2 ≡ A 2   ( m o d   m ) a 8 ≡ ( a 4 ) 2 ≡ A 2 2 ≡ A 3   ( m o d   m ) ⋮ a 2 r ≡ ( a 2 r − 1 ) 2 ≡ A r − 1 2 ≡ A r   ( m o d   m ) \begin{aligned} &a^1\equiv A_0\ (mod\ m)\\ &a^2\equiv(a^1)^2\equiv A_0^2\equiv A_1\ (mod\ m)\\ &a^4\equiv(a^2)^2\equiv A_1^2\equiv A_2\ (mod\ m)\\ &a^8\equiv(a^4)^2\equiv A_2^2\equiv A_3\ (mod\ m)\\ &\vdots\\ &a^{2^r}\equiv(a^{2^{r-1}})^2\equiv A_{r-1}^2\equiv A_r\ (mod\ m)\\ \end{aligned} a1A0 (mod m)a2(a1)2A02A1 (mod m)a4(a2)2A12A2 (mod m)a8(a4)2A22A3 (mod m)a2r(a2r1)2Ar12Ar (mod m)
    注意要计算表的每一行,仅需要取前一行最末的数,平方它然后用模 m m m简化。也注意到表有 r + 1 r+1 r+1行,其中 r r r是第一步中 k k k的二进制展开式中 2 2 2的最高指数。
  3. 乘积:
    A 0 u 0 ∗ A 1 u 1 ∗ A 2 u 2 ∗ ⋯ ∗ A r u r   ( m o d   m ) A_0^{u_0}*A_1^{u_1}*A_2^{u_2}*\cdots *A_r^{u_r}\ (mod\ m) A0u0A1u1A2u2Arur (mod m)
    同余于 a k   ( m o d   m ) a^k\ (mod\ m) ak (mod m)。注意到所有 u i u_i ui 0 , 1 0,1 0,1。因此这个数实际上是 u i = 1 u_i=1 ui=1的那些 A i A_i Ai的乘积。

3 算法实现

算法流程:

  • b = 1 b=1 b=1
  • k ≥ 1 k\ge 1 k1时,循环:
    1.如果 k k k是奇数则 b = a ∗ b   ( m o d   m ) b = a*b\ (mod\ m) b=ab (mod m)
    2.置 a = a 2   ( m o d   m ) a=a^2\ (mod\ m) a=a2 (mod m)
    3.置 k = k / 2 k = k/2 k=k/2(如果 k k k是奇数,转下)
  • 结束循环
  • 转到 b b b的值
def zcpf(a, k, m):
    b = 1
    a %= m
    while k >= 1:
        if k % 2 == 1:
            b = (a * b) % m
        a = a**2 % m
        k //= 2
    return b

print(zcpf(7, 327, 853))

输出:

286

4 参考资料

《数论概论》第四版 P74-P77

本文链接http://www.taodudu.cc/news/show-1781804.html