幂模运算

1. 模运算

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a^b) % p = ((a % p)^b) % p

2. 费马定理

  • 1.若p是素数，a是正整数且不能被p整除，则：a^(p-1) mod p = 1 mod p
  • 2.推论：若p是素数，a是正整数且不能被p整除，则：a^p mod p = a mod p

3. 朴素算法

求: M ^ E % N. 时间复杂度: O(E).

原理: M ^ E % N = (M % N) ^ E % N

def modularpower(m, e, n):
    ''' m ^ e % n
    '''
    res = 1
    for i in range(e):
        res = (res * m) % n
    return res

4. 蒙哥马利算法

求: M ^ E % N. 时间复杂度: O(log2(E)).

参考: CSDN 幂取模算法

def modularpower(m, e, n):
    ''' m ^ e % n
    '''
    res = 1
    m = m % n
    # convert to binary string, and reverse
    base_str = bin(e)[2:][::-1]
    for i in base_str:
        if i == '1':
            res = (res * m) % n
        m = (m * m) % n
    return res

5. 欧几里得算法(辗转相除法)

辗转相除法是用来计算两个整数的最大公约数。假设两个整数为a和b，他们的公约数可以表示为gcd(a,b)。如果gcd(a,b) = c,则必然 a = mc 和 b = nc。a除以b得商和余数，余数r可以表示为r = a - bk，k这里是系数。因为c为 (a,b) 的最大公约数，所以c也一定 (b, r) 的最大公约数，因为r = mc - nck = (m-nk)c。

因此gcd(a,b) = gcd(b,r)，相当于把较大的一个整数用一个较小的余数替换了，这样不断地迭代，直到余数为0，则找到最大公约数。

举例两个整数为1071和462：

  • 第一步：1071 / 462 = 2 * 462 + 147
  • 第二步：462 / 147 = 3 * 147 + 21
  • 第三步：147 / 21 = 7 * 21 + 0

此时余数为零，则21为两个数的最大公约数。

贝祖公式表明对于任意两个整数a和b，都可以找到一对可为负的整数x和y，可以使等式xa + yb = m，其中m为a和b的最大公约数。如果m为1说明a和b互素。所以在互素的情况下，xa + yb = 1。这个等式对于求乘法逆元有很大的帮助。

那么如何通过贝祖公式及扩展欧几里得算法来求乘法逆元呢？举一个例子来描述什么是乘法逆元。如果ab mod m = 1，或者可以表示为ab ≡ 1 mod m，这里b就是a关于模数m的乘法逆元。计算乘法逆元的方法就是扩展欧几里得算法，以下通过一个例子来帮助理解：

假设我们要求3 关于模26的乘法逆元(隐含了3和26的最大公约数为1，即互素)。当a = 3，b = 26，则根据贝祖公式，存在整数x和y，3x + 26y = 1。

思路就是等号两边同时mod 26，等式则变成(3x + 26y) mod 26 = 1 mod 26，根据模运算的性质(a + b) mod m = (a mod m + b mod m) mod m。

所以展开等式(3x mod 26 + 26y mod 26) mod 26 = 1 mod 26。化简最终得到(3x mod 26) mod 26 = 1 mod 26。我们发现3x mod 26 = 1正好符合了乘法逆元的定义，所以欧几里得算法就是解x的关键。

下面将通过辗转相除法来求x：

  • 第一步：26 = 3 * 8 + 2
  • 第二步：3 = 2 * 1 + 1

统一将余数换到等号左边：

  • 2 = 26 - 3 * 8
  • 1 = 3 - 2 * 1

将第一行的2替换到第二行，保证等式左边永远为1，等式右边变成仅由3x + 26y组成。 1 = 3 - (26 - 3 * 8) * 1 = 3 * 9 + (-1) * 26

可得x = 9. 最后9就是3关于模26的乘法逆元。

它可以应用于仿射加密。

  • 仿射加密的公式e(x) = ax + b mod m， 其中a与m互素， b为移动距离。
  • 仿射解密公式d(x) = a-1(x - b) mod m

results matching ""

    No results matching ""