GolangでMiller-Rabin素数判定法を実装してみる
背景
Wikipedia
にも記載されていますが、
Miller-Rabin素数判定法は
与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種で、乱択アルゴリズムです。
フェルマーテストでは、以下のフェルマーの小定理を用いて
素数判定を行いますが、カーマイケル数と呼ばれる合成数を、誤って(素数と)判定してしまいます。
例えば、最小のカーマイケル数は561ですが、のため、素数ではありません。
フェルマーの小定理
素数
と互いに素となる整数
に対して
が成り立つ。
フェルマーテストを改良したのがMiller-Rabin素数判定法です。
詳細はWikipediaを参照頂ければと思いますが、与えられた素数を奇素数(素数判定をしたいのは、大きい整数なので、奇素数を考えれば目的は十分に果たせます)と考え、
と表現します。ここで
は正整数で、
は奇数です。すると式(1)は以下のように書けます。
が素数であれば、式(2)を満たします。左辺を
とみて、式(2)について単位元の平方根を考えます。
非自明な平方根は存在しない(証明もWikipediaにあります)ので以下の2式のみを考えればよいことになります。
ここで、です。
上記は、自明な平方根
または
となった場合を考えて、
となった場合は、さらに繰り返し(平方根が
となるまで)平方根を考えていった結果を表しています。式(3)は
にならず、平方根が取れなくなるまで取ったあとの結果になります。
あとはフェルマーテストと同様に考えて、与えられた数が素数でない(合成数である)のであれば、式(3)および式(4)を満たさないとして、素数判定を行います。
フェルマーテストと同様に偽陽性(素数と判定したのに実は合成数だった)の可能性は残りますが、フェルマーテストより確率は低いようです。
実装
gist1cd38a67c96df7966b9c468927dc2757
結果
今回は以下の4パターンを判定してみました。
- 1から100までに含まれる素数
- 1から合成数(奇整数のみ)
- 以前作った合成数(16329805957987392833 = 7508269669 * 2174909357)
- 素数生成機により生成した500桁の素数
結果は以下の通り、いずれも正しく判定できています。
$ go run MillerRabinPrimalityTest.go ------------Prime------------- 2 : true 3 : true 5 : true 7 : true 11 : true 13 : true 17 : true 19 : true 23 : true 29 : true 31 : true 37 : true 41 : true 43 : true 47 : true 53 : true 59 : true 61 : true 67 : true 71 : true 73 : true 79 : true 83 : true 89 : true 97 : true ------------Composite------------- 9 : false 15 : false 21 : false 25 : false 27 : false 33 : false 35 : false 39 : false 45 : false 49 : false 51 : false 55 : false 57 : false 63 : false 65 : false 69 : false 75 : false 77 : false 81 : false 85 : false 87 : false 91 : false 93 : false 95 : false 99 : false 16329805957987392833 : false 75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 : true
今回はをランダムに選ぶ回数
kをk=20としましたが、精度を上げるにはこの値を増やすことが有効です。逆にk=1などとしてみると以下のように結構間違えます。もちろん乱択アルゴリズムなので何度もやるとミスがあったりなかったりですが。
$ go run MillerRabinPrimalityTest.go ------------Prime------------- 2 : true 3 : true 5 : true 7 : true 11 : true 13 : true 17 : true 19 : true 23 : true 29 : true 31 : true 37 : true 41 : true 43 : true 47 : true 53 : true 59 : true 61 : true 67 : true 71 : true 73 : true 79 : true 83 : true 89 : true 97 : true ------------Composite------------- 9 : false 15 : false 21 : false 25 : false 27 : true 33 : false 35 : false 39 : true 45 : false 49 : false 51 : false 55 : false 57 : false 63 : false 65 : false 69 : false 75 : false 77 : false 81 : false 85 : false 87 : false 91 : true 93 : false 95 : false 99 : false 16329805957987392833 : false 75367631466941141791247084978233913478587466161271622771710895906453753967164967411257954571043148038883968051384064219878882200013408641715083492640764339527637873502061727098279950196988248939994544197535642414553039637030217247486372549770605212095298947963579455290328750806815560590656493190626063424483777638146122548073605596393468295558919015322872295712049815793564477203891171966598995001945926910413702372501638140065699147590309176011776418089018393636130620122226631715476290375904684033 : true
Reference
Atomでconfig.fishをハイライトさせる
zshからfishに移行している最中にconfig.fishがAtomでハイライトされていなかったのでさせました。
単純に拡張子とscope nameを対応させるだけですが、fishを検索ワードにしてると意外と引っかからなかったのでメモ書きとしてまとめておきます。
事前準備(file-typesのインストール)
Atomを開き、cmd + ,でPreferenceを開きます。
Installからfile-typesパッケージを検索し、インストールします。
config.csonの編集
以下のように設定します。
恐らく$HOME/.atom/config.csonにあるかと思います。
"*":
"file-types":
fish: "source.shell"
上記編集後、保存すれば設定が反映されます。
Reference
GolangでCuckoo Hashingを実装してみた
2017/5/27 修正
int64型であるkeyを[]byte型へconvertする際にhasher.Write([]byte(string(key)))ではうまくいかないため以下のように修正しました。
b := make([]byte, 8) binary.LittleEndian.PutUint64(b, uint64(key)) hasher.Write(b)
背景
BloomFilterを実装した後に、やろうやろうと思っていたCuckoo Hashingを実装してみました。
Cuckoo Hashing自体の説明は
@_krzさんの記事がわかりやすいです。絵を交えられているのでイメージもつきやすいです。
メリットとしてはlookupが定数時間(2回比較するだけ)で完了することが挙げられます。
またアルゴリズム自体がわかりやすいです。2つのテーブルを用意しておき、挿入したいkeyのハッシュ値を計算し、ハッシュ値をindexとみて、テーブルが空いていれば挿入。すでに埋まっていれば、keyと既に入っていた値を交換して、もう一つのテーブルで同様の操作を繰り返すという流れになっています。カッコーの托卵のようですね。
デメリットは、ハッシュの衝突が起こった場合やループが無限ループに入る恐れがあります。今回の実装でもMAXLOOPを設定することで無限ループを防いでいます。
また、こちらによるとテーブルの半分が埋まった段階で性能が落ちてしまうそうです。
実装
gistaaf77c63f3668efdd44e2f4ae9642f76
今回は0を空とする実装にしましたが、実際には0を挿入したい場合も多いと思うので、その場合はうまくゼロ値を使うなどするのがよいと思います。
References
Golangで有向グラフをかく
背景
言語処理100本ノック 2015をやっている最中に、有向グラフで表示する問題(Q44)に遭遇しました。 gographvizでDOT言語のdotファイルを作成し、graphvizで可視化したのでまとめます。
動作環境
# sw_vers ProductName: Mac OS X ProductVersion: 10.11.6 BuildVersion: 15G31 # go version go version go1.8 darwin/amd64 # dot -V dot - graphviz version 2.40.1 (20161225.0304)
インストール
graphvizのインストール
# brew install graphviz
gographviz packageのインストール
# go get github.com/awalterschulze/gographviz
有向グラフの作成
設定値などはGraphvizとdot言語でグラフを描く方法のまとめを参考にさせて頂きました。
gist4c915c1e14aae064a92cc30fbcb5eac7
dotファイル上で、Attributionにダブルクオーテーションが必要な場合は、エスケープしないとsyntaxエラーになるので注意してください。
また、今回のように事前のテストができる場合は問題ないですが、Attrを動的に設定するような場合は、以下のようにエラーチェックをしたほうがよいでしょう。
// 例) colorschemeを設定する場合
if _, err := gographviz.NewAttr("colorscheme"); err != nil {
panic(err)
}
nodeAttrs["colorscheme"] = "rdylgn11" // 問題ないことを確認してからmapに格納する
出力のdotファイルは以下のようになります。
gistc0bdfb47ec6948b6bed5cd51ad92f05c
有向グラフの出力
噂のGraphvizを使ってみるにもありますが、上記で出力したdotファイルをもとに、pngファイルとして結果を出力させるには以下のようにします。
# dot -T png diGraph.dot -o diGraph.png
結果です。いい感じですね。
Reference
Golangで言語処理100本ノック2015 第4章: 形態素解析
言語処理100本ノック 2015の第4章: 形態素解析の10問です。
前処理
mecabの処理は先に済ませておきます。
# mecab neko.txt -o neko.txt.mecab
30. 形態素解析結果の読み込み
形態素解析結果（neko.txt.mecab）を読み込むプログラムを実装せよ．ただし，各形態素は表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をキーとするマッピング型に格納し，1文を形態素（マッピング型）のリストとして表現せよ．第4章の残りの問題では，ここで作ったプログラムを活用せよ．
gistc6be3f30935d9f1032cb8dd29b3a6f8e
# go run q30.go [map[base: pos:記号 pos1:空白 surface: ] map[pos:名詞 pos1:代名詞 surface:吾輩 base:吾輩] map[pos1:係助詞 surface:は base:は pos:助詞] map[base:猫 pos:名詞 pos1:一般 surface:猫] map[pos:助動詞 pos1:* surface:で base:だ] map[pos1:* surface:ある base:ある pos:助動詞] map[surface:。 base:。 pos:記号 pos1:句点]]
mecabの結果は形態素ごとに一行で出力されるのでReadLine()で読み取っています。
例として「 吾輩は猫である。」を表示させています。
31. 動詞
動詞の表層形をすべて抽出せよ．
gist0230b9eddcac1d6541935856342866ba
# go run q31.go [生れ つか し] [死な 得 られ]
Q30をそのまま利用すれば余裕です。結果が長くなるので最初と最後の3つだけ標準出力させました。
32. 動詞の原形
動詞の原形をすべて抽出せよ．
gist015db5a66878a77df992821b075ab8b5
# go run q32.go [生れる つく する] [死ぬ 得る られる]
Q31とほぼ同じです。
33. サ変名詞
サ変接続の名詞をすべて抽出せよ．
gistc2c9fe26605d803583db6ee4b26f6f00
# go run q33.go [見当 記憶 話] [抵抗 見当 判然]
こちらもQ31とほぼ同じです。
34. 「AのB」
2つの名詞が「の」で連結されている名詞句を抽出せよ．
gist120cb467e3a271b9bfbd55af9ca1b868
$ go run q34.go [彼の掌 掌の上 書生の顔] [水の中 座敷の上 不可思議の太平]
「の」が出てきた前後が名詞になるものを抜き出しています。
気をつけるのはindex out of rangeのruntime errorを出さないことでしょうか。
35. 名詞の連接
名詞の連接（連続して出現する名詞）を最長一致で抽出せよ．
gistf15b4cadbae765b94f4abf99b771ae39
# go run q35.go [吾輩 猫 名前] [太平 太平 南無阿弥陀仏南無阿弥陀仏]
名詞が続く間はループ回しています。 標準出力させながらコード書いてましたが、意外なもの(非自立や接尾の名詞)が出力され、間違っているのでは？と微妙にハマりました。そもそも国語力というか日本語の弱さが問題です。。。
36. 単語の出現頻度
文章中に出現する単語とその出現頻度を求め，出現頻度の高い順に並べよ．
gistc5f254f78da7fd7774c6513726607a71
# go run q36.go の 9194 。 7486 て 6848 、 6772 は 6420 に 6243 を 6071 だ 5975 と 5508 が 5337
mapは順序を保存してくれないので、擬似的なTreeMapとしてsortedMap型を用意しました。ほぼこちらを参考にしました。
上位10個を抜き出してみましたが、固有名詞がないですね。。。
37. 頻度上位10語
出現頻度が高い10語とその出現頻度をグラフ（例えば棒グラフなど）で表示せよ．
gist5f74bc0a182cfa616d5f270037ac4d17
実行結果
gonum/plotが日本語サポートしていないのでX軸にどの単語だが、表示されないのが微妙ですね。。。出力しているのはQ36と同じですが。 棒グラフの書き方は以前記事にまとめました。
38. ヒストグラム
単語の出現頻度のヒストグラム（横軸に出現頻度，縦軸に出現頻度をとる単語の種類数を棒グラフで表したもの）を描け．
gistc2bdc1b97162a49e390991bd454d45c5
実行結果
英語だとちゃんと軸名が表示されます笑 題意の単語が何を指しているのか戸惑って、問題文理解するのに時間掛かりました。。。
39. Zipfの法則
単語の出現頻度順位を横軸，その出現頻度を縦軸として，両対数グラフをプロットせよ．
gista037ce443bd2066f6061ce91a8167630
実行結果
Q38を流用するとすぐですね。
感想
言語処理をやったことがなかったので、そもそもの用語を知らなくて戸惑うことが多かったです。このまま5章の係り受け解析も頑張ります。
いつも通りコードはGithubにも置いてあります。
Reference
Golangのmath/bigでIntを直接入力したい
背景
Golangの基本型であるint64ではのため20桁程度(※)でoverflowを起こします。そのため、
math/bigパッケージのNewIntを使おうとするとoverflowのコンパイルエラーになります。
※正確には、符号付き64bit整数の最大値9223372036854775807(ギリギリ19桁)を超えるとoverflowします。
例えば、20桁の数16329805957987392833で試してみると、以下のようにconstant 16329805957987392833 overflows int64のコンパイルエラーとなります。
package main
import (
"fmt"
"math/big"
)
func main() {
n := big.NewInt(16329805957987392833) // constant 16329805957987392833 overflows int64
fmt.Println(n)
}
int64の最大値を超えるような大きな数をbig.Int型として扱いたいときは以下のようにすれば直接入力可能です。
package main
import (
"fmt"
"math/big"
)
const (
DECIMAL int = 10
)
func main() {
n, _ := new(big.Int).SetString("16329805957987392833", DECIMAL)
fmt.Println(n)
}
使った素数について
素数生成機をお借りして10桁の素数を2つ(7508269669,2174909357)生成し、積を計算したのが16329805957987392833です。
Reference
DH鍵交換でもWiresharkでSSL/TLSを復号化したい
WiresharkでSSL通信の中身を覗いてみる
を拝見し、実際に自分の手を動かしてみたのですが、記事内でも触れられているようにDiffie-Hellman(DH) key exchange
(および楕円曲線を用いたECDH)
では、実際に鍵を送り合うわけではなく、鍵を生成するためのパラメータだけがやり取りされるので、サーバの秘密鍵を持っていても復号できません。
今回はDH鍵交換(以下、DHE)でもWiresharkでSSL/TLSを復号すべく試行錯誤したので、まとめます。
事前の設定内容
VirtualBoxで以下のゲストOSやApacheを立ち上げておきます。
$ cat /etc/redhat-release CentOS Linux release 7.2.1511 (Core) $ httpd -v Server version: Apache/2.4.6 (CentOS) Server built: Nov 14 2016 18:04:44 $ rpm -aq | grep mod_ssl mod_ssl-2.4.6-45.el7.centos.x86_64 $ openssl version OpenSSL 1.0.1e-fips 11 Feb 2013
ホストOSとゲストOSのIPは、それぞれ以下のようにアサインしました。
| ホストOS | ゲストOS |
|---|---|
| 192.168.10.100 | 192.168.10.104 |
オレオレ証明書はCentOS に Apache HTTPD を導入して SSL を有効にする を参考に作成し、証明書と秘密鍵は以下の名前でssl.confに記載しています。
# サーバ証明書 SSLCertificateFile /etc/httpd/conf/server.crt # サーバ秘密鍵 SSLCertificateKeyFile /etc/httpd/conf/server.key
(参考)DHEを無効にする
参考までにサーバ側とクライアント側でDHEを無効にすることでSSL/TLS通信を復号する方法も記載します。 この方法ではサーバの秘密鍵があれば、SSL/TLS通信を復号することができます。サーバの秘密鍵を外へ出したくないということであれば(むしろ出すべきでないと思いますが)、session keyのみをexportすることでも復号できます。 セッションキーをエクスポートし、秘密鍵を共有することなくWireshark でSSL/TLS 通信を複合 に両方のやり方がありますので、興味がある方はぜひ。
サーバ側でDHEを無効にする
WiresharkでSSL通信の中身を覗いてみる にも記載がありますが、ssl.confで以下のように設定すればOKです。
SSLCipherSuite kRSA
設定後はservice httpd restartでApacheを再起動しておきます。
この状態でhttpsの通信を発生させ、Server Helloに含まれるcipher suiteを見ると
Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)となっており、DHEもECDHEも使われていないことがわかります。
※ssl.confの設定を戻すことをお忘れなく
クライアント側でDHEを無効にする(Firefox)
Firefoxを立ち上げ、アドレスバーにabout:configと打ち込みます。
dheで検索し、DHEおよびECDHEを含むcipher suitesを無効化(false)にします。
以下の太字の箇所が変更箇所です(一番上以外)。
この状態でhttpsの通信を発生させ、Server Helloに含まれるcipher suiteを見ると
Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)となっており、サーバ側でDHEとECDHEを無効化したときと同じですね。
※Firefoxの設定を戻すことをお忘れなく
本題
さて、DHEを無効化せずにWiresharkで復号化したいですね。
復号化するにはサーバの秘密鍵ではなく、session keyを入手する必要があります。
まずはホストOSでsession keyをexport先を指定してFirefoxを起動します。
ここではpremaster.txtにexportさせます。
※Firefoxは閉じた状態で実行しないと怒られます。
$ SLKEYLOGFILE=/YOURPATH/TO/premaster.txt "/Applications/Firefox.app/Contents/MacOS/firefox-bin"
上記を実行すると、いつも通りFirefoxが起動するので、httpsの通信を発生させます。
するとpremaster.txtには以下のようにsession keyが書き込まれているはずです。
$ cat premaster.txt # SSL/TLS secrets log file, generated by NSS CLIENT_RANDOM xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
※実際にはxが16進数で表示されるはずです。
この時点では以下のように復号化できていないです。
復号するためには、Wiresharkでpremaster.txtからsession keyを読むように指定してあげます。
指定方法は、WiresharkのPreferenceからProtocols→SSL→(Pre)-Master-Secret log filenameでpremaster.txtを指定します。
※特にサーバの秘密鍵などは指定する必要ありません。
OKを押下すると以下のようにhttpのパケットが復号できます。
このときのServer Helloに含まれるcipher suiteを見ると
Cipher Suite: TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (0xc02f)となっており、ECDHEでも復号化できていることがわかります。
