Pebble Coding

プログラマーの作業メモ

高速指数計算法アルゴリズム

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

例えば、
 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の冪乗の値は一つ前で計算した値の2乗になっているので、計算量が最小限に抑えられるのである。

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

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

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

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の変数を一つも使っておらずとても綺麗なロジックになる。

curve25519と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}
が得られる。

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)を表します。

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

オイラーの定理

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が素数の場合、2つをかけた合成数 pq に対して \phi(pq) = (p-1)(q-1)が成り立つ。

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

RSAのひ・み・つ - 小人さんの妄想

オイラーのφ関数 - Wikipedia

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

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

edward曲線における加法

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

において、曲線上の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}の順番で並べると、7つほどペアが消える。

 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}が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})を計算すると、5つほどペアが消え、  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}が残る。 あとは自明である。

エドワード曲線とツイストエドワード曲線の形

2007年のエドワードさんの論文(http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf)

から、エドワード曲線と名付けられた


x^{2} + y^{2} = a^{2}(1 + x^{2} y^{2})

がどのような形をしているのか見てみましょう。

まずはa=1.0
 x^{2} + y ^{2} = 1 + x^{2} y^{2}

2本の直線になってしまいました。。

次にa=1.1
 x^{2} + y^{2} = {1.1}^{2}(1 + x^{2} y^{2})

次にa=0.9
 x^{2} + y^{2} = {0.9}^{2}(1 + x^{2} y^{2})

おっと丸くなりました。

次に、ツイストエドワード曲線(http://eprint.iacr.org/2008/013.pdf)


a x^{2} + y^{2} = 1 + d x^{2} y^{2}

をみてみましょう。

a=1, d= -50
 x^{2} + y^{2} = 1 - 50 x^{2} y^{2}

a=-1, d=-50
 - x^{2} + y^{2} = 1 - 50 x^{2} y^{2}

a=-1, d=5
 - x^{2} + y^{2} = 1 + 5 x^{2} y^{2}

 a=-1, d = - 0.7
 - x^{2} + y^{2} = 1 -0.7 x^{2} y^{2}

楕円曲線の形

楕円曲線の一般的な形は以下のように表せます。


y^{2} = x^{3} + ax^{2} + bx + c

暗号理論に用いる楕円曲線は特異でない形のものだけを扱います。
特異でない形のものは2つのパターンに分けられます。
1) yが0の時のxの値が3つある場合
2) yが0の時のxの値が1つだけしかない場合
それぞれの例を挙げます。

1) 
y^{2} = x^{3} + x^{2} - x

これは、左の曲線が閉じているパターンです。

2) 
y^{2} = x^{3} + x^{2} + 1

これは開いているパターン。

このグラフのイメージを掴んでおくと、楕円曲線の理論がとても理解しやすくなります。

a) この曲線上の2つの点を結ぶ直線を引くと、曲線と交わる3番目の点は必ず存在します。
b) xをプラスの無限大に持っていくと、yがプラスの無限大とマイナスの無限大に近づきます。

楕円曲線論入門

楕円曲線論入門

群、体、有限体の定義

群(group)の定義

ある要素の集まりに対して、一つの演算規則 f を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, c を要素とします。

1) 全ての要素に対して、結合法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
2) 全ての要素に対して、単位元が存在する
3) 全ての要素に対して、逆元が存在する

体(field)の定義

ある要素の集まりに対して、加算 f と乗算 g を決め、演算結果はまた要素の集まりの一つになっているとします。
a, b, cを要素とします。
1) 加算について可換群(単位元と逆元が存在する)
2) 乗算について可換群(単位元と逆元が存在する)
3) 加算、乗算について分配法則が成り立つ
f(f(a, b), c) = f(a, f(b, c))
g(f(a, b), c) = g(a, g(b, c))

体の元の数を位数と呼びます。

例1:

整数の集合は体ではありません。
なぜなら 3 を乗算する演算の逆元は 1/3 だが、これは整数ではなく有理数になってしまうから。

例2:

有理数の集合は体です。

有限体

整数の集合に対して、
加算を「整数の加算後に素数pで割った余り」
乗算を「整数の乗算後に素数pで割った余り」と定義した場合、体となります。
つまり、全ての要素に対して逆元が存在します。
元の数は p となります。
この体をF_{p}と書きます。