ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門　3.14〜3.15

暗号 Python

暗号理論入門 原書第3版

暗号理論入門 原書第3版

3.14 元の位数の計算

|G| の任意の素因数 p に対して、f(p) は g^{|G|/p^{f(p)}} = 1 である最大の整数とする。このとき
　 \displaystyle order\ g = \prod_{p||G|} p^{e(p) - f(p)}
である。

例．G はmodulo 101の既約剰余群とする。その位数は 100 = 2^{2} * 5^{2} であり、 e(2) = e(5) = 2 となる。
2 + 101 \mathbb{Z} を計算する。 2^{2*5^{2}} \equiv 2^{50} \equiv -1 mod\ 101 が成立する。 したがって f(2) = 0 である。

2^{2^{2}\ *5} \equiv 2^{20} \equiv -6 mod\ 101 が成立し、 f(5) = 0 となる。
よって100は 2 + 101 \mathbb{Z} の位数である。

n \in \mathbb{N} とし、 g^{n} = 1 と g^{n/p} \ne 1 とが n の任意の素因数 p に対して成立するとき、n は g の位数である。

3.15 中国人の剰余定理

m_1,\ ...,\ m_n を互いに素な自然数とし、 a_1,\ ...,\ a_n は整数とする。次の連立合同式
　 x \equiv a_1 mod\ m_1,\ \ \ x \equiv a_2 mod\ m_2,\ \ \ ...,\ \ \ x \equiv a_n mod\ m_n
を解く。

m = \displaystyle \prod_{i=1}^{n} m_i,\ \ \ M_i = m / m_i,\ \ \ 1 \le i \le n
とおくと、
gcd(m_i, M_i) = 1,\ \ \ 1 \le i \le n
が成立する。

y_i \in \mathbb{Z},\ \ \ a \le i \le n を計算するため、拡張ユークリッドアルゴリズムを使う。

y_i M_i \equiv 1 mod\ M_i,\ \ \ 1 \le i \le n
とおくと、
\displaystyle x = ( \sum_{i=1}^{n} a_i y_i M_i) mod\ m
となる。

例．連立合同式
　 x \equiv 2 mod\ 4,\ \ \ x \equiv 1mod\ 3,\ \ \ x \equiv 0 mod\ 5
を解く。
m_1 = 4,\ \ \ m_2 = 3,\ \ \ m_3 = 5,\ \ \ a_1 = 2,\ \ \ a_2 = 1,\ \ \ a_3 = 0 である。
このとき、 m = 60,\ \ \ M_1 = 60/4 = 15,\ \ \ M_2 = 60/3 = 20,\ \ \ M_3 = 60/5 = 12 である。

y_1 M_1 = 1 mod\ m_1、すなわち -y_1 \equiv 1 mod\ 4 を解くと、絶対値最小の解は y_1 = -1 である。
y_2 M_2 = 1 mod\ m_2、すなわち -y_2 \equiv 1 mod\ 3 を解くと、絶対値最小の解は y_2 = -1 である。 y_3 M_3 = 1 mod\ m_3、すなわち 2y_3 \equiv 1 mod\ 5 を解くと、絶対値最小の解は y_3 = 3 である。
よって x \equiv -2 * 15 - 20 \equiv 10 mod\ 60 となる。

pythonで実装してみる。

def xeuclid(a, b):
    """ return gcd(a,b), x and y in 'gcd(a,b) = ax + by'.
    """
    x = [1, 0]
    y = [0, 1]
    sign = 1

    while b:
        q, r = divmod(a, b)
        a, b = b, r
        x[1], x[0] = q*x[1] + x[0], x[1]
        y[1], y[0] = q*y[1] + y[0], y[1]
        sign = -sign

    x = sign * x[0]
    y = -sign * y[0]
    return a, x, y


def chinese_remainder(a, m):
    """ return x in ' x = a mod m'.
    """
    modulus = reduce(lambda a,b: a*b, m)

    multipliers = []
    for m_i in m:
        M = modulus / m_i
        gcd, inverse, y = xeuclid(M, m_i)
        multipliers.append(inverse * M % modulus)

    result = 0
    for multi, a_i in zip(multipliers, a):
        result = (result + multi * a_i) % modulus
    return result

例の連立合同式を解いてみる。

>>> a = [2, 1, 0]
>>> m = [4, 3, 5]
>>> chinese_remainder(a, m)
10

連立合同式をこの方法で解くには、時間 O( (size\ m)^{2}) と 格納領域 O(size\ m) が必要となる。