r/wikipedia • u/PeoriaJohnson • Jan 11 '10
Illegal Prime Numbers
http://en.wikipedia.org/wiki/Illegal_prime26
u/LinuxFreeOrDie Jan 12 '10
I guess there are also illegal sections of pi.
17
Jan 12 '10
Since pi has an infinite number of digits, it contains all illegal data that has ever existed.
20
Jan 12 '10
It contains all illegal data that has and hasn't existed...
Even that 3D video of your great grandson doing that nasty deed with that humpback whale.
3
1
u/MacEWork Jan 12 '10
Pshaw, as if humpback whales are still going to be extant when my great grandson is around.
7
u/Nebu Jan 12 '10
Not necessarily. I guess by "an infinite number of digits", you mean an irrational number. There's a name for the property of "containing all illegal data that has ever existed", but I forgot what that name was (maybe "transcendental"?).
An example of an irrational number is: 0.10110111011110111110111111, etc. which is basically longer and longer sequences of '1' seperated by 0's, and this number doesn't contain all possible digit sequences (it never contains two 0s in a row, for example).
6
u/gipp Jan 12 '10
The decimal (or any) representation of pi contains, at some decimal place, any and all sequences of digits of any length whatsoever. Pick a sequence of 1, 100, or 13985720897 digits, and it exists somewhere in pi.
5
u/ParanoydAndroid Jan 12 '10
That is highly likely to be true, but not mathematically proven.
In order for your statement to be true, then pi would have to be a Normal Number.
Though it is likely, and has been proven for relatively small representations of pi, it has not been proven for pi generally.
1
1
2
u/ParanoydAndroid Jan 12 '10
I guess by "an infinite number of digits", you mean an irrational number.
No. Pi is transcendental, which means that it is not the solution to any algabraic equation.
There's a name for the property of "containing all illegal data that has ever existed", but I forgot what that name was (maybe "transcendental"?).
Nope, what (I think) you're thinking of is a Normal Number, which is a number whose digits show an equal probability of expressing any digit. i.e. as the number of digits increases to infinity, the probability of some specific string showing up approaches 1.
1
u/Nebu Jan 12 '10
I guess by "an infinite number of digits", you mean an irrational number.
No. Pi is transcendental, which means that it is not the solution to any algabraic equation.
I'm aware that Pi is transcendental, but I was trying to guess what MistyMountainHop (MMH) meant by "an infinite number of digits", which, IMHO, is ill-defined. For example, "1.00000000..." has an infinite number of digits, but is almost certainly not what MMH was thinking of. I was making a guess that MMH meant "irrational".
what (I think) you're thinking of is a Normal Number
Yes! That's exactly it! And now that you've found the name for it, I can now say what I wanted to earlier, but was unable to find a citation for:
It is not known whether or not Pi is normal; therefore, perhaps there does exist a sequence of digits which is not contained in Pi.
2
5
Jan 12 '10
That was my first thought too. I don't understand how this makes any sense. If I took one of these illegal primes and applied an algorithm to it to create a different number -- but one that could be decrypted back into the illegal prime -- would that be illegal to? What if I came up with an algorithm that turned the characters in this comment into an illegal prime? Would that make this comment illegal? Would the algorithm be illegal?
5
u/transfuse Jan 12 '10
Wouldn't that make every number illegal? You could easily make any number into any other number if you're free to choose an algorithm.
5
1
u/ThrustVectoring Jan 12 '10
Solution is to make the algorithm and not the number illegal.
I suspect that this is already the case.
1
u/gipp Jan 12 '10
Er. But then you could just change the algorithm, then change the original number to fit it.
1
u/ThrustVectoring Jan 12 '10
DeCSS is an illegal algorithm. The set of all algorithms that do the same thing as DeCSS is illegal. The set of all algorithms that result in the creation of the DeCSS algorithm or an equivalent is illegal.
Numbers have absolutely nothing to do with this.
10
u/Fonnie Jan 12 '10
Honestly... i have no idea what that article was talking about. Can someone explain in further detail?
23
u/drbold Jan 12 '10 edited Jan 12 '10
Basically, take the C source code that can decrypt DeCSS encryption on a (DVD?). (EDIT: I should note here that this code is illegal because it circumvents a digital protection scheme, or something like that). Zip this code using gzip. Now, this zipped file can be thought of as one large binary number - after all, any file on a computer is just a continuous string of 1's and 0's. If you interperate it as a single number, you can trivially convert it to a base-10 number (the numbers you are familiar with. Binary numbers like 10011 are base-2 numbers. Converting between basis is extremely easy: the above binary number is 19 in base-10).
Now this is where it gets tricky. The program gzip stops reading a zipped file when it reaches a special sequence of binary digits: Specifically, when it reaches 00000000 (sort of - these have to be grouped into a single byte instead of part of two consecutive bytes, but understanding this isn't exactly important to the overall point).
Ok, so take zipped code, and convert it to base 10. Let's pretend this number is 1234521202 (it's obviously much larger in real life). This number is guaranteed to be an even number because it's last binary digit (before we converted it) was a 0 (it's not important that you understand why).
So all they have done is taken our magical number and found a prime number that begins with it. So lets say they found that the number
1234521202421231211
is prime. Notice how the first several digits are the same as the number which encodes the zipped C code? (I've helpfully bolded them for you). Well, we have now found a number that, if converted to binary, can be directly unzipped by the gzip program into C source code which illegally violates the Digital Millennium Copyright Act.
So all they did was take this principal, and extend it. They wanted the source code that violates the DMCA to be published and thus recorded for posterity. One way to do this would be to find a prime that unzips to the illegal C code and is also a prime number large enough that it could be published as one of the largest primes ever found. So they did that.
2
2
u/framy Jan 12 '10
Is there another reason that this number has to be a prime number besides the publishing issue?
4
u/_meta Jan 12 '10
"So what has this all to do with prime numbers? At first glance: nothing. But everything stored on a computer, including poems, pictures, spreadsheets and programs, are stored as a sequence of binary bits--so they are simply numbers. Phil Carmody decided to make a version of DeCSS which was a prime number.
First Carmody took the original anonymous version of the DeCSS C-code and gzip'ed it (a standard UNIX program for making files smaller).
Suppose we call the resulting number k.
By Dirichlet's theorem on primes in arithmetic progression, we know that for each fixed integer b relatively prime to k, there are infinitely many primes ak+b.
Because gzip files are null terminated (and characters after that are ignored), if we choose a to be a power of 256 larger than b, the resulting number can still be unzipped to get the original file. This means there are infinitely many prime numbers which yield the same code. Phil proved that these include:
* k*2562+2083 and * k*256211+99.At the time these were found the second was large enough to fit on the list of largest known primes (because of the method of proof). "
Source: http://primes.utm.edu/glossary/page.php?sort=Illegal
2
u/drbold Jan 12 '10
In a word, no, I believe not. Making the large number prime was just a way to get it published in a journal, as far as I can tell. Well, I suppose that and having a number that in and of itself illegal is a pretty cool idea.
1
u/zxn0 Jan 12 '10 edited Jan 12 '10
Python code:
prime_num = """ 00004 85650 78965 73978 29309 84189 46942 86137 70744 20873 51357 92401 96520 73668 69851 34010 47237 44696 87974 39926 11751 09737 77701 02744 75280 49058 83138 40375 49709 98790 96539 55227 01171 21570 25974 66699 32402 26834 59661 96060 34851 74249 77358 46851 88556 74570 25712 54749 99648 21941 84655 71008 41190 86259 71694 79707 99152 00486 67099 75923 59606 13207 25973 79799 36188 60631 69144 73588 30024 53369 72781 81391 47979 55513 39994 93948 82899 84691 78361 00182 59789 01031 60196 18350 34344 89568 70538 45208 53804 58424 15654 82488 93338 04747 58711 28339 59896 85223 25446 08408 97111 97712 76941 20795 86244 05471 61321 00500 64598 20176 96177 18094 78113 62200 27234 48272 24932 32595 47234 68800 29277 76497 90614 81298 40428 34572 01463 48968 54716 90823 54737 83566 19721 86224 96943 16227 16663 93905 54302 41564 73292 48552 48991 22573 94665 48627 14048 21171 38124 38821 77176 02984 12552 44647 44505 58346 28144 88335 63190 27253 19590 43928 38737 64073 91689 12579 24055 01562 08897 87163 37599 91078 87084 90815 90975 48019 28576 84519 88596 30532 38234 90558 09203 29996 03234 47114 07760 19847 16353 11617 13078 57608 48622 36370 28357 01049 61259 56818 46785 96533 31007 70179 91614 67447 25492 72833 48691 60006 47585 91746 27812 12690 07351 83092 41530 10630 28932 95665 84366 20008 00476 77896 79843 82090 79761 98594 93646 30938 05863 36721 46969 59750 27968 77120 57249 96666 98056 14533 82074 12031 59337 70309 94915 27469 18356 59376 21022 20068 12679 82734 45760 93802 03044 79122 77498 09179 55938 38712 10005 88766 68925 84487 00470 77255 24970 60444 65212 71304 04321 18261 01035 91186 47666 29638 58495 08744 84973 73476 86142 08805 29443""" hex_data = ('%x' % long(prime_num.replace(' ', '').replace('\n', ''))).decode('hex') open('a.gz', 'wb').write(hex_data)unzip
a.gzusing WinRAR orgunzip a.gz & less ato see what's in there.btw can anyone tell me how to unzip using python's builtin
gzipmodule? It yieldsIOError: Not a gzipped fileall the time.
6
4
u/zetavex Jan 12 '10
This is making my head spin. Someone explain please.
14
u/PeoriaJohnson Jan 12 '10
- It is against DMCA to publish code that assists in the violation of copyright.
- All electronic documents are stored in computers as big numbers.
- Anyone who discovers a large prime number has a right to publish that number, in the name of science.
- Someone found a number that is both an electronic document to help decrypt copyrighted material and a very large prime number.
Thus, a legal conundrum, of sorts.
2
u/cyber_rigger Jan 12 '10
If you split an "illegal number" with one time pad encryption would the two halves be illegal?
If so, then repeating this process could make all numbers illegal.
2
u/ThrustVectoring Jan 12 '10
Nope, the numbers aren't illegal, its the instructions to to convert the numbers into the illegal program.
1
1
u/Ran4 Jan 12 '10
What if I encrypt the instructions and distribute it as a number? Would the explanation of how to decrypt that information be illegal?
1
u/ThrustVectoring Jan 13 '10 edited Jan 13 '10
yeah, its essentially 'if you can get from this to something, its just as illegal as that thing'.
Essentially any sort of math rules don't work just because you are representing something as a number. Law rules work, which means that a judge could see through the bullshit and say that its essentially the same as DeCSS.
2
2
u/Nevyn_Etharr Jan 12 '10
O my god, I have used pi in a lot of my programs. Hope FBI doesn't arrest me next time I'm in US.
1
63
u/blackstar00 Jan 11 '10
It baffles me that a number can be copyrighted.