Encontre o menor primo ilegal (provável)

8

Um número primo ilegal é um número primo que codifica informações ilegais de possuir - especificamente, em um caso, um arquivo gzip do código fonte do DeCSS , um software para descriptografar DVDs protegidos contra cópia.

Sua tarefa tem duas fases:

  1. Crie um arquivo de origem que implemente o DeCSS no menor número possível de bytes. Isso pode ser feito em qualquer idioma.

  2. Compacte esse arquivo de origem (usando seu algoritmo de compactação favorito) e repita os arquivos possíveis que descompactam para a mesma coisa (usando o teorema de Dirichlet, se ajudar) até que a primalidade seja atingida.

Como, na verdade, provar que a primalidade pode levar muito poder de computação, será suficiente para a segunda parte passar em um teste de " provável provável " (por exemplo, Miller-Rabin ) para uma probabilidade menor que 2-100 .

A pessoa com o menor número provável de vitórias provável.

code-challenge Joe Z.
fonte
Você pode precisar usar open("out.gz", 'wb').
Joe Z.
1
Você disse quase exatamente o que deveríamos fazer. Onde está a diversão em apenas seguir ordens?
Ugoren
O DeCSS é, por si só, um desafio suficiente que eu o propus no Sandbox, embora ninguém pareça interessado. Mas não é trivial o suficiente para verificar se ele precisa de um bom conjunto de testes. Quanto ao teorema de Dirichlet: o que isso tem a ver com arquivos compactados para a mesma coisa? Quantos formatos de arquivo de compactação têm sequências aritméticas infinitas que são descompactadas para a mesma coisa?
Peter Taylor
2
@ PeterTaylor: De acordo com a entrada da Wikipedia (onde obtive essas informações em primeiro lugar), adicionar caracteres nulos à direita em um arquivo gzip resultará no mesmo código produzido após a descompressão. Dado que você tem um arquivo gzip válido, o teorema de Dirichlet afirma que, eventualmente, você encontrará um número primo adicionando caracteres nulos ao final e, em seguida, adicionando um número que seja relativamente primordial à coisa toda.
Joe Z.
1
A implementação do GNU pode falhar ao fornecer um erro, mas, nesse caso, não é um descompactador compatível, conforme definido na especificação do formato do arquivo. Quanto aos casos de teste, eles precisam ser pequenos o suficiente para serem incorporados à pergunta e não devem infringir os direitos autorais de ninguém.
Peter Taylor

Respostas:

4

Java (cerca de 2048 bits)

14951059135011030015480908520726485619103063818476057564660360628799292628035097139943806440612109515246411930476451010075357954683100898936593739762786721583164361680031433048702186473094092210118641364347032899100220949873928633438856732508590863996147513646363328498023218161000104939462296626885931085914071985322044175133733909287366858309877885352980365735019082872958155754848273583139151810812417879417661663044291630490856568568829579704849173609110647303708828534149066778229242936297219753177569833591637704406031011600073082097633261877649625598598670707453831253888534424016277678136396605413799234576729

O código é

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

Tomei a liberdade de renomear as tabelas de pesquisa de CSSt1... CSSt5para P... Te o método de CSSDescramblepara C. Também abandonei a etapa gzip, porque estava dando um arquivo maior que a fonte.

Peter Taylor
fonte
Passa Ballie-PSW. Além disso, devo entender que seu algoritmo de compactação favorito é None? ;)
primo 15/05
2
@primo, meu algoritmo de compactação favorito é contextual: aquele que fornece o menor resultado para os dados de entrada. ;)
Peter Taylor