Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« 2010年2月 | トップページ | 2010年5月 »

2010年4月

2010-04-21

Ruby はじめました

Ruby はじめました。



数年前(5年以上も前)に勉強しようと思ったことがあって、
本は何冊か買ってあったのですが、ずっと積読されていて
たぶんコードは一度も書いたことはなかったハズ。

で、Twitter 向けサービスを新たに作るのに、
せっかくだから Ruby で作ってみようかな、
とか思ったわけです。
# どうも Perl は好きになれないので・・・(とくにオブジェクト指向まわり)


まずは積んであった本を読みました。

この本は改版されてるのですが、家にあったのは初版。 Appendix で「Ruby 1.8 の変更点」とかあるくらい古いですが、 まぁ、基本的なところは変わっていないと信じて読みました。 いや、思っていた以上にいい内容でした。特に1.5章。 他の言語(Perl とか C とか)を知っているひとが まさに陥りそうな罠について指摘してくれています。 たとえば、真偽値の扱い(「0」は真)とか。 この先もしばらくお世話になりそうです。 で、続けて、処理系をインストール。 cygwin の最新パッケージだと ruby-1.8.7 なのですが、 せっかくなので 1.9 系を使ってみたいなぁ、というわけで、 ソースコードからビルドしてみました。 と言っても、Ruby の本家サイトから tarball を落として展開して、
% ./configure --prefix=/opt/ruby-1.9.1 --enable-shared
% make
% make install
であっさり。 make の途中で「Tk が pthread 対応じゃないよ」と言われますが、 たぶん Tk を使うことはないので無視(ぉ あとは ~/.bashrc とかで PATH と LD_LIBRARY_PATH を設定して終わり。 無事に ruby 1.9.1 (p378) が使えるようになりました(たぶん)。 ためしにちょっとした Twitter API クライアントを書いて 練習してみようかと思いますー

2010-04-17

Apple の戦略

すごくいい記事を見つけたので、ご紹介。

    アップルはなぜ Objective-C にこだわるのか
    << maclalala2

先日の iPhone OS 4.0 SDK の発表以来、Adobe (Flash) の排除とか
開発者の囲い込みとかいう議論を巻き起こしている Apple ですが、
その裏にはこんな戦略があるのでは、という話です。

たしかに Apple は過去に幾度も異なるアーキテクチャへの移行を
成功させてきました。モトローラの 68k から PowerPC、そして
現在の Intel x86 への移行は、いずれも大きな混乱を招くことなく、
むしろ Mac の価値を高める結果になっています。Mac のように
膨大な数の開発者を抱えるプラットホームの移行がこれほどスムーズに
成功し続けている例は他に知りません。

Apple がアーキテクチャの移行を成功させ続けている理由のひとつとして、
非常に高度なエミュレーション技術を持っている点が挙げられると思います。
たとえば、Mac OS X (Cocoa) への移行に際しては、旧来の Mac OS の
アプリケーションをそのまま実行可能な Classic 環境を提供しています。
また、かつての 68k から PowerPC への移行においても、Mac OS (System 7) に
従来の 68k コードを動的に変換して実行する機構を搭載し、PowerPC への
スムーズな移行を実現しています。今回の iPad (iPhone OS 4.0) に関しても
同様の技術を用いている可能性は十分にあると思われます。

そして、今回紹介した記事でもっともインパクトのあった一文がこれ:

基本的にアップルは、CPU をコモディティーとして扱い、 そのことによって「自社製造か購入か」という戦略を自由に選べ、 サプライヤーに対しては強力な支配力を行使し、長期的には 自らのプラットフォームに後光を与えることが可能になるのだ。
この戦略は、おそらく、現在の Wintel 連合に対する 強力なアドバンテージになると思われます。 たしかに Intel の CPU は PC 業界を支配していますが、 スマートフォンや組み込みデバイスの世界では違います。 まだ立ち上がっていない(iPad が火付け役になるかもしれない) タブレットの分野にいたっては、まったく白紙の状態です。 もし、タブレットやスマートフォンにとって最適なアーキテクチャが Intel x86 ではなく、さらに現在存在する開発リソースをそのまま (あるいは最小限の労力で)その「最適なプラットホーム」に 移行させる技術を Apple だけが提供できるとしたら・・・ 10年後の IT 業界の勢力地図が今とは一変している可能性も 決してゼロではありません。 ところで、Apple にひとつお願いがあります。 iPhone OS SDK の Windows 版がほしいです。 iPhone はすごくほしいし、アプリも作ってみたいのですが、 そのためだけに Mac を買うのは財政的につらいものがあります。 アプリが作れないというだけの理由で Android を買ってしまいそうです。 まぁ、いずれにしても今年の夏までは様子見ですけどね。

2010-04-13

RSA 暗号

多倍長計算の高速化にトライしようと思ったのですが、
その応用のひとつである RSA 暗号について調べていたら、
いつのまにかハマってしまいましたw

    ⇒ RSA暗号  --  Wikipedia

素数判定コードで(確率的)素数を生成してみたので、
それを使ってみよう、という話です。

ポイントは「拡張されたユークリッドの互除法」です。

    ⇒ ユークリッドの互除法  --  Wikipedia

「d×e + χ×φ = 1」の「d」を求める計算なのですが、
最初は係数の計算方法がぜんぜん理解できなくて、
紙に式変形を書いてみてようやくコードに起こせました。

その上、コードを書いてみると「χ」じゃなくて「d」が
負になってしまって、これを補正する方法が分からず
しばらく悩みました。

「d」が求まれば、暗号化&復号化は bmodpow() で一発です。

できたコードが↓

#!/usr/bin/perl -w ############################################################################## # RSA crypt sample ############################################################################## use strict; use warnings; use Math::BigInt lib => 'GMP'; use Math::Random::MT qw(srand rand); #============================================================================= sub rand32 { return (int(rand(0x10000)) << 16) | (int(rand(0x10000))); } sub rand_inf { my $arg = shift; if (ref($arg)) { # object of Math::BigInt my $x = substr($arg->as_hex(), 2); # 先頭の "0x" は削っておく my $ntimes = int((length($x) / 8)); my $y = '0x'; if (length($x) % 8 != 0) { my $limit = hex(substr($x, 0, length($x)-8*$ntimes)); $y .= sprintf("%x", rand32() % $limit); } for (my $i =0; $i < $ntimes; $i++) { $y .= sprintf("%08x", rand32()); } return Math::BigInt->new($y); } else { return int(rand($arg)); } } #============================================================================= sub gcd { my $m = shift; my $n = shift; $m = Math::BigInt->new($m) unless (ref($m)); $n = Math::BigInt->new($n) unless (ref($n)); if ($m->bcmp($n) < 0) { # swap my $k = $m; $m = $n; $n = $k; } while (! $n->is_zero()) { my $r = $m->copy()->bmod($n); $m = $n; $n = $r; } return $m; } sub gcd_ext { # 「拡張されたユークリッドの互除法」 by Wikipedia my $m0 = shift; my $n0 = shift; $m0 = Math::BigInt->new($m0) unless (ref($m0)); $n0 = Math::BigInt->new($n0) unless (ref($n0)); my $m = $m0; my $n = $n0; my @a = (Math::BigInt->new('0'), Math::BigInt->new('1')); my @b = (Math::BigInt->new('1'), Math::BigInt->new('0')); # die if ($m->bcmp($n) < 0); while (! $n->is_one()) { my ($q, $r) = $m->copy()->bdiv($n); die if ($r->is_zero()); # 入力は互いに素のハズ unshift(@a, $a[1] - $q * $a[0]); unshift(@b, $b[1] - $q * $b[0]); $m = $n; $n = $r; } if ($a[0] < 0) { $a[0] += $n0; $b[0] -= $m0; } die if ($a[0]->is_neg()); return +($a[0], $b[0]); } #============================================================================= { # 4096bit probable prime number my $p = Math::BigInt->new('★素数その1★'); my $q = Math::BigInt->new('★素数その2★'); my $n = $p * $q; my $e = 65537; # =2^16+1 my @coeff = gcd_ext($e, ($p-1)*($q-1)); print $coeff[0]->as_hex() . "\t" . $coeff[1]->as_hex() . "\n"; # 検算 print +($coeff[0] * $e + $coeff[1] * ($p-1)*($q-1))->as_hex() . "\n"; print +(($coeff[0] * $e)->copy()->bmod(($p-1)*($q-1)))->as_hex() . "\n"; my $d = $coeff[0]; # RSA 暗号の動作確認 my $max = Math::BigInt->new('0x1' . ('0' x (512 / 4))); foreach my $i (1..1024) { local $| = 1; print sprintf("%10d ", $i); print "running..."; my $original = rand_inf($max); print "encoding..."; my $encoded = $original->copy()->bmodpow($e, $n); print "decoding..."; my $decoded = $encoded->copy()->bmodpow($d, $n); print "comparing..."; my $is_ok = ($decoded->bcmp($original) == 0); if ($is_ok) { print "OK\n"; } else { print "ERROR\n"; die; } } } ############################################################################## ##############################################################################
素数を2個与えると、公開鍵を生成して、1024個の乱数に対して 「暗号化⇒復号化⇒比較」をやります。 コードを書いてみて、とりあえず RSA 暗号の基礎が理解できたかんじです。 充実した休日になりました♪

素数判定(その2)

素数判定について調べたのですが、難しさがいまいち実感できなかったので、
ちょろっとコードを書いてみました。

多倍長演算の実装がめんどくさかったので、Perl です。

#!/usr/bin/perl -w

use strict;
use warnings;

use Math::BigInt;
use Math::Random::MT qw(srand rand);

#=============================================================================

sub rand32 {
	return (int(rand(0x10000)) << 16) | (int(rand(0x10000)));
}

sub rand_inf {
	my $arg = shift;
	if (ref($arg)) {
		# object of Math::BigInt
		my $x = substr($arg->as_hex(), 2);  # 先頭の "0x" は削っておく
		my $ntimes = int((length($x) / 8));
		my $y = '0x';
		if (length($x) % 8 != 0) {
			my $limit = hex(substr($x, 0, length($x)-8*$ntimes));
			$y .= sprintf("%x", rand32() % $limit);
		}
		for (my $i =0; $i < $ntimes; $i++) {
			$y .= sprintf("%08x", rand32());
		}
		return Math::BigInt->new($y);
	} else {
		return int(rand($arg));
	}
}

sub is_prime {
	my $n = shift;
	die unless ($n > 1);
	return 1 if ($n == 2);
	return 0 if $n->is_even();

	my $d = $n->copy();
	$d->bdec();
	$d->brsft(1) while $d->is_even();

	my $n1 = $n->copy()->bdec();
	
	foreach my $k (1..20) {
		my $a = rand_inf($n-2) + 1;
		my $t = $d->copy();
		my $y = $a->bmodpow($t, $n);
		while (($t != $n1) and ($y != 1) and ($y != $n1)) {
			$y = $y->bmodpow(2, $n);
			$t->blsft(1);
		}
		if (($y != $n1) and $t->is_even()) {
			print sprintf("%3d", $k);
			return 0;
		}
	}
	return 1;
}

sub get_prime {
	my $bit_length = shift;
	die unless ($bit_length % 4 == 0);
	my $limit = Math::BigInt->new('0x1' . ('0' x ($bit_length / 4)));
	my $count = 0;
	while (1) {
		my $x = rand_inf($limit);
		if (is_prime($x)) {
			print "\n";
			print "OK " . $bit_length . ' ' . $count . ' ' . sprintf("%258s", $x->as_hex()) . "\n";
			return $x;
		}
		$count++;
	}
}

{
	for (my $i=32; $i<=1024; $i*=2) {
		foreach (1..16) {
			print '### ' . time() . ' ' . `/bin/date` . "\n";
			my $value = get_prime($i);
		}
	}
}
実行すると、32bit から 1024bit までの素数を 16個ずつ見つけてくれます。 うちの PC で実行すると、 512bit の素数を1個みつけるのに 3分くらいかかっていました(打ち切ったので 1024bit は不明)。 ちなみに PC のスペックは以下の通り:
    AMD Phenom X4 9750 / 2.4GHz / WindowsXP SP3
    Perl v5.10.0 built for cygwin-thread-multi-64int
ところで、CPAN で "BigInt" で検索すると、 Math::BigInt::GMP とか Math::BigInt::Pari とか なにやら意味ありげなモジュールがみつかります。 GMP というのは GNU で開発している多倍長演算ライブラリらしい。 "GNU Multi-Precision Library" とのこと。 ⇒ GMP -- Wikipedia cygwin なので使えるかわからなかったのですが、 /usr/lib/libgmp.dll.a とかがすでに置いてあったので、 Let's Try! インストールは cpan コマンドで "install Math::BigInt::GMP" で一発。 使うには上記コードの6行目を変えるだけ。超カンタン♪
< use Math::BigInt;
--
> use Math::BigInt lib => 'GMP';
実行してみると、動作速度にびっくり。 512bit の素数が1秒未満で見つかります。1024bit でも数秒。 正直、ここまで速くなるとは思っていませんでした。GMP すごい! さて、これからちょっと高速化にチャレンジしてみようかと思います。 たぶん GMP は超えられないでしょうけど・・・

素数判定

ちょっと気になったので、素数判定について調べてみました。



「素数判定」というのは、ある自然数が素数か否かを判断することです。

    ⇒ 素数判定  --  Wikipedia

原理的には、エラトステネスのふるいとかすれば 100% 確かな答えが得られます。
でも、公開鍵暗号とかで使うような大きな数についてそれをやるのは非現実的。

最近(2002年)になって、多項式オーダの計算時間で素数判定ができるという
すばらしい理論が発表されましたが、多項式の次数が高くて現実には時間がかかる。

    ⇒ AKS素数判定法  --  Wikipedia

というわけで、現実的な解としては、「素数でない数を十分高い確率で弾ける」
アルゴリズムを使ってテストして、そのテストに繰り返しパスした数を
「確率的素数 (probable prime)」として暗号とかに使うことになります。

そのアルゴリズムとしては「ミラー-ラビン素数判定法 (Miller-Rabin
primality test)」というものが有名らしいです。

    ⇒ ミラー-ラビン素数判定法  --  Wikipedia

Wikipedia の記事には Ruby のコード例まで載っています(すばらしい!
数式は理解できなくてもコードなら理解できる(ぉ

また、注目すべき記述もあって、

もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。 もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である。
とのことです。つまり、48bit 以下の整数なら a = 2, 3, 5, 7, 11, 13, 17 の ケースだけ調べれば 100% 確かな判定ができるということですね。すばらしい。 べき乗の高速化についても Wikipedia の記事が参考になります。 ⇒ 冪乗 -- Wikipedia 「上位桁から計算する方式」とか、面白いですねー じつは、この種の計算(多倍長整数の繰り返し乗算)は GPGPU に向いている のではないかと思っているので、もうちょっと調べてみようと思います。

« 2010年2月 | トップページ | 2010年5月 »