Podcast 8, April 2008: Codes and codebreaking - the Enigma machine

// INDENTATION HAS NOT BEEN PRESERVED BY THIS WEB SITE,,, sorry about that.. .

// Dennis Bednar 2010-08-03.
//
// This code is related to Enigma plugboard of Enigma cryptographic machine used in World War 2.
// There are 26 plugs labelled A-Z, in the plugboard.
// The "plug" for each letter actually has two sockets, and there are two male pins at end of each wire.
//
// A wire can be between any two *different* letters, which causes the pair of letters to be swapped.
// Hence if there is a wire between A and K, then input A converts into output K,
// and input K converts into output A. (IE, A <-> K).
//
// To compile and run this code:
//
// contents of doit.cmd file:
// rem compile and run Main.java
// del Main.class
// \jdk1.5.0_08\bin\javac.exe Main.java
// \jdk1.5.0_08\bin\java.exe Main
//
// Then just run doit.cmd.
// ====================================================

import java.math.BigInteger; // for big integers arbitrarily large

public class Main
{
public static void main( String argv [] )
{

// TEST CODE IS commented out.

// testFactorials();

// testCommas();

work();
}

// Unit Test Code
// compute n! for n=1..10

public static void testFactorials()
{
System.out.println( "=== BEG testFactorials ===" );
for (int i = 1; i < 10; ++i)
{
// convert into into String, so we can use BigInteger(String) constructor
String strNum = new Integer(i).toString();

BigInteger bi = new BigInteger( strNum );
BigInteger result = factorial( bi );
System.out.println( strNum + "!=" + result );
}
System.out.println( "=== END testFactorials ===" );
}

// Unit Test Code
// try putting in comma's with decimal digits strings that are 1..MAX_PLACES length
// starting with "1", "12", "123", "1234", ... "123456789", "1234567890", ...
// we expect to convert "1234" into "1,234", to add commas in that number.

public static void testCommas()
{
final int NUM_PLACES = 25; // a constant, max nr of decicmal positions

System.out.println( "=== BEG testCommas ===" );
// try num=1, "12", "123", ... "123456789", "1234567890", "12345678901"
String num = "";

// used to figure out which digit to grab next
String digits = "0123456789";

// try input number strings with values of "1", "12", "123", "1234",
// and so forth

for (int i = 1; i <= NUM_PLACES; ++i)
{
int pos = i%10;
num += digits.substring( pos, pos+1 );
String result = addCommas (num );
System.out.println( "IN: " + num + " OUT: " + result );
}
System.out.println( "=== END testCommas ===" );

}

// see also:
// http://www.codesandciphers.co.uk/enigma/steckercount.htm
//
// More abstractly: the number of ways of choosing m pairs out of n objects is:
//
// n! /((n-2m)! m! 2m)
//
// If you want to convince yourself of this formula you might like to check that there are:
//
// 3 different ways of putting 2 pairs of wire into 4 plugboard sockets
// 15 different ways of putting 3 pairs of wire into 6 plugboard sockets.
// From this formula we can find out something which often surprises people, which is that the number of possible plugboard pairings is greatest for 11 pairs, and then decreases:
//
// EXPECTED OUTPUT from this function, based on above "see also" HTML link:
//
// 1 pair: 325
// 2 pairs: 44.850
// 3 pairs: 3,453,450
// 4 pairs: 164,038,875
// 5 pairs: 5,019,589,575
// 6 pairs: 100,391,791,500
// 7 pairs: 1,305,093,289,500
// 8 pairs: 10,767.019,638,375
// 9 pairs: 58,835.098,191,875
// 10 pairs: 150,738,274,937,250
// 11 pairs: 205,552,193,096,250
// 12 pairs: 102,776,096,548,125
// 13 pairs: 7,905,853,580,625
//
//

public static void work()
{
System.out.println( "=== Number of combinations of m wires in Enigma plugboard having 26 letters ===" );

BigInteger numWires = BigInteger.ONE;

final BigInteger NUM_PLUGS = new BigInteger("26");

// try 1..13 wires in a plugboard of 26 letters
//
// NB: I once tried 14 instead of 13, and verified that we blew up with
// IllegalArgumentExceptioni when trying to call factorial(-2).

for( int i = 1; i <= 13; ++i)
{
String strPair = null;
BigInteger combinations = numPairs( NUM_PLUGS, numWires );
if (i == 1)
strPair = "pair";
else
strPair = "pairs";

// before we could rely on addComma() method, we print both without *and* with commas
// System.out.println( numWires + " " + strPair + ": " + combinations + " (" + addCommas(combinations.toString() ) + ")" );

// i pair(s): combinations_with_commas

System.out.println( numWires + " " + strPair + ": " + addCommas(combinations.toString() ) );
numWires = numWires.add( BigInteger.ONE );
}
System.out.println( "=== DONE ===" );

}

// return number of pairs of m objects from n total objects
//
// More abstractly: the number of ways of choosing m pairs out of n objects is:

// n! /((n-2m)! m! 2^m)
public static BigInteger numPairs( BigInteger n, BigInteger m )
{
final BigInteger TWO = new BigInteger( "2" );

BigInteger numerator = factorial( n );
BigInteger div1 = factorial( n.subtract( m.multiply( TWO )) ); // (n-2m) !
BigInteger div2 = factorial( m ); // m!

int mi = m.intValue(); // cannot do pow(BigInteger), must do pow(int)
BigInteger div3 = TWO.pow( mi ); // 2^m

BigInteger divisor = div1.multiply(div2.multiply(div3)); // div1*div2*div3

BigInteger result = numerator.divide( divisor );
return result;
}

// return n!, or "n factorial".
// 0! = 1
// 1! = 1
// 2! = 2*1
// 3! = 3*2*1
// 4! = 4*3*2*1
// ...
// n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
/**
* @return n!
* @throws IllegalArgumentException if n < 0.
*/

public static BigInteger factorial( BigInteger n )
{
// if n < 0 (ie, a netative number, then this is illegal)

if (n.compareTo( BigInteger.ZERO ) < 0)
throw new IllegalArgumentException( "factorial(" + n.toString() + ") attempted: you cannot use negative number" );

if (n.equals(BigInteger.ZERO))
return BigInteger.ONE;
if (n.equals(BigInteger.ONE))
return BigInteger.ONE;
BigInteger prod = BigInteger.ONE;

// prod = n * (n-1) ... * 3 * 2

while (! n.equals(BigInteger.ONE))
{
prod = prod.multiply(n); // prod = prod * n
n = n.subtract( BigInteger.ONE ); // n = n-1
}

return prod;
}

// add comma's to a decimal integer
// "" -> ""
// "1" -> "1"
// "12" -> "12"
// "123" -> "123"
// "1234" -> "1,234"
// "12345" -> "12,345"
// "123456 -> "123,456"

public static String addCommas( String number )
{
if (number.indexOf(".") != -1)
throw new IllegalArgumentException( "illegal decimal point found:" + number );

// TBD: maybe should check that only digits 0-9 are passed in number ??

// 3 or less digits is unchanged
if (number.length() <= 3)
return number;

// find index where first comma belongs

// find len of initial digits ( 4 -> 1, 5 -> 2, 6 -> 3)
int prefixLen = number.length() % 3;
if (prefixLen == 0)
prefixLen = 3;

int begInx = 0;
int endInx = prefixLen;

// put comma AFTER each group (not now)
String result = number.substring( begInx, endInx );
int remLength = number.length() - prefixLen;

// after first comma
begInx += prefixLen;
endInx += 3;

// remLen is now a multiple of 3, and we
// take 3 digits at a time, putting a comma in front of each 3 digits.

for (; remLength > 0; remLength -= 3)
{
// concatenate "," and next 3 digits
result += ( "," + number.substring( begInx, endInx ) );

// move to the next group of 3 digits
begInx += 3;
endInx += 3;
}

return result;
}
}

instead of 58,835.098,191,875 for 9 pairs, should stay 53,835.098,191,875