6 : 01 ラムダ関数たん…ハァハァ

← 5 - 27 p↑ もくじ i 6 - 02 n →

任意の4つの数を与えてパズルを解く「思考」スクリプト

2002年 6月 2日
記事ID d20602_1

4つの4で遊ぼうよ」から発展して、任意の4つの数に対してパズルを解く JavaScript です。Netscape, Mozilla, IE で動作します。

「4つの4」の初期バージョンは、かなり計算時間がかかりましたが、そのごの高速化で、きわめて軽くなっています。手元の環境では、平均して1秒~10秒程度でパズルを解くことができます。また、初期バージョンはIE専用の「意味論関数」execScriptを使っていましたが、書き直してネスケやモジラでも動作するようになりました。

例題と出力サンプル

7, 10, 25, 46 をこの順序で使って120を作れ。
120 = ∑7 + 10 / √25 × 46 (所要2.875秒)
100, 200, 300, 400を使って61を作る方法は?
61 = √100 + ( ∑200 + 300 ) / 400 (所要2.273秒)
2, 4, 6, 8 を使って10を作る方法は何通り?
総和記号の使い方デフォルトで、「66個、答があったにゅ。Cost 3.876 seconds.
20 = 2 + 4 + 6 + 8
20 = ( 2 + 4 ) + 6 + 8
20 = -( ( 2 - 4 ) × 6 - 8 )
20 = ( 2 + 4 + 6 ) + 8
以下いろいろ表示されてます。なかには同じ意味のものもあります。全部の項の符号を変えて全体をかっこでくくってマイナスを1個または奇数個つける表現は明らかに同じ値になりますが、このような場合は、ひっくるめて1回しかカウントしません。全体にマイナスをつけた形と、各項ごとに符号を反転した形のどちらがリストアップされるかは、決まってません。
7, 7, 7, 7を使って1000を作る
残念ながら答が見つからなかったにょ。」と出力されます。これは「問題が難しすぎて答が(あるけど)分からなかった」のではなく、「定義された表現空間内に解がない」という事実が全数検索によって確定した場合です。unsolved(未解決)でなく、unsolvable(解決不能)です。ある種の方程式における「解なし」などに相当します。
1, 2, 3, 4 をこの順番で使って0~100を作る
0 = 1 - 2 - 3 + 4
1 = -( 1 - 2 × 3 + 4 )
2 = 1 + 2 + 3 - 4
3 = 1 + 2 × 3 - 4
4 = 1 + 2 - 3 + 4
5 = -( 1 × 2 - 3 - 4 )
6 = 1 - 2 + 3 + 4
7 = -( ( 1 - 2 ) × 3 - 4 )
8 = -( 1 - 2 - 3 - 4 )
9 = -( 1 + 2 - 3 × 4 )
10 = 1 + 2 + 3 + 4
以下、76個についての答が数秒で出ました。1, 2, 3, 4のような小さい数を使うと、大きめの数は作れないことが多いです。階乗記号や総和記号の2重使用を許可してないためです。許可してもしなくても技術的には同じことですが、今回は許可してません。
4つの4を使って円周率πを作れ
これは今回の「ぱずら~」とは関係ありません。とんちでもありません。いま書いていて、ふと思いついた問題です。思いついた解は足し算と掛け算と2つの括弧とひとつの……関数を使います。数学の先生に聞いてみよう。

この記事は、すぐ次の「ラムダ関数――夢みつつ目覚めるもの」につづきます。

この記事のURL

テキスト版省パケ版XML版


ラムダ関数――目覚めつつ夢みるもの

2002年 6月 2日
記事ID d20602_2

このメモは直前の「任意の4つの数を与えてパズルを解く「思考」スクリプト」から参照によって話を渡されました。

ラムダ関数――夢みつつ目覚めるもの

「4つの4」の最初のバージョンでは、コードを文字列として生成し、次にそれを「解釈」する、という二段構えを使っていました。これは本質的には、Lispでいうラムダ関数のようなもので、値が関数である変数(関数が代入された変数)、言い換えれば、本質的には、関数(メソッド)を返す関数(つまり超関数)にあたります。JavaScript では関数を文字通りリテラルとして使うこともできますが、さらに関数コンストラクタによって、実行時に動的に何度も何度も自分で自分(の一部)をリコンパイルする、という離れ業が使えます。JavaScriptというと、ブラウザでかんたんな処理を行う簡易言語というイメージがあるかもしれませんが、その深層は意外にも C や Java より柔軟です(まぁ、Cプログラマにとっては、それが厳密でなくて気持ち悪い、という面がありうるのも事実ですが)。

その場で動的にコンパイルされる、というスクリプト言語の本質が、一方においては(実行時間における)弱点であると同時に、他方において、以下で述べるような超柔軟な構造を形成します。Perl における eval も同じことです。実行時にコンパイルされるからこそ、自分で自分を見つめる「コンパイル層」と「記述層」のふたつのレイヤが生じて、それらのあいだでいろいろな「階層のもつれ」をもてあそぶことができ、このような「もつれ」のなかにこそ「意味」や「思考」や「知能」のようなものがひそんでいるのであろう、ということは、広く認識されてます。

// 変数に「解釈すると計算式」になるような文字列を形式的に格納して……
expression = getExpressionEx( op_code, param, param2, n1, n2, n3, n4 );

// それを内容的に解釈して実際に計算する関数を作って……
var lambda = new Function(  "return " + expression + ";" );

// 幻想世界と回線をつなぎ、戻り値を現実世界でいただく
evaluated = lambda( );

最初の代入では、expression は単なる冷たい文字列です。例えば、1+2+3+4 という7つの記号がならんだ模様です――ここでの説明を理解するには、これを「足し算の式だ」と解釈せず、ただの模様だ、と思わなければなりません。実際、これは、JavaScript の文字列として例えばae9gyj#と同じ透明でランダムな存在です。次の lambda には、この模様を戻り値にせよ、という関数が入ります。ラムダは、ふたつの世界を結ぶ役目のかんなぎです。彼女は、この模様を単なる冷たい記号列として受け取りつつ、同時に、この模様の意味を知っています――ないしは、同じことですが、知っているふりができます。彼女が冷たい文字列にくちづけすると、それは、ぽっとふくらんで「意味」をおび、「こたえ」を返すことができるようになります。

ラムダは、1+2+3+4 をまず単なる文字列としてたんたんと読み込み、次の瞬間、それをコンパイルして「10」を「意味」していることを理解します。

3番めの文で、evaluated はラムダ関数が息を吹き込んで作った戻り値をもらいます。

ラムダ関数にとって、このプロセスは、無数に流れるループのなかの一瞬のひとこまにすぎません。

ラムダ関数はプロシージャであると同時に、単なる揮発する一時的な変数であって、ループがまわるたびに違うものが入ります。Functionコンストラクタが一時的に生成するプロシージャへの参照です。参照の入り口はlambdaという決まっためじるし(なまえ)を持っていますが、それが参照する実体は、めまぐるしく変化します。つまり、lambdaは、あるレベルでは、ひとつの変数ですが、lambda というのは誰ですか、何ですか?と尋ねても、lambdaというなまえが指し示している「モノ(世界、関数)」は、1秒に何万回となく変化します。あくまで変数 lambda なのです。関数 getExpressionEx が返す「だれか」(名無しさん)の考え方を一時的に「自分」だと思って、それを忠実に実行し――実際、その時点では、 lambda はその名無しさんと同一なのですが――、実行が終わると、すぐに「自分」を解放して次の名無しさんに「なる」わけです。

言うまでもなく、これは自閉症者のロジックです、が、あなたは、この文を呼んでもこれが何を指しているのかコンパイルできないでしょう。

以上が、Cのようなコンパイル言語よりもダイナミックにコンパイルされるスクリプト言語が柔軟でありうることの説明ですが、これは他方において、巨大ループの1ステップごとにコンパイラが起動され自分で自分を再コンパイルする、という大きな計算コストを意味しています。

2つの世界の通信に特有の問題については、別記事「execScript()が解釈する変数のスコープ」も参考にしてください。

    } else
    if( g_sqrts == 1 ) {
        if( flag[0] )
            N[ g_sqrt_idx[0] ] = "Math.sqrt(" + N[ g_sqrt_idx[0] ] + ")";
    }

    var base = g_sqrts;
    if( g_sigmas == 4 ) {
        if( flag[ base+0 ] )
            N[ g_sorted_idx[0] ] = "Sigma(" + N[ g_sorted_idx[0] ] + ")"; 
        if( flag[ base+1 ] )
            N[ g_sorted_idx[1] ] = "Sigma(" + N[ g_sorted_idx[1] ] + ")"; 
        if( flag[ base+2 ] )
            N[ g_sorted_idx[2] ] = "Sigma(" + N[ g_sorted_idx[2] ] + ")"; 
        if( flag[ base+3 ] )
            N[ g_sorted_idx[3] ] = "Sigma(" + N[ g_sorted_idx[3] ] + ")"; 
    } else

これとはまた別のレベルですが、自分で自分を持ち上げる、という意味では、次のような考えともイメージが近いです。

document.write('<script type="text/javascript">');
document.write('document.write("I know you like the function " + ');
document.write('"<code>document.write()<\/code>, do you?");');
document.write('<\/script>');

この記事のURL

テキスト版省パケ版XML版


Pig PGP なんちゃって暗号

2002年 6月 1日
記事ID d20601

PigPGP は、JavaScript で RSA暗号系を実装する試みです。 おもしろいといえばおもしろいですし、クレイジーといえばクレイジーです。 2004年になって、とうとう本物のPGPと同等の1024ビット強度も実現、 乱数ジェネレーターも Mersenne Twister を搭載するなど、「なんちゃって暗号」と呼ぶにはちょっと本格的になりすぎたかもしれません。 以下はいちばん最初、たった64ビットでも苦労していた時期のメモです。最新版のデモは下記URLにあります。
http://www.faireal.net/demo/PigPGP/

鍵の生成

Mozillaユーザのボブは デモページ を開いて、「鍵生成」をクリックした。1秒程度で64-bit鍵が生成された。

/H/b+9-D+u-e+P+o2=*=-8s+rW2がボブの公開鍵、
/H/b+9-D+u-e+P+o2=*=/n/X-a/r/2-Q/g$がボブの秘密鍵だ。

ボブは公開鍵をホームページで公開する一方、秘密鍵は秘密の場所に保存した。

メッセージの暗号化

アリスはボブに秘密のメッセージを送ることにした。ボブが公開している公開鍵/H/b+9-D+u-e+P+o2=*=-8s+rW2を「公開鍵」欄にペーストしてから、テキスト欄にメッセージをタイプする。

「暗号化」をクリックすると、アリスのメッセージは、ボブにだけ解読可能な形で暗号化された。

以下が出力例である。(注: この暗号系はセッション鍵を使っているため、同じ文章を同じ鍵で暗号化しても、そのつど異なる出力になる。)

-----BEGIN PigPGP MESSAGE-----
Version: PigPGP 0.1.0 by JavaScript

7/y+t/3-r-eO/5j-S+C-T+gB7J+t-v-r-J/I+2/g-l+C/U+gd77J+4+HG/IP/g-V
+C-S+g+67i+t/4-rs/Iqc+x+C/m+gC74+t-s+HJ-Y/wC/W+C-T+gr7/L+t-b-r-P
E/0/g+N+C/i+g17H+t-A+HJ-Y/w9+R-f-2+g07I+t+W-r-a/I+F/g-k+C/5+g@7e
J+4+HG/Io/g-c+C/3+gH76+t-2-r+T/Iq/g-R+C-N+gC+f+U-9/Y-r-O/Is/g-e+
C-J+gd7/$+t-A+HJ-Y/w/g-k+C/J+g-Y7y+t+Y-r+A/I+q/g-d+C-L+g+171J+4+
HG/IP/g+P+C/3+gy7/y+t-l-r+T/I+6/L-3-5B+gGA+q/3/0-r-Ogf/g-l+C/e+g
r78+t-d-r-D/Is-wWS+R+gB7/C+t-d-r-7/Io/g-c+C/3+gD7f-d/a-r+A/Iy/g-
K+C-X+gv77+t-0-r-a/Iq/g-r+C/i+gj7D+t+Y+HJ-Y/wl+c+C-U+gy7/A+t/2-V
/q/IZ0-G+C/3+gX7a+t-A-r+ID$/g+N+C/h+g17H+t/6+HJ-Y/w/g/$+CZ+g-e/m
-JJ+1-r+y/IR/g-5+C/m+gA74+t-n-r-zT/D/g+N+C-$+gA71+t-8-r-0-Y/z-wT
-a+U+O07f-i-f-r+E/I+1/g+N+C-S+g+67-w-7+t-VEl2/g-R
= +z-Z-V-7/f+x+c+o

-----END PigPGP MESSAGE-----

Pig PGPというだけあって、いかにもPGPっぽいが、もちろん互換性はない。

アリスは、この秘密のメッセージを、ボブにメールで送った。メールは盗聴されていたが、だれにも解読できなかった。

暗号解除

さて、ボブはアリスからのメッセージをテキスト欄にペーストし、「秘密鍵」の欄には、自分の公開している公開鍵に対応する秘密鍵
/H/b+9-D+u-e+P+o2=*=/n/X-a/r/2-Q/g$
をペーストした。

「暗号解除」をクリックすると、アリスからのメッセージがあらわれた。

ボブはアリスに返事を書いた。アリスへの返事を暗号化するときには、今度はアリスが公開しているアリスの公開鍵を使う。ボブ自身の鍵では、ない。そして、ボブはアリスの秘密鍵を知らない。このように、やりとりする方向によって異なる鍵を使い、しかも暗号化するときの鍵(受信者の公開鍵)と暗号解除するときの鍵(受信者の秘密鍵)が異なる。「公開鍵暗号は非対称鍵だ、というのは、こういうことなんだなぁ」アリスとボブは、しみじみ実感するのであった。

リンク

この記事のURL

テキスト版省パケ版XML版


100-bit RSA by JavaScript

2002年 5月31日
記事ID d20531

現在は512ビット版を公開していますが、参考までに古い記事も残しておきます。

簡易リファレンス

oKey = new RSA( strength )
暗号強度 strength ビットのRSA鍵オブジェクト oKey を生成して返す。strength の範囲は24以上、100以下。もしくは引数なしで呼び出して、以下のプロパティを明示的に設定することもできる。
oKey.modulus
公開鍵と秘密鍵の両方で使われる法(modulus)をBigint形式で格納。
oKey.publicKey
公開指数。Bigint。
oKey.secretKey
秘密指数。Bigint。
oKey.setKeys( mod, pub, sec )
オブジェクトoKeyに鍵を設定する。引数はBigint、数値、数値を表す文字列のどれでも良く、すべての引数を設定しなくても良い。
oKey.encrypt( message )
oKeyの公開鍵を使って message を暗号化して、結果をBigintオブジェクトで返す。 message はBigint、数値、数値を表す文字列のどれでも受け付ける。
oKey.decrypt( encrypted )
oKeyの秘密鍵を使って、encrypted を暗号解除する。encrypted はBigint、数値、数値を表す文字列のいずれでも良い。戻り値はBigint。

実演

上記のように64ビット鍵は充分に高速に扱えるようになったので、80ビットと100ビットに挑戦してみます。

var oKey = new RSA(80);
_debug( "80ビットの鍵を生成しました: " + oKey );

以下の公開鍵を使って「12345678905555」を暗号化します。
法 1 59451 04683 81864 79200 58494 01711
指数 1 86714 37520 24315

var test = "12345678905555";

var oPubkey = new RSA();

oPubkey.setKeys("1 59451 04683 81864 79200 58494 01711" , "1 86714 37520 24315");

_debug( test + "を暗号化。使用する鍵: " + oPubkey);

_debug("結果: " + oPubkey.encrypt( test ));

38875 64474 95279 32099 48253 16740 が得られるはずです。

上記に対応する秘密鍵
1 05034 82749 44284 05749 84137 22755
を使って、上で得られた暗号を解除します。

var encrypted = "38875 64474 95279 32099 48253 16740";

var oSeckey = new RSA();
oSeckey.setKeys("1 59451 04683 81864 79200 58494 01711" , "1 86714 37520 24315" ,
    "1 05034 82749 44284 05749 84137 22755" );

_debug( encrypted + "を暗号解除。使用する鍵: " + oSeckey );

_debug( "結果: " + oSeckey.decrypt( encrypted ) );

1234 56789 05555に戻るはず。

まとめ

暗号化と暗号解除は、計算量が多いです。そのためPGPでも、メッセージ全文を公開鍵で暗号化することはせず、メッセージを共有鍵暗号で暗号化して、その共有鍵を公開鍵で暗号化して送る、という方法が採用されました。

鍵が長くなった場合に時間がかかるのは鍵の生成です。その時間の大部分が素数の検索です。さらに言えば、候補の数が素数かどうかの確認に時間がかかります。手元の環境で、上の100ビット鍵を使うと、暗号化や暗号解除の処理は数秒~数十秒程度にすぎませんが、この100ビット鍵の生成には3分かかっています。また、試しに104ビット鍵を作ると7分かかりました。かたっぱしから割ってみて素数性を確認する方法では100ビットくらいが限界で(1つの素数あたり50ビット=10進16桁)、さらに上に行くには、確率的な方法を使う必要があります。

24ビットから始めて、この遊びもとうとう100ビットに到達しました。あくまで「遊び」ですが、やってみると、いろいろと実感が深まり、なにかと勉強になるもんです。

リンク

この記事のURL

テキスト版省パケ版XML版



webmaster@faireal.net