Temukan perdana ilegal (kemungkinan) terkecil

8

Sebuah prime ilegal adalah bilangan prima yang mengkodekan informasi yang ilegal untuk memiliki - khususnya, dalam satu kasus, file gzip dari kode sumber DeCSS , sebuah software untuk mendekripsi copy-dilindungi DVD.

Tugas Anda memiliki dua fase:

  1. Buat file sumber yang mengimplementasikan DeCSS dalam sesedikit mungkin byte. Ini dapat dilakukan dalam bahasa apa pun.

  2. Kompres file sumber ini (menggunakan algoritma kompresi favorit Anda), dan lakukan iterasi melalui file-file yang mungkin terekompresi ke hal yang sama (menggunakan teorema Dirichlet jika itu membantu) sampai keaslian tercapai.

Karena benar-benar membuktikan keutamaan mungkin mengambil terlalu banyak daya komputasi, itu akan cukup bagi bagian kedua untuk lulus tes " kemungkinan prima " (misalnya Miller-Rabin ) dengan probabilitas kurang dari 2 -100 .

Orang dengan kemungkinan perdana terkecil menang.

code-challenge Joe Z.
sumber
Anda mungkin perlu menggunakannya open("out.gz", 'wb').
Joe Z.
1
Anda mengatakan hampir persis apa yang harus kita lakukan. Di mana kesenangannya hanya dengan mengikuti perintah?
ugoren
DeCSS sudah cukup dari tantangan itu sendiri yang saya usulkan di Sandbox, meskipun tampaknya tidak ada yang tertarik. Tapi itu cukup non-sepele untuk memverifikasi bahwa itu membutuhkan test suite yang bagus. Adapun teorema Dirichlet: apa hubungannya dengan file yang mengompres ke hal yang sama? Berapa banyak format file kompresi yang memiliki deret aritmatika tak terbatas yang mendekompres ke hal yang sama?
Peter Taylor
2
@PeterTaylor: Menurut entri Wikipedia (di situlah saya mendapatkan info itu di tempat pertama), menambahkan trailing karakter nol ke file gzip akan menghasilkan kode yang sama yang dihasilkan pada dekompresi. Mengingat bahwa Anda memiliki file gzip yang valid, teorema Dirichlet menyatakan bahwa pada akhirnya Anda akan menemukan bilangan prima dengan menambahkan karakter nol di akhir dan kemudian menambahkan angka yang relatif prima untuk semuanya.
Joe Z.
1
Implementasi GNU mungkin gagal memberikan kesalahan, tetapi jika demikian maka itu bukan dekompresor yang sesuai seperti yang didefinisikan dalam spesifikasi format file. Adapun kasus uji, mereka harus cukup kecil untuk menanamkan dalam pertanyaan dan tidak boleh melanggar hak cipta siapa pun.
Peter Taylor

Jawaban:

4

Java (sekitar 2048 bit)

14951059135011030015480908520726485619103063818476057564660360628799292628035097139943806440612109515246411930476451010075357954683100898936593739762786721583164361680031433048702186473094092210118641364347032899100220949873928633438856732508590863996147513646363328498023218161000104939462296626885931085914071985322044175133733909287366858309877885352980365735019082872958155754848273583139151810812417879417661663044291630490856568568829579704849173609110647303708828534149066778229242936297219753177569833591637704406031011600073082097633261877649625598598670707453831253888534424016277678136396605413799234576729

Kodenya adalah

void C(int[]s,int[]k){int a=k[0]^s[84]|256,b=k[1]^s[85],c=k[2]^k[3]<<8^k[4]<<16^s[86]^s[87]<<8^s[88]<<16,d=c&7,e=0,f,i=127;for(c=c*2+8-d;++i<2048;e>>=8){e+=S[f=(c>>17^c>>14^c>>13^c>>5)&255]+T[d=Q[b]^R[a]];b=a/2;a=a&1<<8^d;c=c<<8|f;s[i]=P[s[i]]^e&255;}}//!Y

Saya mengambil kebebasan mengubah nama tabel pencarian dari CSSt1... CSSt5ke P... T, dan metode dari CSSDescrambleke C. Saya juga membuang langkah gzip, karena itu memberikan file yang lebih besar daripada sumbernya.

Peter Taylor
sumber
Lulus Ballie-PSW. Juga, apakah saya mengerti bahwa algoritma kompresi favorit Anda adalah None? ;)
primo
2
@ primo, algoritma kompresi favorit saya adalah kontekstual: yang memberikan hasil terkecil untuk data input. ;)
Peter Taylor