実行可能素数 (Executable prime) とは、特定のOS (オペレーティングシステム) で実行可能な命令を含むプログラムとして解釈ができるような値を持つ実行可能数 (Executable number) であり、かつ素数である[1][2]。どのような素数が実行可能かはOSに依存するため、以下一般的に使用されているOSで考える。
最小の実行可能素数[]
現行のもので、1バイトプログラムを使用できる最も一般的なOSはx86であり、RET命令に当たる\(195\)が最小値となるが、これは素数ではない。フィル・カーモディとクリス・カルドウェルによると、x86で実行可能素数となる最小の数の候補は以下の2バイトプログラムである。
| 値 | 命令 | 実行結果 |
|---|---|---|
| \(7\times256+195=1987\) | POP ES; RET | クラッシュする (ただし、カーモディが実行した際にはクラッシュしなかった) [1]。 |
| \(14\times256+195=3779\) | PUSH CS; RET | クラッシュする[1]。 |
| \(22\times256+195=5827\) | PUSH SS; RET | クラッシュする[1]。 |
| \(38\times256+195=9923\) | ES:RET | 実行可能だがセグメントオーバーライドする[2]。カーモディはこれを最小の実行可能素数としている[1][3]。 |
| \(46\times256+195=11971\) | CS:RET | 実行可能だがセグメントオーバーライドする[2]。 |
| \(47\times256+195=12227\) | DAS; RET | プログラムが正常に終了する最小の実行可能素数[1][2]。 |
現行ではないOSを含む場合、カーモディは最小の実行可能素数を\(199\)であるとしている。これは、どちらも1980年には一般的だった、CP/Mを実行している8080またはZ80で実行可能な1バイトプログラムであり、ウォームリセットを実行するRST 0と解釈される[2]。
非自明な実行可能素数[]
初めて発見された非自明な実行可能素数は、カーモディが2001年9月10日に発見した\(\sim4.93108\times10^{1810}\)である[1][4]。この素数はi386でELFファイルとしてそのまま実行可能であり、DeCSSを表している[2]。よってこの素数は初めて発見された実行可能違法素数でもある[4] ( "違法" である理由は当該記事を参照) 。
49310835970285019002757776723907649572849077721502086320807501840979262788509765886455780201366007328679544734112831735367831201557535981978545054811571939345877330038009932619505876452502382040811018988504261517657994170425088903702911901587003047943282607382146954157033022798755768189560162403006411151690087287983819425827167456477481668434792846458092913153186007001004335318936319343912948604450370991980047709462921558180711169153031876288477878354157593289109329544735088188246549506000501900627470530538116427829426747485349652574536815117065502819055526562213531463104210086628679711444670636692198258615811125155565048134207686732340765505485910826956266693066236799702104812396562518006818323653959348395675357557532461902348106470098775302795618689292538069330520423814996994545694577413833568990600587083218127048611336820265159051663518740290181976939376778529287221095504129257925738186605845015055250274994771883129310457698090915304613359419030258813205932277444385255046677902451869706262778889197958042306575061566983469561779787965920164405193996071698111261519561027628323398257914233217269614437443810564855293488763492103098870287874532331325321226786332837027925099749969488775936915917644588032718384740235933020374888506755706587919461134193230781485443645437511320709860639074641756412163504238800296780855867037038750941076982118376549920520436825585464228850242996332268536912464855000755916640247292407164507253196744999529448434741902107729606820558130923626837987951966199798285525887161096136561780745661592488660889816456854172136292084665627913147846679155096515431011353858620819687583688359557789391454539356819960988085404765907358972898983425047128918416265878968218538087956279039978629449397605467534821256750121517082737107646270712467532102483678159400087505452543537