異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
数論アルゴリズム入門
横田 壽 1
1
芝浦工業大学 December 22, 2014
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
基数
n を (dk−1 dk−2 . . . d1 d0 )b のように表すとき，b を基数という．ま
た，d はディジット (桁) といい，0 から b − 1 の間の整数である．
この表記法は
n = dk−1 b k−1 + dk−2 b k−2 + · · · + d1 b + d0
を意味している．
例題
(11001001)2 を求めよ．
解 (11001001)2 = 1 ∗ 27 + 1 ∗ 26 + 1 ∗ 23 + 1 ∗ 20 = 201
例題
b = 26 のとき，数字の 0∼25 がそれぞれ A∼Z を表すとする．こ
のとき，(BAD)26 を求めよ．また，(B.AD)26 を求めよ．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
解 (BAD)26 = 1 ∗ 262 + 0 ∗ 26 + 3 = 679
例題
7 進法で 160 と 199 の乗算を行え．
解 160 = (316)7 , 199 = (403)7 より，
3 1 6
4 0 3
1 2 5 4
1 6 0 3 0
1 6 1 5 5 4
例題
(11001001)2 を (100111)2 で割れ，また (HAPPY) を SAD) で
割れ．
110
解答 (1001001)2 ÷ (100111)2 = 101 100111
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
例題
106 を 2 進数，7 進数, 26 進数に変換せよ．
解答 106 ÷ 2 = 0 より，最下位桁の数字が求まる．またその商
500000 を 2 で割ると最後から 2 番目の桁の数が求まる．以下同様
に繰り返すと，106 = (11110100001001000000)2
NOTE b k−1 ≤ n < b k を満たす整数 n は，b を基数として k 桁を
持つ．対数の定義より，
log n
桁の数 = [logb n] + 1 = [
]+1
log b
NOTE 数 n を 2 進数で表すとき，桁数をビット長という．
例題
次の演算を行え．
1 1 0 1 0 1 1
+ 1 0 1 1 0 1 1
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
解 この演算を行うには，次のステップを 7 回繰り返す．
1. 上下のビット数を調べる．また上のビットの上に繰り上がりが
あるか調べる．
2. 両方のビットが 0 で繰り上がりもない場合，0 を記入し次の桁
へ移動
3. 両方のビットが 0 で繰り上がりがある場合，もしくは片方の
ビットが 0 で他方が１，かつ繰り上がりがない場合は，1 を記入
し次の桁へ移動
4. 片方のビットが 0 で他方が 1，かつ繰り上がりがある場合，も
しくは両方のビットが 1 で繰り上がりがない場合は，0 を記入し
次の桁に繰り上がりをしてから移動する．
5. 両方のビットが 1 で繰り上がりがある場合，1 を記入し次の桁
に繰り上がりをしてから移動する．
この手続きを 1 回行うことをビット演算という．これより，2 つ
の k ビットの数の加算には k ビット演算が要求される．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
O 記法.
.
関数 f : Z+ → Z+ を整関数という．
f (n) と g (n) が n ≥ n0 で f (n) < Cg (n) となる定数 C が存在
するとき，f (n) = O(g (n)) と表す．
g (n) として用いる関数は，f (n) より簡単な関数で，f (n) より
あまり早く増加しない関数を用いる．
例題 √2n2 + 3n + 4 を O 記法で表すと 2n2 + 3n + 4 = O(n2 )
問 n n + n3 + 2n を O 記法で表せ．
f (n)
問 lim
= 定数 ならば，f (n) = O(g (n)) が成り立つこ
n→∞ g (n)
とを示せ．
f (n)
= 0 のとき，f (n) = ◦(g (n)) と表す．
n→∞ g (n)
f (n)
= 1 のとき，f (n) ≍ g (n) と表す．
lim
n→∞ g (n)
lim
素数定理 π(n) ≍
n
log n .
π(n) は n 以下の素数の個数を表す．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
Ω 記法
f = Ω(g ) は g = O(f ) を意味する．
f = Θ(g ) は f = O(g ) と f = Ω(g ) を意味する．
これらの記号は数式の中より数式の内側で用いられることが
多い．
関数が nO(log log n) であるということは，n ≥ n0 に対して，関
数が ≤ nC log log n となる定数 C が存在することを意味する．
問
1. ε が任意の正の数のとき，log n = ◦(nε ) と表せることを示せ．
2. 全次数が高々n の x, y , z の単項式の数を最良の評価となる式で
与えよ．
3. 最初の n 個の正整数の平方の和
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
数の長さ
整数の長さ (length) はその整数を 2 進数で表したときのビッ
トの数を意味する．
length(n) = 1 + [log2 n]
であり，これは O(log n) で評価できることに注意
例題 次の操作によって求められる長さを求めよ．
それぞれの長さが高々k の n 個の正整数を
1
2
加え合わせる
掛け合わせる
解答
2 つの数の和は，大きい方の数の長さか大きい数の長さ＋１
であることに注意する．それぞれの長さが高々k ということ
より，それぞれの数は 2k より小さいことがわかる．よって，
n 個の数の和は n2k より小さいことから，その長さは高々
k + length(n) となる．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
長さ k の数 m は 2k−1 ≤ m ≤ 2k を満たす．すると，m1 が長さ k
をもち，m2 が長さ k をもつなら，２つの不等式
2k−1 ≤ m1 < 2k
2k−1 ≤ m1 < 2k
を掛けて，22k−2 ≤ m1 m2 < 22k を得る．これから length(m1 m2 )
は m1 と m2 の長さの和，または m1 と m2 の長さの和-1 に等しい．
これより，n 個の積は
2nk−n ≤ Πmi < 2nk
したがって，長さは nk − (n − 1) と nk の間である．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
数の長さ
問
n! の長さを求めよ．
解答 n! を構成している n 個の数はすべて length(n) より長
い長さを持たないことに注意する．
n = Πmi とすると，mi < 2length(n) を満たす．したがって，
n! = Πmi < 2nlength(n)
これより，n! の長さは n(length(n)) 以下である．したがって，
length(n!) ≤ nlength(n) = O(n log n)
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
演習問題
次の各々の場合，指示した数の長さを評価せよ．答えは O 記
法で表せ．
それぞれの長さが高々k である n 個の数の和
n4 + 25n2 + 40
n の k 次多項式 ak nk + ak−1 nk−1 + · · · + a1 n + a0 ．ただし，k
と ai は定数
ビット数が k 以下の全ての素数の積
(n2 )!
n 番目の Fibonacci 数
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ランドウの O 記法
Ω 記法
演習問題
n 番目の Fibonacci 数の長さと漸近的に等しいような関数
g (n) を見出せ．
Stiring の公式を使い，n! の長さと漸近的に等しいような関数
g (n) を見出せ．
文字 A, B, C . . . . , Z が 26 進文字として使われているとする．
このとき
(CAT )
(DOG )26 26
の２進数での長さは，ほぼ次のどれに等しいか．
50, 150, 500, 1500, 5000, 15000, 50000, 150000, 500000, 1500000
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
ビット演算
数 n を 2 進数で表すとき，length(n) をビット長という．
問 次の演算を行え．
1 1 0 1 0 1 1
+ 1 0 1 1 0 1 1
一桁ごとの演算をビット演算という．
2 つの数を足すのに必要な時間（ビット演算の数) は２つの
数の長さの最大値に等しい．
Times(k ビット + ℓビット) = max(k, ℓ)
2 つの数 m と n で表すときは，
Times(m + n) = max(log m, log n)
問 次の演算を行え．
1 1 0 1 0 1 1
× 1 0 1 1 0 1 1
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
ビット演算
k ビットの整数に ℓ ビットの整数をかけることを考える．
1 1 1 0 1
×
1 1 0 1
1 1 1 0 1
1 1 1 0 1 0
1 1 1 0 1
1 0 1 1 1 1 0 0 0
高々ℓ 個の行を得る．ここで，各行はある数だけ左にシフト
しただけである．シフトはビット演算ではなく管理上の手続
きとして数えられるので，時間評価では無視されることに注
意する．その結果，各行の足し算は k 個のビット演算しか要
しない．したがって，ビット演算の総数は
(ℓ個の加算) × (加算あたり k 個のビット演算) = kℓ
より少ない．Times(m × n) = O(log m log n)
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
ビット演算
(11001001)2 を (100111)2 で割ることを考える．
1 0 1
1 0 0 1 1 1 ) 1 1 0 0 1 0 0 1
1 0 0 1 1 1
1 0 1 1 0 1
1 0 0 1 1 1
1 1 0
k > l とするとき，k ビット整数を ℓ ビット整数で割った時の
時間評価を求める． 商と余りを得るには最大で k − l + 1 回の減算が必要である．
そして各減算は，ℓ ビット演算を必要とする．したがって，
時間評価は (k − ℓ + 1)ℓ ≤ kℓ
k ビットを ℓビットで割るのにかかる時間 ≤ kl
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
アルゴリズム
計算をするために明示的な段階的手続は，アルゴリズムとよ
ばれる．
徐算は乗算と同じように解析でき，k ビット整数を ℓ ビット
整数で割るとき，商と余りを得るには O(ℓ(k − l + 1)) 個の
ビット演算を要する.
課題
k ビット整数 n を基数 10 の表現に変換するのに要する時間を
評価せよ．
n! を計算するのに要する時間を評価せよ．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
除算
課題解答
k ビット整数を 10 進表現に変換することを考える．まず，k
ビット整数を n とし，n を 10 = (1010)2 で割る.
n = 10q1 + r1
q1 = 10q2 + r2
q2 = 10q3 + r3
..
.
この結果，割り算は [log10 n] + 1 = O(k) 回必要で，1 回の割
り算で減算を O(4k) 回行う必要がある．したがって，ビット
演算数の合計は O(k 2 ) = O(log2 n) となる．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
アルゴリズム
例題 k ビット整数 n を b 進数表現に変換するのに必要な
時間を評価する．
解答 n を ℓ ビット整数 b で割る.
割り算は [logb n] + 1 = O(log2 n/ log2 b) = O(k/ℓ) 回必要で，
1 回の割り算で減算を O(ℓk) 回行う必要がある．したがって，
ビット演算数の合計は O(k 2 ) = O(log2 n) となる．
n! を計算するのに必要な時間を評価せよ．
解答 2 · 3 · · · k − 1 と k をかけるのに必要なビット演算を考え
る．(k − 1)! を k にかけるには，(k − 1)! の値を求めるため
に，k − 2 回の掛け算を必要とする．つまり最悪 n 回の掛け
算を必要とする．次に，(k − 1)! を 2 進数で表すのに，
length(n!) = O(n log n) の演算が必要である．そこで，
(k − 1)! と k をかけるには O((k − 1)!k) 回．つまり，
O(n log n × log n) = O(n log2 n) の演算が必要となる．これを
k = 1 から k = n まで行うので，演算数の合計は
O(n2 log2 n)
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
演習問題
O 記法をつかって，3n を 2 進で計算するのに必要なビット演
算の数を n の簡単な関数で評価せよ．
同じことを nn について行え．
N n を計算するのに必要なビット演算の数を n と N の簡単な
関数で評価せよ．
次の２進数
101101110010111000111
の正確な値を計算するのに必要なビット演算数は，ほぼ次の
どれに等しいか．
100, 1000, 10000, 100000, 106 , 101 0, 102 5, 107 5
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
Euclid
例題 2 つの整数 a > b > 0 が与えられるとき，a と b の最
大公約数 d を計算することと，方程式
au + bv = d
を整数 u と v について解くことは，ともに時間 O(log a log b)
でできる．
解答 ユークリッドアルゴリズムより
a = q0 b + r1
0 < r1 < b
b = q1 r1 + r2
..
.
0 < r2 < r1
rl−1 = ql rl + rl+1
rl
0 < rl+1 < rl
= ql+1 rl+1
これより，d = rl+1 を得る．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
最大公約数
逆向きに戻ると，
d
= rℓ+1 = rℓ−1 − qℓ rℓ
= vℓ rℓ + uℓ−1 rℓ−1
vℓ = qℓ , uℓ−1 = 1
= vℓ−1 rℓ−1 + uℓ−2 rℓ−2
..
.
vl−1 = uℓ−1 − qℓ−1 vℓ , uℓ−2 vℓ
= v1 r1 + u0 b
= vb + ua
除算 a = q0 b + r1 のビット演算数が高々length(b) · length(q0 ) で
あることを用いる．すると，すべての除算の総時間は
O(log b(log q0 + log q1 + · · · log qℓ+1 )) = O((log b)(log Πqi ))
である．しかし，Πqi ≤ a であるから，限界は O(log b log a) で
ある．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
合同式
定義
3 つの整数 a, b および m が与えられているときに，差 a − b が m
で割り切れるならば，
「m を法として，a は b と合同である」とい
い，a ≡ b mod m と表す．
課題
ax ≡ 1 (modm)
は |a| < m および gcd(a, m) = 1 として，x について時間
O((log m)2 ) で解けることを示せ．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
定理
数 a が ab ≡ 1 mod m となる b を持つことと，gcd(a, m) = 1 とな
ることは同値である．
例題
160−1 mod 841 を求めよ．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
Fermat の小定理
定理
素数 p を考える．任意の整数 a に対して，ap ≡ a mod p が成り立
つ．また，(a, p) = 1 のとき，ap−1 ≡ 1 mod p が成り立つ．
例題
7 を基数として，21000000 の最後の桁の値を求めよ．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
繰り返し２乗法を用いた法ベキ乗計算
定理
m は k ビットの自然数，N は ℓ ビットの自然数，そして |b| < m
とする．m を法とする b N の最小非負剰余を，時間 O(k 2 ℓ) で見出
す方法を示せ．
問
n5 − n は常に 30 で割り切れることを証明せよ．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
多項式時間から指数時間まで
多項式時間
2 進数で表された全長が高々k の整数について，そのアルゴリ
ズムを実行するのに必要なビット演算数が O(k d ) となる整数
d が存在する．
通常の算術演算 +, −, ×, ÷ は，多項式時間アルゴリズム
指数時間
2 進数で表された全長が高々k の整数について，そのアルゴリ
ズムを実行するのに必要なビット演算数が O(e ck ) の形の時間
評価をもつ．ただし，c は定数である．ここで，k は整数の 2
進数としての全長である．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
ビット演算
アルゴリズム
多項式時間から指数時間まで
多項式時間から指数時間まで
整数 n を素因数分解するとき，2, 3, 4, 5, 6 . . . で割っていく
と，このアルゴリズムは時間 O(n1/2+ε ) かかる．これより，
k d = n1/2+ε とおくと，k ≈ log2 n となり，指数時間となる．
多項式時間と指数時間の間の領域で分類する有用な方法を紹
介する．
定義
γ を 0 と 1 の間の実数，c > 0 とする．このとき，
γ (log log n)1−γ
Ln (γ; c) = O(e c(log n)
)
と定める．
Ln (1; c) = O(e c log n ) = O(nc ),
Ln (0; c) = O(e c log log n ) = O((log n)c )
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
素因数分解
問
8091 を素因数分解せよ．
解：(Carl Pomerance)
8051 = 8100 − 49 = 902 − 72
= (90 − 7)(90 + 7) = 83 · 97
これより，n の素因数分解には
x2 − n = y2
となる x, y を探せばよい．つまり，n = 8051 の時には，
x = 90, 90 ± 1, 90 ± 2, . . . として，Q(x) = x 2 − n が平方数になる
ものを探す．この方法を Fermat の平方差法という．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
2 次ふるい法
M. Kraitchik は Fermat 法を改良し，n|x 2 − y 2 = (x + y )(x − y ) を
満たす n の因数を見つける方法を考え出した．もし，n - x + y ま
たは n - x − y ならば，gcd(x − y , n) > 1 となる．ここで，ユーク
リッドアルゴリズムを用いて gcd(n, x − y ) を求めると，n の自明
でない因数が求まる．
632 − n = 32 = 25
642 − n = 159 = 3 · 53
n = 3937 の場合について考える． 652 − n = 288 = 25 · 32
662 − n = 419 = 419
672 − n = 552 = 23 · 3 · 23
これより，(63 · 65)2 ≡ (25 · 3)2 mod n を得るので，
gcd(63 · 65 − 25 · 3, 3937) をユークリッドアルゴリズムで求めると
31 となる．したがって，
3937 = 31 · 127
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
プロジェクト
因数分解の方法はここで紹介したもの以外に，連分数法と数
体アルゴリズムが知られている．
連分数法について調べ発表を行う．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
クラス P,NP, および NP 完全
クラス P（Polynomial) に属するとは，ある問題が多項式時間
のアルゴリズムを持つときである．
クラス NP(Non-deterministic Polynomial) に属するとは，あ
る決定問題が非決定性多項式時間のアルゴリズムを持つとき
である．
未解決問題 クラス P = クラス NP
クラス NP 完全（NP-complete) 問題とは，NP に属する問題
のうち，解くのが最も難しいものをいう．NP のすべての問
題から多項式時間帰着可能な問題
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
暗号
Alice 重要な文書を送る人
Bob 重要な文書を受け取る人
Alice が重要な文書をインターネットを介して Bob に送る．
このとき，Alice の文書は 26 進数の数字に変換された後 10 進
数で表される．したがって，送るのは数字の羅列である．
Alice が送った数字の羅列を傍受したものは，26 進数表示の
アルファベットに戻すことで Alice の送った文書の中身を知
ることができる．
ここでどうすれば途中で盗聴されても中身を知られないで済
むかを考える．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
秘諾方法
ステガノグラフィー データ隠蔽技術の一つ．在原業平「からころもきつつなれに
しつましあればはるばるきぬるたびをしぞおもう」
画像に著作権者などを埋め込む電子透かし (digital watermark)
コード 単語やフレーズを事前に決めておいた言葉・記号で
置き換える．
サイファ 通信文を意味とは関係なく，事前に決めたアルゴ
リズムにしたがって，文字やビットごとに置換や転置をおこ
なうことで，読めない文に変換する．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
共有鍵暗号
Alice と Bob はこっそり会って，お互いしか知らない秘密鍵
(secret key) となる数字を決める．
Alice から Bob に重要な文書を送るとき，平文（plaintext) を
この秘密鍵を使って暗号文 (ciphertext) に暗号化する，
文書を受け取った Bob は秘密鍵を用いて，暗号文を平文に
戻す．
この方法の問題点をあげ，どうすれば改良できるか考えよ．
．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
公開鍵暗号
Diffie と Hellman は１９７５年に，鍵を２つ用意することを
考えた．１つは，公開鍵とよばれ誰でも見ることができるも
の，もう一つは秘密鍵である．ここで，重要なことは秘密鍵
があれば公開鍵が作れるが，公開鍵があっても秘密鍵は容易
に作れないことである．
Bob は秘密鍵から作った公開鍵をインターネット上に公開し
ておく．
Alice は Bob の公開鍵を用いて，平文を暗号文に変換し送る．
暗号文を受け取った Bob は秘密鍵を使って復号化し，暗号文
を平文に直す．
Eve が盗聴に成功したとしても，公開鍵から秘密鍵は簡単に
作れないので，秘密情報は守れる．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
RSA 暗号
2 つの大きな素数を用意する．ここでは例なので素数を
p = 43, q = 53 とする．
ここで，n = 43 × 53 = 2279 を公開鍵とする．
(p-1) と (q-1) の積を計算する．L = 42*52 = 2184
L=2184 と互いに素で L より小さい任意の整数 e を選ぶ．こ
こでは e = 101 を選び公開鍵とする．
次に，e × d ≡ 1 mod L となる正の整数 d を計算する．これ
が秘密鍵となる．
d は 2184 を法とする e = 101 の逆元より，Euclid の互除法を
用いると，d = 173 となる．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
暗号化・復号化
平文 cat を暗号化することを考える．
cat を 26 進表示で表すと 2,0,19 これを 10 進数に直すと
2 × 262 + 0 + 19 × 260 = 1371
1371 を公開鍵 101 と 2279 を使って暗号化すると，
1371101 ≡ 1520 (mod 2279)
となり，1520 が暗号文となる．
次に 1520 を復号化するには秘密鍵 d = 173 を用いて，
1520173 mod 2279 を計算すればよい．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
期末課題
平文・暗号文に用いるアルファベットを 40 文字とする．
A − Z は 0 − 25 に対応し，空白 = 26, . = 27, ? = 28, $ = 29
とし，数字 0 − 9 は 30 − 39 に対応する．また，平文は２文
字組で，暗号文は３文字組で表す (k = 2, l = 3 とし，n は
402 < n < 403 の範囲とする）．
RSA 暗号プログラムを改良し， “SEND $7500” というメッ
セージを，暗号化鍵 (n, e) = (2047, 179) を持つ相手に送信
せよ.
n を因数分解し，復号化鍵 (n, d) を求めて，この暗号を破れ.
n を因数分解しなくても，手早く復号化鍵を求めることがで
きることを説明せよ.
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
離散対数暗号
RSA 暗号は，おおきな２つの素数を生成しそれらを掛け合わ
すことで n を生成することが，n から２つの素数をもとめる
よりもずっと簡単であるという事実を基礎とすることを前節
で述べた．” 落とし戸” や” 一方向” といった性質をもつもの
が，数論の他の基本的な計算処理にも存在する．そこで，こ
こでは有限体におけるベキ乗計算を考える．
定義 G を有限群，b と b のベキ乗である y を G の要素と
すると，b に対する y の離散対数とは，b x = y であるような
任意の整数 x のことである．
例 G = F∗19 = (Z/19Z)∗ とし，b を生成元 2 とすると，底
２に対する 7 の離散対数は 6 である．
２が生成元とは，2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10,1
のように，F19 のすべての元を生成するからである．そして，
26 = 64 = 7(mod19)
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
離散対数暗号
例 2 X 2 − X − 1 の根 α を F∗9 で考えると，底 α に対する −1
の離散対数は 4 である．
まず，F9 は F32 より，p = 3 は F9 の標数である．つまり，
1 + 1 + 1 = 0 になる．次に，α を X 2 − X − 1 の根とすると，
α2 = α + 1
α3 = α2 + α = 2α + 1 = −α + 1
α4 = −α2 + α = −1
したがって，α4 = −1 となり，α に対する −1 の離散対数は
4 である．
離散対数問題とは，b x は高速に計算できるが，b x = y の b
と y が与えられているとき，どのように x を高速に求めるか
である．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
Diffie-Hellman 鍵交換システム
大きな有限体 Fq の中からランダムに要素を生成する
Diffie-Hellman 法を紹介する．
q は公開され，すべての人が，鍵がどの有限体に属している
のか知っていると仮定する．Fq の要素 g を固定し，これも
公開する.
A(Aida) と B(Bernardo) が F∗q の乱数である鍵に合意し，それ
を用いて平文を暗号化するものとする．
Aida は１から q − 1 の範囲で秘密の乱数 a を選び，g a ∈ Fq
を計算し公開する．
Bernardo も同じように乱数 b を選び，g b ∈ Fq を計算し公開
する．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
Diffie-Hellman 予想
g a と g b だけしか知らないなら，g ab を求めるのは計算上困
難である．
離散対数が計算可能ならば，g a と g b より，a, b が求まる．し
たがって，g ab も求まり，Diffie-Hellman 予想は成り立たない．
この逆も成り立つと予想する人もいるが，これはまだ未解決
問題である．つまり，a と b を求めずに，g a と g b から直接
g ab を求める方法をだれも思いつかないということである．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
Visual C# 入門
どんな手段でもよいから Visual C#が使える状態にする．
Visual C#を起動し，Form アプリケーションを開く．
ツールボックスから label, textbox, button を取り出し次の
フォームを作成する．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
Properties
(name)
Form1
lable1
lable2
txtbox1
txtbox2
btnTrans
BackColor
LigthSteelBlue
LigthSteelBlue
LigthSteelBlue
Window
Window
DarkRed
Font
9pt
14pt
14pt
14pt
14pt
14pt
H. Yokota
Location
0,0
44,33
44,71
142,33
142,71
302,33
Size
424,196
47,19
86,19
119,26
119,26
94,35
Algorithmic Number Theory
Text
初めての暗号化
平文
10 進表示
数値化
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
イベント Driven
1
”btnTrans”をダブルクリックし，実際にボタンを押したとき
にやらせたいことを書く．
2
string plainText = txtbox1.Text; // plainText を文字列である
と宣言し，画面上のテキストボックスに入力された文字列を
取り込む．
3
文字列を 10 進数に変換
unicode において小文字の a は 97 に変換される．
cat の c は 99 に変換され，26 の 2 乗をかける．
文字列は配列として扱える．str[0] ← c, str[1] ← a, str[2] ←
t
str[0] には 99 という数字が格納される.
262 は Math.Pow(a,b) を用いる．Math.Pow(a,b) は ab を表
し，型は double 2 × 262 + 0 + 19 × 260 の値
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
1
// 1 文字のアスキーコードは plainText[0] で取り出せ，a の
アスキーコードは 97 である．この情報を用いると，平文の 1
文字を 10 進数に変換ができる．つまり，(plainText[0]-97) で
a が 0 に変換され，さらに
(plainText[0]-97)*Math.Pow(26,plainText.Length-k-1) で，10
進数になる．
2
for ループを用いて書くと，
3
double val = 0.0;
4
for(int k=0;k < plainText.Lenght;k++)
{
val += (plainText[k]
-97)*Math.Pow(26,plainText.Length-k-1); }
txtbox2.Text = val.ToString();
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
実行
このプログラムを実行するには，ソリューションのビルド F6 ボ
タンをクリックする．ここでエラーがなければ，F5 ボタンをク
リックし実行する．うまくいくと次の画面が表示される．”cat”と
打ち込み，数値化ボタンをクリックすると，1371 が表示される．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
メソッド
1
先ほどのループを含む部分を新たにメソッドを用意して記述
する．
2
private double numberTransform(string str)
{
double val = 0.0;
for(int k=0;k < str.Lenght;k++)
{
val += (str[k]
-97)*Math.Pow(26,str.Length-k-1); }
return val }
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
最後に，btnTrans 以下を次のように書き換える．
private void btnTransform Click(object sender, EventArgs e)
{
string plainText = txtbox1.Text;
txtbox2.Text =
numberTransform(plainText).ToString();
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
最大公約数
1
まず，次のようなインターフェイスを作成する．
2
テキストボックス txtboxInput
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
2 つの数字の取り出し方
1
2
3
4
5
6
最大公約数を求めたい 2 つの数字を入力する．このとき，ど
のようにすれば取り出しやすいか考える．
日常の生活で 2 つの数字を書くときには，間にスペースやカ
ンマを入れる．そこで，スペースを入れた場合について考
える．
例えば，248 128 と 2 つの数字が入力されたとする．このと
き，C#には，入力された文字列をスペースで 2 つの配列に
分ける方法がある．それが，Split コマンドである．
string[] st = txtboxInput.Text.Split(’ ’);
これで，st[0] には文字列としての 248 が st[1] には文字列と
しての 128 が入る．
そこで，数字としての 248 を取り出すため，int.Parse(st[0])
とする．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
1
int a = int.Parse(st[0]);
2
int b = int.Parse(st[1]); により，a,b は整数型として扱うこと
ができる．
3
そこで，a=248,b=128 の最大公約数を Euclid の互助法を用
いて求めるためのアルゴリズムを考える．
4
a = q1 b + r1 を満たす q1 と r1 を求めることになる．このと
き q1 は a/b で求まる．また，
r1 = a − q1 b = a − (a/b)b = a%b で求まる．
5
次に，b=128 と r1 = 120 の最大公約数は,b = q2 r1 + r2 を満
たす q2 と r2 を求める．同様に，r1 = q3 r2 + r3 を満たす q3 と
r3 を求める．つまり，gcd(248,128) = gcd(128,120) =
gcd(r1 , r2 ) = (r2 , r3 ) = · · · = gcd(ri , ri+1 ) = · · · = gcd(rk , 0)
= rk
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
プログラム
1
2
ri+2 = ri %ri+1 を繰り返し，ri+2 が 0 になったときの ri が最
大公約数であることに気付くと，
private int gcd(int a, int b)
{
int[] r = new int[10];
int r[0] = a;
int r[1] = b;
int i = 0;
while(r[i+1] > 0)
{
r[i+2] = r[i] % r[i+1];
i++;
}
return r[i];
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
1
gcd(int a, int b) を呼び出すために，計算ボタンを押したら次
のメソッドを用意する．
2
private void euclid Click(object sender, EventArgs e)
{
string[] st = txtboxInput.Text.Split(’ ’);
int a = int.Parse(st[0]);
int b = int.Parse(st[1]);
txtboxOutput.Text = gcd(a, b).ToString();
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
再帰処理
1
2
3
4
c#では，再帰を使ってプログラムを書くことができる．例
えば，
sum(n) = 1 + 2 + 3 + · · · + n-1 + n とおくと，
sum(n) = sum(n-1) + n と表せる．これより
int sum(int n)
{
if(n==1)
return 1;
else
{
return sum(n-1) + n;
}
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
再帰処理
1
private int gcd(int a, int b)
{
if (a == 0)
{
return b;
}
else
{
int result = exgcd(b % a, a);
return result;
}
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
期末課題
平文・暗号文に用いるアルファベットを 40 文字とする．
A − Z は 0 − 25 に対応し，空白 = 26, . = 27, ? = 28, $ = 29
とし，数字 0 − 9 は 30 − 39 に対応する．また，平文は 2 文字
組で，暗号文は 3 文字組で表す (k = 2, l = 3 とし，n は
402 < n < 403 の範囲とする）．
RSA 暗号プログラムを改良し， “SEND $7500” というメッ
セージを，暗号化鍵 (n, e) = (2047, 179) を持つ相手に送信
せよ.
n を因数分解し，復号化鍵 (n, d) を求めて，この暗号を破れ.
n を因数分解しなくても，手早く復号化鍵を求めることがで
きることを説明せよ.
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
平文と暗号文の文章単位の集合は，各ユーザ間で異なるが，
現実では同じになるように選ぶ．たとえば，N 文字のアル
ファベットにおけるシステムを考える．
k < ℓ はお互いの正の整数で，N k と N l がそれぞれ 10 進数で
約 200 桁であるように選ぶものとする．
平文は k 文字のブロックで，つまり N 進数 k 桁の整数として
考える．つまり，0 から nk の間の同義数と対応させる．
同様に，暗号文を ell 文字のブロックで表す．
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
期末課題
1
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
1
private void btnEncryption Click(object sender, EventArgs e)
{
try
{
plainPair = Int32.Parse(txtboxPair.Text);
cryptPair = Int32.Parse(txtboxCrypt.Text);
plainText = txtboxPlainText.Text;
plainNumber = strToint(plainPair, plainText);
txtboxValue.Text = plainNumber.ToString();
}
catch (Exception ex)
{
ex.Message.ToString();
}
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
btnCipher
1
private void btnCipher Click(object sender, EventArgs e)
{
string[] key = txtboxKey.Text.Split(’,’);
int length = key.Length;
string[] equiv = txtboxValue.Text.Split(’,’);
int len = equiv.Length;
string cip = ””;
for (int j = 0; j < len; j++) // 同義数ごとに暗号化
をする
{
cip += cipher(equiv[j], key[0], key[1], cryptPair);
}
txtboxCipherText.Text = cip; // 暗号文を表示
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
strToint
1
private string strToint(int pair, string st)
{
int length = st.Length; // st は平文
string equiv = ””; // 同義数を equiv とする．
int j = 0;
double henkan = 0.0;
int[] s = new int[length];
int k = 0;
while (j < length)
{
if (char.IsLetter(st[j]))
{
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
cipher
1
private string cipher(string equiv, string st0, string st1, int
num)
{ int pubkey = int.Parse(st0); // 公開鍵のベース 2047
int power = int.Parse(st1); // 公開鍵作成用の累乗 179
int len = equiv.Length; // 同義数の文字数
long r = 1;
string[] cr = new string[12];
string res = ””;
for (int i = 0; i < power; i++)
{ r = r * (int.Parse(equiv));
r = r % pubkey;
}
res = crypt(r);
return res;
}
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
crypt
1
private string crypt(long r)
{
int k = 0;
while (j < 3) // 3 文字組
{
k = j % 3;
fl = r / Int32.Parse(Math.Pow(40, 2 k).ToString());
t[j] = int.Parse(fl.ToString());
rem = r % Math.Pow(40, 2 - k);
r = long.Parse(rem.ToString());
if (t[j] >= 0 && t[j] <= 25) c[j] = (char)(t[j] +
65);
H. Yokota
Algorithmic Number Theory
異なる基数系の数
計算量
時間評価
素因数分解
公開鍵暗号
btnDecrypt
1
private void btnDecrypt Click(object sender, EventArgs e)
{
string st = txtboxCipherText.Text;
int length = st.Length;
int[] s = new int[length];
double henkan = 0.0;
string dec = ””;
while(j < length)
{
if (char.IsLetter(st[j]))
{
if (char.IsLower(st[j])) { };
else s[j] = st[j] - 65;
}
H. Yokota
Algorithmic Number Theory

コール酸摂取ラットにおける脂肪肝の発症と腸内細菌叢変動との関連性

巡回セールスマン問題

数論アルゴリズム

ｽﾗｲﾄﾞ ﾀｲﾄﾙなし

アトラスシリコン半導体飛跡検出器：ATLAS Silicon

加藤 晃史

ジェロトランセンデンス理論

マヨラナのニュートリノ系での CPの破れの探求

2006年度 今井研演習Ⅲ課題説明会

断眠実験によるサーカディアンリズムの変動がパフォーマンスに及ぼす