Solved

# Hill cipher - wrong result (Linear algebra)

Posted on 2003-03-13
Medium Priority
1,484 Views
Hi everyone,
I am writing a program to illustrate Hill's cipher.
My problem is that when I inverse the key matrix K,
I get a matrix that if I multiply it in K, I get
The identity matrix multuiplied with the determinant of K...
Can someone come up with an idea for this problem?
Here's the code:

/**
* This program uses static methods to be used for
* implementing Hill's cipher.
* @author Sweiry Itsik
*/
public class HillCipherFunctions
{
private static final int MOD_FACTOR = 26;
private static final int MAX_SIZE = 10;
private static final int MIN_SIZE = 2;

/**
* This function calculates the inverse number
* of the given x, mod 26.
* @param x The number to find the inverse of.
* @return The inverse number of x mod 26.
*/
public static short inv_26(long x)
{
// Will hold the number after mod MOD_FACTOR
short y;
// Will hold the gcd of y and MOD_FACTOR.
int gcd;
int i=0;
/* This helper would be used to calculate the inverse.
These are the only 5 multiplies of 26 (+1) that can give
us the inverse numbers, sorted according to efficiency.
This way we reduce complexity to be 1-5 steps, instead of
Using the Euclidean algorithm which would usually take more.
*/
int helper[] = {27,105,209,391,625};

// Deals with negative numbers.
y = modWithNegativeFix(x);
// Check gcd
gcd = gcd_26(y);

if (gcd != 1)
{
return 0;
}
while ((helper[i]%y)!=0)
{
// Go to the next element in helper.
i++;
}
return (short)(helper[i]/y);
}

/**
* Deals with the % sign for negative numbers.
* @param x The x to check and fix.
* @return The result of x%26.
*/
protected static short modWithNegativeFix(long x)
{
long y;
if (x < 0)
{
y = (x*(-1)) % MOD_FACTOR;
if (y != 0)
{
y = (y * (-1)) + MOD_FACTOR;
}
}
else
{
y = x % MOD_FACTOR;
}
return (short)y;
}

/**
* Finds the gcd of the given x and 26.
* @param x The number to find the gcd of (with 26).
* @return The gcd of x and 26.
*/
protected static int gcd_26(long x)
{
int y = MOD_FACTOR;
if (x==0)
{

// It is not relatively prime to 26.
return 0;
}
// GCD algorithm.
while (x != y)
{
if (x > y)
{
x -= y;
}
else
{
y -= x;
}
}
return (int)x;
}

/**
* Calculates the determinant of a given square function.
* @param m The number of rows and columns of the matrix.
* @param A The matrix.
* @exception IllegalArgumentException If m or A are illegal.
* @return The determinant mod 26.
*/
public static short determinant(int m,short A[][])
throws IllegalArgumentException
{
// Checks the arguments and throws exception if needed.
checkArgs(m,A);
// Uses calcDet as the recursion function.
long result = calcDet(m,A);
// Deals with negative results.
if (result < 0)
{
short helper = (short)((result*(-1)) % MOD_FACTOR);
if (helper != 0)
{
helper = (short)((helper * (-1)) + MOD_FACTOR);
}
return helper;
}
// Else - simply mod the result with 26.
else
{
return (short)(result % MOD_FACTOR);
}
}

// Checks the arguments for validity.
private static void checkArgs(int m,short A[][])
{
// Checks the input.
if (!(checkMatrix(A,m)))
{
throw new
IllegalArgumentException("Illegal matrix!");
}
if (m > MAX_SIZE || m < MIN_SIZE)
{
throw new
IllegalArgumentException("Wrong matrix size!");
}
}

// Determinant calculation using minors expansion.
private static long calcDet(int m, short A[][])
{
int i,j,j1,j2;
long result;
// Will hold the temp matrix.
short B[][] = new short[m][m];
// If A is 2x2, we know to calculate its determinant.
if (m==2)
{
return A[0][0] * A[1][1] - A[1][0] * A[0][1];
}
// A bigger than 2x2 matrix - use recursion to reduce it.
else
{
result = 0;
for (j1=0;j1<m;j1++)
{
for (i=1;i<m;i++)
{
j2 = 0;
for (j=0;j<m;j++)
{
if (j == j1)
{
continue;
}
// Creates the minor.
B[i-1][j2] = A[i][j];
j2++;
}
}
// Calculates the determinant - (+/-)1 * A[0][j1] * |B|
result += Math.pow(-1.0,(1.0+j1+1.0)) *
A[0][j1] *
calcDet((short)(m-1),B);
}
}
return result;
}

// checks the matrix to see if it has out of range elements.
// Returns false if it's illegal, true otherwise.
private static boolean checkMatrix(short[][] matrix,int m)
{
int i,j;
for (i=0;i < m;i++)
{
for (j=0;j < m;j++)
{
if (matrix[i][j] > 25 || matrix[i][j] < 0)
{
return false;
}
}
}
return true;
}

// Finds the inverse of a given matrix.
// Returns null if the matrix is not invertible.
/**
* Returns the inverse matrix of the given matrix.
* @param m The number of rows and columns of the matrix.
* @param A The matrix to inverse.
* @return the inverse matrix of A, or null if there isn't one.
* @exception IllegalArgumentException If m or A are illegal.
*/
public static short[][] inv_matrix(int m,short A[][])
throws IllegalArgumentException
{
// Checks the args and throws exceptions if necsessary.
checkArgs(m,A);
if (m == 2)
{
return findInverseFor2x2Matrix(A);
}
short B[][] = new short[m][m];
long detA = modWithNegativeFix(calcDet(m,A));
if (!isInvertible(detA))
{
return null;
}
// Else - Do the inverse finding algorithm.
// Finds the adjoint matrix of A, and stores it in B.
// Finds the inverse of the matrix,using:|A|'s inverse*adjA
multMatrixByFactor(B,m,inv_26(detA));
return B;
}

// Finds the inverse for a 2x2 matrix.
private static short[][] findInverseFor2x2Matrix(short[][] A)
{
short temp;
// Calcs the determinant and finds the modulos of it.
long detA = modWithNegativeFix(calcDet(2,A));
// Checks if the matrix is invertible.
if (!isInvertible(detA))
{
return null;
}
// Interchanging diagonal elements.
temp = A[0][0];
A[0][0] = A[1][1];
A[1][1] = temp;
// Changing signs of the other 2.
A[0][1] *= -1;
A[0][1] = modWithNegativeFix(A[0][1]);
A[1][0] *= -1;
A[1][0] = modWithNegativeFix(A[1][0]);
// Multiply A by 1/|A| to get the inverse.
return (multMatrixByFactor(A,2,(inv_26(detA))));
}

// Checks if a given determinant represents an invertible matrix.
private static boolean isInvertible(long determinant)
{
// Checks if the matrix is invertible.
return (gcd_26(determinant) == 1);
}

/**
* Transposes A and returns the transposed matrix.
* @param A The matrix to transpose.
* @param m The number of rows and cols of the matrix.
* @return The A matrix transposed.
* @exception IllegalArgumentException If m or A are illegal.
*/
public static short[][] transposeMatrix (short A[][],int m)
throws IllegalArgumentException
{
// Checks the args and throws exception if necessary.
checkArgs(m,A);
int i,j;
short dest[][] = new short[m][m];
for (i=0; i < m;i++)
{
for (j=0; j < m;j++)
{
// Transposes the matrix.
dest[j][i] = A[i][j];
}
}
return dest;
}

/**
* Finds the adjoint matrix of the given matrix.
* @param A The matrix to find the adjoint of.
* @param m The number of rows and Columns.
* @return The adjoint matrix of A.
* @exception IllegalArgumentException if A or m are illegal.
*/
public static short[][] findAdjoint(short A[][],int m)
{
short i,j;
for (i=0;i < m;i++)
{
for (j=0;j < m;j++)
{
// Finds the minor(and cofactor)of the current element.
(findMinorAndCof(A,i,j,m));
}
}
// The adjoint matrix is a transpose of the cofactors.
}

// Finds the minor (and cofactor) of the current element.
private static long findMinorAndCof
(short[][] matrix,short row,short col,int m)
{
// Holds the indices and the position in the source matrix.
short i,j;
// realI,realJ will hold the position in the temp matrix.
short realI,realJ;
// Holds the matrix to calculate determinant on.
short temp[][] = new short[m-1][m-1];
// Holds the determinant of temp.
long result;
for (i=0,realI=0;i < m; i++)
{
// Ignores the given row.
if (i != row)
{
for (j=0,realJ=0;j < m;j++)
{
// Ignores the given column.
if (j != col)
{
// Puts the element and increments realJ.
temp[realI][realJ] = matrix[i][j];
realJ++;
}
}
// Increments realI only if it's not the given row.
realI++;
}
}
// Stores the determinant of temp in result.
result = calcDet((short)(m-1),temp);
// Checks the cofactor and returns the modified result.
if (((row+col)%2) == 0)
{
return result;
}
// Else.
return result * -1;
}

// Multiplies the given matrix by the given factor.
private static short[][] multMatrixByFactor
(short A[][],int m,short factor)
{
int i,j;
short temp[][] = new short[m][m];
for (i=0;i < m;i++)
{
for (j=0;j < m;j++)
{
// Multiplies each element with the factor
temp[i][j]=(short)((factor * A[i][j]));
}
}
return temp;
}

/**
* Prints the given matrix to the standard output.
* @param A The matrix to print.
* @param m The number of rows and columns of the matrix.
*/
public static void printMatrix(short[][] A,int m)
{
int i,j;
for (i=0;i < m;i++)
{
System.out.print("\n");
for (j=0;j < m;j++)
{
System.out.print(A[i][j] + "\t");
}
}
System.out.print("\n");
}
}
0
Question by:JavaInTheMorning
• 2

LVL 3

Author Comment

ID: 8132101
Sorry for the long code...
The problem is when I call the function:

inv_matrix(m,A),m;

Where A is:
1 15 5
24 11 16
25 7 10

and the result comes out: (B)
24 15 3
4 15 0
23 4 15

(A*B)=I*|A| = I*17

(remember that everything in here is modulos 26).

THANKS!
Itsik

0

LVL 2

Accepted Solution

JonathanJonas earned 2000 total points
ID: 8132465
Hello Itsik,

One quick question - what is your expected output in the example which you give above?

Is it:

552     345     69
92      345     0
529     92      345

I got this output after compiling your code and changing one line in the inv_matrix method.

I changed:

multMatrixByFactor(B,m,inv_26(detA));

to

B = multMatrixByFactor(B,m,inv_26(detA));

Does that make sense?

Cheers,

Jonathan
0

LVL 3

Author Comment

ID: 8143740
Already answered my own stupidity... I figured that out, but you deserve the points just for the headache...
Thanks,
Itsik
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
###### Suggested Courses
Course of the Month9 days, 4 hours left to enroll