Matthieus
06-09-2008, 12:40 PM
Can anyone Solve this brainteaser?
This brainteaser concerns encryption, which is the conversion of a document (which is called the plaintext) into unreadable gibberish (which is called the ciphertext) in a manner such that it can then be turned back into the original plaintext only by the intended recipient. One primitive form of encryption is the monoalphabetic simple substitution cipher. The name sounds complicated, but it's just like the cryptogram puzzles you've probably seen in crossword puzzle books or newspapers. It basically means the type of code wherein you write out the alphabet on one line, and then underneath it you write it out again, but this time in an arbitrary order, like this:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ZYXWVUTSRQPONMLKJIHGFEDCBA
The important thing to note is that the lower alphabet can be in any order at all. Together they form an encryption key. To encrypt a message, you look up each letter of the plaintext in the upper alphabet, and replace it with the corresponding letter in the lower alphabet.
For example, let's suppose that our plaintext is "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG". We would start with the letter T, and look it up in the upper alphabet. Directly under it, we see that there is a G, so we would write out a G as the first letter of the ciphertext. Similarly, H would become S, and E would become V. If you continued the process, the final encrypted message would be "GSV JFRXP YILDM ULC QFNKH LEVI GSV OZAB WLT". Normally, to decrypt the message, one would just reverse the process by looking up the letters of the ciphertext in the lower alphabet, and finding the corresponding letters in the upper alphabet, but I have something else in mind.
A curious fact about this process is that no matter what order the lower alphabet is in, any plaintext which you encrypt repeatedly will eventually produce the original plaintext after some number of passes. By "encrypt repeatedly", I mean to treat the resulting ciphertext as a new plaintext, and encrypt it again, and so on until it eventually produces the original plaintext, thus coming full circle. Using the key from the example above, it would only take two passes to arrive back where you started, but consider this key:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
CDEFGHIJKLMNOPQRSTUVWXYZAB
Using this key, you would have to encrypt and re-encrypt, over and over, each time going from the upper alphabet to the lower one, 13 times in all, before finally arriving back at the original plaintext, as you can see here:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
if this key represents the minimum number of one iteration, then some other key must represent the maximum.
Here is the big question: Using the process described above, what is the maximum number of times one would have to encrypt something before once again arriving back at the original plaintext?
This brainteaser concerns encryption, which is the conversion of a document (which is called the plaintext) into unreadable gibberish (which is called the ciphertext) in a manner such that it can then be turned back into the original plaintext only by the intended recipient. One primitive form of encryption is the monoalphabetic simple substitution cipher. The name sounds complicated, but it's just like the cryptogram puzzles you've probably seen in crossword puzzle books or newspapers. It basically means the type of code wherein you write out the alphabet on one line, and then underneath it you write it out again, but this time in an arbitrary order, like this:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ZYXWVUTSRQPONMLKJIHGFEDCBA
The important thing to note is that the lower alphabet can be in any order at all. Together they form an encryption key. To encrypt a message, you look up each letter of the plaintext in the upper alphabet, and replace it with the corresponding letter in the lower alphabet.
For example, let's suppose that our plaintext is "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG". We would start with the letter T, and look it up in the upper alphabet. Directly under it, we see that there is a G, so we would write out a G as the first letter of the ciphertext. Similarly, H would become S, and E would become V. If you continued the process, the final encrypted message would be "GSV JFRXP YILDM ULC QFNKH LEVI GSV OZAB WLT". Normally, to decrypt the message, one would just reverse the process by looking up the letters of the ciphertext in the lower alphabet, and finding the corresponding letters in the upper alphabet, but I have something else in mind.
A curious fact about this process is that no matter what order the lower alphabet is in, any plaintext which you encrypt repeatedly will eventually produce the original plaintext after some number of passes. By "encrypt repeatedly", I mean to treat the resulting ciphertext as a new plaintext, and encrypt it again, and so on until it eventually produces the original plaintext, thus coming full circle. Using the key from the example above, it would only take two passes to arrive back where you started, but consider this key:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
CDEFGHIJKLMNOPQRSTUVWXYZAB
Using this key, you would have to encrypt and re-encrypt, over and over, each time going from the upper alphabet to the lower one, 13 times in all, before finally arriving back at the original plaintext, as you can see here:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ
if this key represents the minimum number of one iteration, then some other key must represent the maximum.
Here is the big question: Using the process described above, what is the maximum number of times one would have to encrypt something before once again arriving back at the original plaintext?