A Coincidental Note
Argh. You \emph{hate}\ it when you see people cheating. You hate it
even more when they try to be overly clever. You've found a note left
by one of your school's famous cheating team. Apparently, Henry
Gondorf took a test earlier and wants to help his buddies. It looks
like random text, but you doubt it. You heard him complaining about
funky French names, so you're guessing it's a Vigen\`ere cipher.
Luckily, you know it's weakness: analysis through the index of
coincidence.
\emph{The rest of the story is not necessary for the problem}.
The Vigen\`ere cipher works by shifting characters by a relative
amount. Each letter of the key determines the distance the plaintext
will be shifted. For example, if the plaintext were `A' and the
appropriate letter of the key were `G', the result would be `G' (`A' +
`G' - `A'). If the next letters of the text and key were `C' and `D',
respectively, the result would be `F'. Thus, each letter of the key
determines a rotation of the alphabet. The key is reused, so if the
key were five letters long, every five characters would be from the
same rotation.
Write a program to determine the index of coincidence of a given
string with shifts ranging from one to ten.
The index of coincidence of a sample is calculated by rotating the
letters to the right and finding the probability of finding the
same letter in the same location. For example, the index of
coincidence of \texttt{ackgaknarf} with a shift of three is .3.
Random letters have an index of coincidence around 3.8\%; English
text has one around 5.9\%. Rotating the alphabet does not change
the index of coincidence, so it can be used to identify the length
of the key used in a Vignere cipher. Here, however, the samples
will not be long enough to gather useful statistics.
Input will consist of a sequence of at most 30 letters. Capitalization
does not matter.
Your output should be a table of shifts and calculated indices to three
places after the decimal point. The output should not be expressed as
a percentage.
Ciphertext: ackgaknarf
Shift Index
1 0.000
2 0.000
3 0.300
4 0.100
5 0.000
6 0.100
7 0.300
8 0.000
9 0.000
10 1.000
Ciphertext: thisoneistooeasy
Shift Index
1 0.062
2 0.000
3 0.000
4 0.000
5 0.188
6 0.188
7 0.125
8 0.000
9 0.125
10 0.188
Ciphertext: ialreadyknowhowtodrink
Shift Index
1 0.000
2 0.000
3 0.182
4 0.045
5 0.000
6 0.045
7 0.045
8 0.000
9 0.045
10 0.000