Encuentra el primo ilegal (probable) más pequeño

8

Un número primo ilegal es un número primo que codifica información que es ilegal poseer, específicamente, en un caso, un archivo gzip del código fuente de DeCSS , una pieza de software para descifrar DVD protegidos contra copia.

Su tarea tiene dos fases:

  1. Cree un archivo fuente que implemente DeCSS en la menor cantidad de bytes posible. Esto se puede hacer en cualquier idioma.

  2. Comprima este archivo fuente (usando su algoritmo de compresión favorito) e itere a través de posibles archivos que se descompriman a la misma cosa (usando el teorema de Dirichlet si es útil) hasta que se alcance la primalidad.

Como probar que la primalidad puede tomar demasiado poder de cómputo, será suficiente para que la segunda parte pase una prueba de " cebado probable " (por ejemplo, Miller-Rabin ) a una probabilidad de menos de 2 -100 .

La persona con el menor primo probable gana.

code-challenge Joe Z.
fuente
Es posible que deba usar open("out.gz", 'wb')en su lugar.
Joe Z.
1
Dijiste casi exactamente lo que deberíamos hacer. ¿Dónde está la diversión en solo seguir órdenes?
ugoren
DeCSS es un desafío suficiente en sí mismo que lo propuse en el Sandbox, aunque nadie parece interesado. Pero no es lo suficientemente trivial como para verificar que necesita un buen conjunto de pruebas. En cuanto al teorema de Dirichlet: ¿qué tiene que ver eso con los archivos que se comprimen a la misma cosa? ¿Cuántos formatos de archivo de compresión tienen secuencias aritméticas infinitas que se descomprimen en la misma cosa?
Peter Taylor
2
@PeterTaylor: De acuerdo con la entrada de Wikipedia (que es donde obtuve esa información en primer lugar), agregar caracteres nulos finales a un archivo gzip dará como resultado que se produzca el mismo código en la descompresión. Dado que tiene un archivo gzip válido, el teorema de Dirichlet establece que eventualmente encontrará un número primo al agregar caracteres nulos al final y luego agregar un número que sea relativamente primo para todo.
Joe Z.
1
La implementación de GNU puede fallar al dar un error, pero si es así, entonces no es un descompresor compatible como se define en las especificaciones del formato de archivo. En cuanto a los casos de prueba, deben ser lo suficientemente pequeños como para incrustar en la pregunta y no deben infringir los derechos de autor de nadie.
Peter Taylor

Respuestas:

4

Java (aproximadamente 2048 bits)

14951059135011030015480908520726485619103063818476057564660360628799292628035097139943806440612109515246411930476451010075357954683100898936593739762786721583164361680031433048702186473094092210118641364347032899100220949873928633438856732508590863996147513646363328498023218161000104939462296626885931085914071985322044175133733909287366858309877885352980365735019082872958155754848273583139151810812417879417661663044291630490856568568829579704849173609110647303708828534149066778229242936297219753177569833591637704406031011600073082097633261877649625598598670707453831253888534424016277678136396605413799234576729

El código es

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

Me tomé la libertad de renombrar las tablas de búsqueda de CSSt1... CSSt5a P... T, y el método de CSSDescramblea C. También abandoné el paso gzip, porque estaba dando un archivo más grande que la fuente.

Peter Taylor
fuente
Pases Ballie-PSW. Además, ¿debo entender que tu algoritmo de compresión favorito es None? ;)
primo
2
@primo, mi algoritmo de compresión favorito es contextual: el que da el resultado más pequeño para los datos de entrada. ;)
Peter Taylor