概要
違法素数（illegal prime）と呼ばれる素数についてのメモ。 違法素数と呼ばれている理由を簡潔に述べ、違法素数を模した素数を実際に生成してみる。
違法素数とは
違法素数とは、違法な情報やコンピュータプログラムを含む素数のことである。 ここで、「コンピュータプログラムを含む」とは、10進数表記の素数を2進数（バイナリ）に変換したものが、実行可能なプログラムになり得るという意味である。
違法素数の発見には、違法となるコンピュータプログラムを合法的に公開できないかという背景があった。 コンピュータプログラムの実態は「0」と「1」から成るバイナリであり、これは10進数に変換することができる。 もしも10進数に変換した数字が意味のある素数（巨大なものや未発見のものなど）になれば、その素数を正当な理由により公表することができる（すなわち、合法的に違法プログラムを公開することができる）。
典型的な違法素数としては、DVDのコピーガード（CSS）を破るプログラム（DeCSS）をgzipで圧縮したファイルを含むものがある。
プログラムを素数に変換する
当然、コンピュータプログラムを10進数に変換した値が都合よく意味のある素数
となるわけではない。したがって、何らかの方法を用いて、
から
を生成／発見する必要がある。
先述のDeCSSに関する違法素数の場合、下記の定理を用いることで、から
を発見することができた。
また、違法素数発見までの大まかなステップは次の通りである。
ステップ２．では、が素数かどうかを判定する必要がある。
DeCSSの場合は、楕円曲線素数判定法を用いて素数の判定を行っていた。
ここからは、上記のアイデアを踏襲し、違法でないプログラムを素数に変換してみる。本来は、素数として公開する価値のあるものを生成しなくてはならないが、素数としてプログラムを公開することは目的ではないため、適当な素数が発見できたら素数の探索を打ち切ることとする。
素数に変換するプログラム（test.c）は以下の通りである。
#include <stdio.h> int main() { printf("Hello, World!\n"); return 0; }
まずはgzipで圧縮する。
$ gzip test.c
生成された圧縮ファイルを確認する。
$ file test.c.gz
圧縮ファイルの中身を確認する。 画面中央に表示されるバイナリ文字列が抽出／変換対象である。
$ xxd -b test.c.gz
raw.binというファイルに、バイナリデータを抽出する。
$ xxd -b test.c.gz | cut -d: -f 2 | sed 's/ .*//; s/ //g' > raw.bin
raw.binの中身を確認する。
$ cat raw.bin
raw.binにバイナリ文字列が取り込めているが、改行も含まれている。 以下のpythonスクリプト（encode.py）を用いて、raw.binから改行を取り除きつつ、バイナリ文字列を抽出する。さらに、得られたバイナリ文字列を10進数に変換して出力する。
num = '' with open('raw.bin', 'r') as f: for line in f: num += line[:-1] k = int(num, 2) print('k = ' + str(k))
encode.pyを実行すると、test.c.gzのバイナリを10進数に変換した値が得られる。
k = 821600734566137881387000788187973003833081472275563418263905927542487877192781549631683632699881684903101404180775507841463395922519264003020975692899581694715033810660202936317042477536525814395922089837881244182300713085449348944937091072
次に、疑似的な違法素数を求める。
先述の通り、実際は公開する価値のある素数に変換するが、今回はただの検証であるため、
から生成できる任意の素数を使う。
さらに簡単のため、
とし、
は総当たりで求める。
ここで、
と
は互いに素であるという条件から、
は奇数のみを探索すればよい（探索範囲の上限はひとまず
とした）。
を求めるpythonスクリプト（calc.py）は以下の通り。
from sympy import isprime k = 821600734566137881387000788187973003833081472275563418263905927542487877192781549631683632699881684903101404180775507841463395922519264003020975692899581694715033810660202936317042477536525814395922089837881244182300713085449348944937091072 b_MAX = 1000 for b in range(1, b_MAX, 2): p = k * 256 + b if isprime(p): print('p = ' + str(p)) print('b = ' + str(b)) break
calc.pyを実行すると、と
が得られる。
p = 210329788048931297635072201776121088981268856902544235075559917450876896561352076705711009971169711335193959470278530007414629356164931584773369777382292913847048655529011951697162874249350608485356054998497598510668982549875033329903895314537 b = 105
ここまでで、プログラムを素数に変換することができた。
なお、この
は243桁である。
素数を変換してプログラムを得る
今度は、先ほど求めた素数からプログラムが得られることを確認する。
今、
と自然数
それぞれの値ならびに
という関係が公開されているとする。
素数を変換し、プログラムを求めるpythonスクリプト（decode.py）は以下の通り。
from Crypto.Util.number import long_to_bytes p = 210329788048931297635072201776121088981268856902544235075559917450876896561352076705711009971169711335193959470278530007414629356164931584773369777382292913847048655529011951697162874249350608485356054998497598510668982549875033329903895314537 a = 256 b = 105 k = (p - b) // a with open('sample.c.gz', 'wb') as f: f.write(long_to_bytes(k))
decode.pyを実行すると、sample.c.gzというファイルが生成される。 生成された圧縮ファイルを確認する。
$ file sample.c.gz
$ xxd -b sample.c.gz
sample.c.gzは、test.c.gzと同じ中身であることが確認できる。この圧縮ファイルを解凍すると、sample.cが生成される。
$ gzip -d sample.c.gz
sample.cの中身を確認すると、test.cと同じであることが分かる。
$ cat sample.c
これで、正しく元に戻せることも確認できた。
感想
非合法なものを意味のある素数として公開するというアイデアがとても面白く感じた。
実際にこのようなことができる素数を発見したときは、発見者はとても感動したのではないかと思う。
今回の検証にて、パラメータをうまく選べば、素数
210329788048931297635072201776121088981268856902544235075559917450876896561352076705711009971169711335193959470278530007414629356164931584773369777382292913847048655529011951697162874249350608485356054998497598510668982549875033329903895314537
に「Hello, World」を出力するCプログラム（を圧縮したもの）を埋め込めることが分かって良かった。
