Editing 2626: d65536

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 8: Line 8:
  
 
==Explanation==
 
==Explanation==
In binary computing, 16 bit unsigned numbers range from 0 to 65535, for a total of 65536 unique numbers, a number which is hence well-known to software engineers. Generating large numbers in a manner that is truly random is a recurring problem in cryptography, required to send private messages to another party. People today still use dierolls to generate private random numbers.
+
{{incomplete|Created by a HEXAKISMYRIAPENTAKISCHILIAPENTAHECTATRIACONTAKAIHEXAHEDRON - Please change this comment when editing this page. Do NOT delete this tag too soon.}}
 +
In binary computing, 16 bit numbers range from 0 to 65535 (or 1 to 65536). Generating large numbers randomly is a recurring problem in cryptography.
  
In role-playing games (and occasionally in other tabletop games), multiple shapes of dice are often used to generate random numbers in specific ranges.  By convention, these are referred to as d''n'' according to their number of faces. A traditional six-faced die would be a d6, and many popular pen-and-paper role-playing games use dice ranging between d4 and d20. While there are larger dice used in tabletop games (most commonly d100), these are usually split into multiple smaller ones. For example, a d100 is often two d10s rolled together, with one die providing the first digit and the other die giving the second digit — the total number of possible combinations (100) is the product of the number of faces of the two dice (10 * 10). While "real" {{w|Zocchihedron|d100s}} and other large-numbered dice do exist, most people consider them to be impractical: they need to be either impractically large or have very small faces (resulting in small print for the numbers), they're close enough to being spheres that it's difficult to get them into a stable resting position, and even if they are stationary, determining which face is "on top" is difficult to do by eye. The Zocchihedron (d100) die is also difficult to ensure as unbiased because of geometry requiring dissimilar faces and therefore a different mixture of 'stopping factors' for each face it could land upon. The largest unbiased die is a [https://en.wikipedia.org/wiki/Disdyakis_triacontahedron d120] (excluding the bipyramids and trapezohedra, which can theoretically be made with arbitrarily many sides), so it is very likely that [[Cueball|Cueball's]] d65536 die is also biased.  
+
In role-playing games (and occasionally in other tabletop games), dice are often referred to as d[number] according to their number of faces. A traditional six-faced die would be a d6, and many popular pen-and-paper role-playing games use dice ranging between d4 and d20. While there are larger dice used in tabletop games (most commonly d100), these are usually split into multiple smaller ones to save the hassle of throwing large dice. For example, a d100 is often two d10s rolled together, with one die providing the first digit and the other die giving the second digit — the total number of possible combinations (100) is the product of the number of faces of the two dice (10 * 10). There are, however, "real" {{w|Zocchihedron|d100s}} and similar dice as well, but they are considered specialty dice and often nicknamed "golf balls" to emphasize how large and unwieldy they are.
  
Here, Cueball has constructed a d65536 for generating random 16 bit numbers. It may have solved the problem of generating large random numbers with fewer die rolls, but it magnifies all of the problems with large-numbered dice to ludicrous extremes. In order for the faces to be readable, the die is ridiculously huge, dwarfing the human standing next to it. Rolling such a die is not only physically challenging, but it would also need a huge space in which to roll if the result is to be random, and that space would need to have an extremely flat and rigid surface in order for the die to come to rest. And even if those problems were solved, simply getting to a vantage point to see the top of the die would be a major challenge, and determining which number was truly on top would be near impossible to do by eye. If one really wished to use dice, it would be much easier to simply use multiple dice rolls. For instance, one could roll eight d4 dice (or use 16 coin flips), and convert the result into binary. This has the same randomness as a single die roll{{fact}}, but can take much longer, so people do purchase d16s to simplify it and speed it up.
+
Here, Cueball has constructed a d65536 for generating random 16 bit numbers, likely with a [https://www.shapeways.com/product/U9CN6MT6X/d256 3d printer] or other CAM tools. It has solved the problem of being secure from a cryptography standpoint, but presents a new set of challenges from its sheer size, dwarfing an average human. While large in itself, a die that big could still be emulated by rolling multiple dice (e.g. 8 4-faced dice or 16 coin flips) and converting the result into binary before getting the desired number. Part of the humor stems from the the comic completely failing to mention another big problem with this die: Deciding which of the 65536 faces is up. This is another problem with a d100, as many sides appear to be up at once. Similarly horrible hilarity will ensue if such a massive die is cast with enough energy to be random while expect it to stop rolling in a short period of time let alone on a table top or even within a building (which raises the question of whether breaking through a wall or furniture is all part of the randomization or requiring a re-roll as per house rules).
  
The closest regular shape similar to the depicted in the comic could be a {{w|Goldberg polyhedron}}. However, no such polyhedron exists with exactly 65536 hexagonal faces. The closest Goldberg Polyhedron has a mixture of 65520 hexagons and 12 pentagons, totaling 65532 faces. It is possible to construct a fair die without a matching regular shape by limiting the sides which it could land on and designing those sides to be fair (for instance, a prism with rectangular facets that extend its entire length, and rounded ends to ensure it doesn't balance on end).
+
The closest regular shape similar to the depicted in the comic could be a {{w|Goldberg polyhedron}}. However no such polyhedron exists with exactly 65536 hexagonal faces. The closest Goldberg Polyhedron has a mixture of 65520 hexagons and 12 pentagons, totalling 65532 faces. It is possible to construct a fair die without a matching regular shape by limiting the sides which it could land on and designing those sides to be fair (for instance, a prism with rectangular facets that extend its entire length, and rounded ends to ensure it doesn't balance on end).
  
The title text references how cryptographic systems (especially RSA and other factoring-is-hard based systems) are vulnerable to quantum attacks as quantum computing technology develops. The title text is essentially punning on the idea of a "large" quantum system. "Large" in the quantum computing sense would be on the order of 64 qubits each of which would be an atom or two at most. This would still be microscopic and will never be as large as the giant die the comic is centered on; but for a well-observed environment and human rolling without sufficient entropy (consider somebody obsessed with a certain number dropping the die on something soft), a conventional computer could predict some rolls. See also [[538]] for non-mathematical paths of cryptography.
+
The title text references how many cryptographic systems (especially RSA and other factoring-is-hard based systems) are vulnerable to quantum attacks as quantum computing technology develops. The title text is essentially punning on the idea of a "large" quantum system. "Large" in the quantum computing sense would be on the order of 64 qubits each of which would be an atom or two at most. This would still be microscopic and will never be as large as the giant die the comic is centered on; but for a well-observed environment and human rolling without sufficient entropy (consider somebody obsessed with a certain number dropping the die on something soft), a conventional computer could predict some rolls. See also [[538]] for non-mathematical paths of cryptography.
  
Since 65536 is 2^16, if for some reason you must simulate a D65536 using nothing but D&D dice, the most efficient method is to roll a D8 4 times and roll a D4 twice (2^(3×4) · 2^(2×2)), or roll a D8 5 times and toss a coin (2^(3×5) × 2).
+
==Trivia==
 +
*If a real d65536 were constructed with each number having an equal area and each printed in 12 point font, the resulting die would be about 5 feet (1.5 meters) in diameter. If it were made out of standard acrylic, and not hollow, it would weigh about 2 tons (1700kg).
 +
*This die would have a 0.00001526 chance of rolling a natural one (or any other number).
 +
*There are seven 16-bit numbers fully visible in the picture: 30827, 25444, 11875, 28525, 12082, 13874 and 13359. They conceal a message. If these numbers are split big-endian into two 8-bit ASCII characters each, the result is <code>xkcd.com/2624/</code>.
  
 
==Transcript==
 
==Transcript==
:[A large sphere with a several lines, and in some places grids, are shown. Cueball, standing next to it, is dwarfed by its size, as it is at least seven times as tall as he is. The sphere has many lines following various great circles or parallel lesser circles around the curve of the sphere, and some patches of cross hatching to suggest further texturing along these lines hovering just below the degree of most of the illustrative detailing. The lines and grids cover the sphere in three layers of parallel axes, angled sixty degrees from each other, implying a huge mesh of equilateral triangles or hexagons. In the top right part of the ball is a black circle. An arrow points to this circle, and the end of the arrow goes to a larger circle that partly obscures the rightmost part of the sphere. The circle shows a zoom in on the surface in the black circle on the sphere. The zoom shows a small portion of the sphere's surface, showing that the grid comes along because the sphere is divided into elongated hexagonal faces with numbers up to at least five-digits. Seven numbers can be fully seen, but there are nine other faces partly shown, five of these with part of their numbers visible, one of these clearly only have four digits. One of the empty faces must also have a number with only 1-3 digits, as no numbers are visible although a significant part of the face is visible.]
+
{{incomplete transcript|Do NOT delete this tag too soon.}}
 +
:[Drawing of a large die with many sides, about ten meters in diameter; Cueball is standing next to it as a size reference. A small portion of the die's surface is zoomed in, showing elongated hexagonal faces with five-digit numbers.]
  
:[Here follows the numbers in the zoomed in part of the sphere, with  "..." represents numbers being cut off. The numbers are read in lines left to right, even though the numbers are tilted from down towards the right, which could have suggested a different reading order.]  
+
:[Numbers on the zoomed in part of the die, "..." represents being cut off:]  
 
:30827  
 
:30827  
:16[bottom part of a cut-off line][small cut-off circle]  
+
:16[bottom part of a line][small circle]  
 
:...38  
 
:...38  
 
:11875  
 
:11875  
 
:25444  
 
:25444  
:...[top part of a cut-off line]5  
+
:...[top part of a line]5  
 
:12082  
 
:12082  
 
:28525  
 
:28525  
:3 [left part of a cut-off line]...  
+
:3...  
 
:13359  
 
:13359  
 
:13874  
 
:13874  
:[Two cut-off lines, likely the start of the number 2]...
+
:2...
  
 
:[Caption below the image:]
 
:[Caption below the image:]
 
:The hardest part of securely generating random 16-bit numbers is rolling the d65536.
 
:The hardest part of securely generating random 16-bit numbers is rolling the d65536.
 
==Trivia==
 
*If a real d65536 were constructed with each number having an equal area and each printed in 12 point font, the resulting die would be about 5 feet (1.5 meters) in diameter, which isn't several times the size of a person as the comic suggests, but is still large enough to be hilariously inconvenient. If it were made out of standard acrylic, and not hollow, it would weigh about 2 tons (1700kg).
 
*This die would have a 0.00001526 chance of rolling a natural one (or any other number).
 
*There are seven 16-bit numbers fully visible in the picture: 30827, 25444, 11875, 28525, 12082, 13874 and 13359. [https://dotnetfiddle.net/fjLYZe They conceal a message.] If these numbers are split big-endian into two 8-bit ASCII characters each, the result is <code>xkcd.com/2624/</code>. For example, converting the first number 30,827 to hexadecimal (in which a four digit number covers exactly 65,536 different values) converts to a hex value of 786B. Splitting this into 78 and 6B, these are the hex ASCII codes for "x" and "k" respectively.
 
  
 
{{comic discussion}}
 
{{comic discussion}}
Line 49: Line 49:
 
[[Category:Cryptography]]
 
[[Category:Cryptography]]
 
[[Category:Comics featuring Cueball]]
 
[[Category:Comics featuring Cueball]]
[[Category:Binary]]
 

Please note that all contributions to explain xkcd may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see explain xkcd:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel | Editing help (opens in new window)