2017-07-04

高速指数計算(べき乗)アルゴリズム

整数論

ある数の大きなべき数を計算を行う際にできるだけ少ない計算量で行うための方法として、高速指数計算法というものがある。

例えば、
$7 ^ {1281}$
を計算したいとする。ここで
$1281 = 1 + 256 + 1024 = 2 ^ {0} + 2 ^ {8} + 2 ^ {10} = 2 ^ {0} \times 1 + 2 ^ {1} \times 0 + 2 ^ {2} \times 0 + \ldots + 2 ^ {10} \times 1$
のように2の累乗の足し算に分解する。
そして、 $7 ^ {1281} = 7 ^ {1} \times 7 ^ {256} \times 7 ^ {1024}$ を計算する。
この分解をプログラムで行う場合には、順番に値を2で割り算し、その値が奇数であるかどうか判定し、値が0になるまで繰り返せばよい。やってみよう。

0: 1281 -> odd $7 ^ {1}$
1: 640 -> even $7 ^ {2}$
2: 320 -> even $7 ^ {4}$
3: 160 -> even $7 ^ {8}$
4: 80 -> even $7 ^ {16}$
5: 40 -> even $7 ^ {32}$
6: 20 -> even $7 ^ {64}$
7: 10 -> even $7 ^ {128}$
8: 5 -> odd $7 ^ {256}$
9: 2 -> even $7 ^ {512}$
10: 1 -> odd $7 ^ {1024}$
11: 0 -> 終わり

oddの部分の7の冪乗部分の3つを掛け算すれば答えが得られるが、この繰り返し処理の中で、
7の冪乗の値は一つ前で計算した値の２乗になっているので、計算量が最小限に抑えられるのである。

再帰を使わずにswiftで書くとこんな感じになる。

func pow(e:Int) -> Int {
    var b:Int = 7
    var r:Int = 1
    while e > 1 {
        if isOdd(e) { r *= b }
        // 2乗する
        b = b * b
        // 2で割る
        e /= 2
    }
    return r * b
}

再帰を使った場合はこんな感じになる。

func pow(e:Int) -> Int {
    if e == 0 { return 1 }
    let s = pow(e/2)
    // 2乗する
    let r = s * s
    if isOdd(e) {
        return r * 7
    } else {
        return r
    }
}

$pow(1281) = pow(640) ^ {2} \times 7$
$pow(640) = pow(320) ^ {2}$
$pow(320) = pow(160) ^ {2}$
$pow(160) = pow(80) ^ {2}$
$pow(80) = pow(40) ^ {2}$
$pow(40) = pow(20) ^ {2}$
$pow(20) = pow(10) ^ {2}$
$pow(10) = pow(5) ^ {2}$
$pow(5) = pow(2) ^ {2} \times 7$
$pow(2) = pow(1) ^ {2}$
$pow(1) = 7$

再帰を使った場合は見ての通りvarの変数を一つも使っておらずとても綺麗なロジックになる。

2017-06-27

curve25519とed25519の同等性

ed25519

curve25519とは、
$\nu^{2} = \mu^{3} + 486662\mu^{2} + \mu$
のことであり、
ed25519とは、
$x^{2} + y^{2} = 1 +\frac {121665}{121666} x^{2}y^{2}$
のことである。これは単純な変数の置き換えで同等性が示せる。
ただし、ed25519の方が加法定義で場合分けをする必要がなく、扱いやすい。

$d = 486662$ とし、 $\frac {d - 2}{d + 2} = \frac {121665} {121666}$ とする。

$\nu = \sqrt{d} \frac {\mu} {x}$
$\mu = \frac {1+y} {1-y}$
を代入して計算すると、
$(2+d)x^{2} + dy^{2} = d + (d-2)x^{2}y^{2}$
となる。
xを $x \sqrt{ \frac {d}{d+2}}$ で置き換えると。 $x^{2} + y^{2} = 1 + \frac {d-2} {d+2}x^{2}y^{2}$
が得られる。

2017-06-22

RSA暗号の原理を理解するための数学知識

暗号

RSA暗号に関する文章を読んでいてもその数学的な原理がさっぱり理解できなかったのですが、
色々読んでいるうちになんとなく分かってきましたので、メモしておきます。

まずモジュラー演算記号(mod)を覚えましょう。
$a = b \mod n$
これは整数aを整数nで割った余りとbを整数nで割った余りが等しいことを表します。
例:
$9 \mod 4 = 1$
$107 \mod 10 = 7$

モジュラー演算には以下の性質があります。

$a = b \mod n, \\ c = d \mod n$ 　

のとき、

$a + c = b + d \mod n$

$a * c = b * d \mod n$

$a^{m} = b^{m} \mod n$

である。

$ef = eg \mod n$ で gcd(e, n) = 1 ならば
$f = g \mod n$
である。
ここで gcd(a, b) は整数a,bの最大公約数(Greatest Common Divisor)を表します。

合同式の意味とよく使う６つの性質 | 高校数学の美しい物語

オイラーの定理

nが正の整数で、gcd(a, n) = 1 のとき、 $a^{\phi(n)} = 1 \mod n$ である。
$\phi(n)$ は1からnまでの自然数のうちgcd(b, n)=1となる数bの個数を意味する関数とする。

nが素数の場合は、bは1, 2, 3, … , n-1となり、 $\phi(p) = p-1$ となる。

また、p, qが素数の場合、２つをかけた合成数 pq に対して $\phi(pq) = (p-1)(q-1)$ が成り立つ。

RSA暗号の世界 – まいとう情報通信研究会

ＲＳＡのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

中国人剰余定理によりgcd(p, q) = 1のとき、
$m = n \mod p$
$m = n \mod q$
であれば
$m = n \mod pq$ 　　である。

中国剰余定理の証明と例題（二元の場合） | 高校数学の美しい物語

2017-06-19

edward曲線における加法

ed25519

Edward曲線 $x^{2} + y^{2} = a^{2} + a^{2}x^{2}y^{2}$

において、曲線上の２つの点 $(x_{1}, y_{1}), (x_{2}, y_{2})$ の加算後の点を次のように定義する。

$\displaystyle X = \frac {1} {a} \cdot \frac {x_{1} y_{2} + x_{2} y_{1}} {1 + x_{1} x_{2} y_{1} y_{2}}$

$\displaystyle Y = \frac {1} {a} \cdot \frac {y_{1} y_{2} - x_{1} x_{2}} {1 - x_{1} x_{2} y_{1} y_{2}}$

この点は代数計算によって、エドワード曲線上の点になることを確かめることができる。
が、計算は長く厄介なので、計算方法を記しておく。　　

$A = X^{2} + Y^{2} - a^{2}X^{2}Y^{2}$ を計算し、 $a^{2}$ に等しくなることを示す方針で行く。

代入すると $\displaystyle a^{2} A = \frac {1} {(1 + x_{1} x_{2} y_{1} y_{2})^{2}} \cdot \frac {1} {(1 - x_{1} x_{2} y_{1} y_{2})^{2}} \cdot ( \\ (x_{1}y_{2} + x_{2}y_{1})^{2}(1- x_{1}x_{2}y_{1}y_{2})^{2} \\ + (y_{1}y_{2} - x_{1}x_{2})^{2} (1 + x_{1} x_{2} y_{1} y_{2})^{2} \\ - (x_{1}y_{2} + x_{2}y_{1})^{2} (y_{1}y_{2} - x_{1}x_{2})^{2})$

ここで、

$\displaystyle a^{2}A(1 - x_{1}^{2} x_{2}^{2} y_{1}^{2} y_{2}^{2})^{2} = B + C + D$ と置く。

B + C + Dを全て展開し、 $x_{1}, x_{2}, y_{1}, y_{2}$ の順番で並べると、７つほどペアが消える。

$B + C + D = x_{1}^{2}y_{2}^{2} + x_{2}^{2}y_{1}^{2} + x_{1}^{4}x_{2}^{2}y_{1}^{2}y_{2}^{4} + x_{1}^{2}x_{2}^{4}y_{1}^{4}y_{2}^{2} \\ + y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2} - 4 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{2}x_{2}^{2}y_{1}^{4}y_{2}^{4} + x_{1}^{4}x_{2}^{4}y_{1}^{2}y_{2}^{2} \\ - x_{1}^{2}y_{1}^{2}y_{2}^{4} - x_{2}^{2}y_{1}^{4}y_{2}^{2} - x_{1}^{4}x_{2}^{2}y_{2}^{2} - x_{1}^{2}x_{2}^{4}y_{1}^{2} \\ = E_{4} + E_{8} + E_{12}$

ここで $E_{i}$ はx,yの個数を表すが、それぞれ別々に計算してゆくと、 $E_{4}, E_{8}, E_{12}$ には、 $x_{1}^{2} + y_{1}^{2}$ , $x_{2}^{2} + y_{2}^{2}$ が２つ以上出てくるので、 $x_{1}^{2} + y_{1}^{2} = a^{2} ( 1 + x_{1}^2 y_{1}^2)$
$x_{2}^{2} + y_{2}^{2} = a^{2} ( 1 + x_{2}^2 y_{2}^2)$ に置き換える。

ここで、 $\frac {1} {a^{4}} (E_{4} + E_{8} + E_{12})$ を計算すると、５つほどペアが消え、 $1 - 2 x_{1}^{2}x_{2}^{2}y_{1}^{2}y_{2}^{2} + x_{1}^{4}x_{2}^{4}y_{1}^{4}y_{2}^{4}$ が残る。あとは自明である。