?
Solved

Hill cipher - wrong result (Linear algebra)

Posted on 2003-03-13
3
Medium Priority
?
1,471 Views
Last Modified: 2007-12-19
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.
            B = findAdjoint(A,m);
            // 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;
            short adj[][] = new short[m][m];
            for (i=0;i < m;i++)
            {
                  for (j=0;j < m;j++)
                  {
                  // Finds the minor(and cofactor)of the current element.
                        adj[i][j]=modWithNegativeFix
                                                      (findMinorAndCof(A,i,j,m));
                  }
            }
            // The adjoint matrix is a transpose of the cofactors.
            return (transposeMatrix(adj,m));
      }
      
      // 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
Comment
Question by:JavaInTheMorning
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 3

Author Comment

by:JavaInTheMorning
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

by:
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

by:JavaInTheMorning
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

Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

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 …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
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…
This video teaches viewers about errors in exception handling.
Suggested Courses
Course of the Month9 days, 23 hours left to enroll

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question