違法素数をデコード、任意のバイナリの素数を見つけるPHPとClojureのコード

decode.clj

;;; Usage: clj decode.clj prime.txt > decss.c.gz
;;;        gunzip decss.c.gz

(def src (slurp (first *command-line-args*)))
(def illegal-prime (bigint (.replaceAll src "[^0-9]" "")))
(def prime-bytes (.toByteArray (.toBigInteger illegal-prime)))

(def stdout (.getChannel (java.io.FileOutputStream. java.io.FileDescriptor/out)))
(.write stdout (java.nio.ByteBuffer/wrap prime-bytes))

decode.php

<?php
/**
 * Usage: php decode.php prime.txt > decss.c.gz
 *        gunzip decss.c.gz
 * require: GMP (brew install php56 php56-gmp)
 */

$file = file_get_contents($argv[1]);
$primeStr = preg_replace('/[^0-9]/','',$file);
$illegalPrime = gmp_init($primeStr);

echo gmp_export($illegalPrime);

discover.php

<?php
/**
 * Usage: cat hoge.gz | php discover.php
 * require: GMP (brew install php56 php56-gmp)
 */

$shift8 = gmp_init(256);

// 整数化
$binNum = gmp_init(0);
while (false !== ($ch = fgetc(STDIN)))
  $binNum = gmp_add(gmp_mul($binNum, $shift8), gmp_init(ord($ch)));

// $binNum * 256^x + y を素数判定
$dig = gmp_pow($shift8, 2);
while (true) {
  $shifted = gmp_mul($binNum,$dig);
  for ($i=1; $i<256; $i+=2) {
    $prime = gmp_add($shifted, gmp_init($i));
    if (gmp_prob_prime($prime, 10) > 0)
      goto discover;
  }
  $dig = gmp_mul($dig, $shift8);
}
discover:

echo gmp_strval($prime);




/*
example:
$ echo "hello world" > hello.txt
$ gzip hello.txt

$ cat hello.txt.gz |php discover.php ; echo
1130375567415046636046904582027313879410212693497295916820264467363375003537924147441411857973106735841287
$ cat hello.txt.gz |php discover.php > hello_prime.txt

$ php decode.php hello_prime.txt > hello2.txt.gz
$ gunzip hello2.txt.gz
$ cat hello2.txt
hello world
*/

prime.txtはここから素数をコピペして作るべし
http://en.wikipedia.org/wiki/Illegal_prime

decode.php.gzを素数化するとこんなかんじ

29956 83506 66310 56618 17329 64548 31889 39973 50705 38149
77466 41990 17486 33406 02162 33584 72661 70128 52523 21029
31911 13855 39436 02682 17711 19539 65727 87030 67551 49815
42331 06845 98460 23867 66277 71977 47452 96306 78163 44039
60705 80401 65817 34491 91517 81887 03883 22434 18915 07380
88174 15431 34999 35264 93384 21713 56923 48237 64560 13585
07432 95138 50860 01293 15306 16327 85203 84796 76236 69671
33694 13563 41661 06667 71562 88672 24969 42752 15040 65988
59891 84005 89473 30452 35402 04056 33026 42092 51605 89055
41300 65350 78506 42380 13606 65404 65530 44807 17409 07522
45451 41427 75547 69272 16041 39714 17010 08649 20743 08967
22663 72386 77466 97181 46913 40409