4 ms·
tl;dr- Programming code serialized to binary seems like a Base-2 number to them, so they were looking for "illegal" C scripts that would be prime when read as
by _Nat_ 9y ago
tl;dr- Programming code serialized to binary seems like a Base-2 number to them, so they were looking for "illegal" C scripts that would be prime when read as a Base-2 number.
They give the example of a C script that breaks an old DRM crypto scheme.
It seems kinda silly since primes have a fairly regular distribution, so all they need to do is:
1. Pick any program they want to be "prime".
2. Serialize it and check if it's prime. If so, done; if not prime, continue.
3. Perform some minor code modification that doesn't change the script's functionality, e.g. tweaking a variable name or the content of a comment.
4. Return to Step (2), looping until a prime representation has been found.
- Normal_gaussian 9y ago* 3 append a NULL byte * 4 serialise and check if prime; if so then done 5 check if any byte value makes it prime when appended. If so, append it, else append NULL. Repeat until done
- zodiac 9y agoThere's already a 1401-digit prime that contains the gzip of the source code of DeCSS. He wanted to do more.
- dmurray 9y agoStep 2 (checking if huge numbers are prime) is a hard problem. Additionally, the author wanted to find a prime that encoded the program that was also notable for some other reason (to give people a legitimate pretext to host it). He decided to try to make it one of the largest primes ever discovered, and it was, though it no longer is.
- xucheng 9y agoFYI, prime number test can be done in determining polynomial time (instead of NP). So it is not a hard problem.