QFTのメモ

お題自由な学校のレポート課題1内で, ショアのアルゴリズムを説明するために QFT の概要について示したのだが, 折角なのでその内容の一部を抜粋し, こちらのブログのほうにも載せておくことにした. ショアのアルゴリズムについては, 調べればいくらでも出てくるし, 学会誌, 書籍等で分かり易く述べられていることも多いので, 本エントリで特別取り上げることはしないが, その大体は以下のアクティビティ図の手順の通りである2.

ショアのアルゴリズムのアクティビティ図

シンプルなブリッジのソフトウェア実装

以前の投稿, ARPパケットに対する挙動からネットワーク上の盗聴者を特定するにて, 実験を行うにあたりリンクレイヤー上のパケットの受信と送信を行なった. このパケットを別のネットワークインタフェースから送出するようにすればブリッジになるし, MAC アドレステーブルと照合して転送すれば L2 スイッチにもなるとのことで, 一応 Linux 上で動くものを作ってみた.

2 枚の NIC が必要であるが, Virtual Box の仮想アダプタを利用すれば良い. 実装の本質的な部分は, 異なるディスクリプタへの書き込みのみである. これを応用して, 複数個のネットワークインタフェースにも対応してみたい.


フィボナッチ数列の一般項の導出

フィボナッチ数列を以下の漸化式で定義する.

フィボナッチ数列

fn+2=fn+1+fn (n0)f_{n+2} = f_{n+1} + f_n\ (n\geq 0)

ここで, 初項と第二項をそれぞれ a1=1,a2=1a_1=1, a_2=1 とする. 各項を fn+2c2fn+1cfn1f_{n+2}\rightarrow c^2、f_{n+1}\rightarrow c、f_n\rightarrow 1 と置き換えると c2=c+1(1)c^2=c+1\tag{1} が得られる. この解は c=1±52c=\dfrac{1\pm{\sqrt{5}}}{2} となる. ここで, ψ=152,ϕ=1+52\psi = \dfrac{1-\sqrt{5}}{2}, \phi = \dfrac{1+\sqrt{5}}{2} と置く. フィボナッチ数列の漸化式の特性方程式の解は (1)(1) の解より ψ,ϕ\psi, \phi であるから fn+2=fn+1+fn{fn+2ψfn+1=ϕ(fn+1ψfn)fn+2ϕfn+1=ψ(fn+1ϕfn)f_{n+2}=f_{n+1}+f_{n}\Leftrightarrow\begin{cases}f_{n+2}-\psi f_{n+1}=\phi(f_{n+1}-\psi f_n) \\ f_{n+2}-\phi f_{n+1}=\psi(f_{n+1}-\phi f_n)\end{cases} と変形できる. いま bn=fn+1ψfn,cn=fn+1ϕfnb_n=f_{n+1}-\psi f_n, c_n=f_{n+1}-\phi f_n と置くと次の漸化式が得られる.


ARPパケットに対する挙動からネットワーク上の盗聴者を特定する

通信が暗号化されていればまだ良いが, 自分の送受信しているパケットを同一ネットワーク上の信用できない者/物に無断で見られるのはやはり気持ちの良いものではない. 本エントリではそのような不届き者の存在を仮定して, その不届き者を比較的簡単に特定するといった試みを行う.

お断り

本エントリでの試行は当然ながら私個人のローカル LAN 上で行なっており, 同様の試行を公衆回線上などで行うと迷惑/法に抵触する可能性があるのでやめること. 本エントリに起因する直接的又は間接的な損害に関して, その理由及び原因を問わず著者(Roki) は一切の責任を負わない.

ネットワーク盗聴を検出する原理

ネットワークに接続するためには, 大抵コンピュータに NIC を装着して TCP/IP の設定を済まし, ハブに接続する. 同プロトコルにおける各コンピュータの通信では, IP アドレスと MAC アドレスによる論理情報と物理情報の組み合わせを利用して, 目的のコンピュータに対するパケットの送信を実現する. 通常, その過程で NIC は自分とは無関係であるパケットを破棄する. しかし NIC をプロミスキャスモードにすると, 自分とは無関係であるパケットを破棄せずに取り込むようになる. 盗聴者はこれを利用して, 同一ネットワーク上を流れる他人のパケットを取得できる.


ベジェ曲線

典型的なパラメトリック曲線の一種である, ベジェ曲線(Bézier curve)についての学習メモ. パラメトリック曲線とその一種であるエルミート曲線に関しては, 前回の記事を参照.

ベジェ曲線は, パラメータ t(0t1)t\\ (0 \leq t \leq 1) と複数の制御点 PiP_i から構成されるパラメトリック曲線の一種である1. 始点と終点の線分から成る, 次数 nn のベジェ曲線は n+1n+1 の制御点をもち (=P0,P1,,Pn= P_0, P_1, \cdots, P_n の制御点があるベジェ曲線を n1n-1 次ベジェ曲線という), この内分点を繰り返し取ることによって, 曲線を得ることができる. この始点と終点の線分を, セグメントといい, これが得られる曲線そのものになる2. まず, ここでは 2 次ベジェ曲線を描くとして, そのイメージをつけるために, 図3を用いてその概要を見る. なお, 2 次ベジェ曲線は true type フォントなどで使われている.

2 次ベジェ曲線を描画する途中経過