I am programming an automatic Vigenere Cipher decoder using a frequency analysis. To be able to do that, I need the length of the key used. I am programming in Java.
My program works perfectly fine, but only with key lengths that are prime numbers. Example: The key has a length of 6. My program detects a key length of 3, as it is the smallest factor.
My input would look like this: [196, 231, 15, 67, 93, 26]. These are the distances between matching substrings in the ciphered text. These are only example numbers, not sure if they would work. The output should be a single number, the key length associated to the numbers.
This is my code for determining the key length:
public class LengthDeterminer {
public static int getLength(int[] matchDistances) {
if (matchDistances == null) return -1;
Map<Integer, Integer> factorsToOccurency = factorsToOccurency(matchDistances); // Collect factors with occurency count
if (VigenereDecipher.debugMode()) {
System.out.println(factorsToOccurency);
}
return Collections.max(factorsToOccurency.entrySet(), Map.Entry.comparingByValue()).getKey();
}
private static Map<Integer, Integer> factorsToOccurency (int[] matchDistances) {
Map<Integer, Integer> returnMap = new HashMap<>();
for (int i = 0; i < matchDistances.length; i++) {
if (matchDistances[i] <= 1) continue; // Negative distances would only double every number, maybe a problem of a other part of my program
int smallFactor = smallestFactor(matchDistances[i]);
if (returnMap.containsKey(smallFactor)) {
returnMap.put(smallFactor, returnMap.get(smallFactor) +1);
} else {
returnMap.put(smallFactor, 1);
}
}
return returnMap;
}
private static int smallestFactor(int x)
{
if(x < 1) return -1;
if(x == 1) return 1;
for(int i=3; i<=x; i++)
if(x % i == 0)
return i;
return -1; // To stop compiler's complaints.
}
}
The getLength() class is the one being initially called. I input the distances between matching substrings in the ciphered text. When using non-prime keys it doesnt work, it just spits out the smallest prime factor of the key length.
Can anybody help me?