Matrices and Modulus

pcmattman · Post by **pcmattman** » Sat Apr 21, 2007 12:31 am

I need assistance. Can anyone tell me what the inverse of the matrix

| 7 2 |
| 1 1 |
( lol ascii art )

is, in mod 26? I know the determinant is 5, so I just need to find a number that I can multiply 5 by to get 1 (mod 26). The problem is, it can't be a float because it's working towards a decryption matrix... It has to be an integer.

Any ideas? I'm sure there's at least one maths genius out there

.

Zekrazey1 · Post by **Zekrazey1** » Sat Apr 21, 2007 12:59 am

so I just need to find a number that I can multiply 5 by to get 1 (mod 26)

21?

pcmattman · Post by **pcmattman** » Sat Apr 21, 2007 1:03 am

Hey, that's correct! Thanks so much!

How on earth did you figure that out?

Edit: wait. It's not right. The inverse of the initial matrix comes out as

Code: Select all

| 21 10 |
| 5  17 |

Multiplying against the initial matrix should return the identiy matrix:

Code: Select all

| 1 0 |
| 0 1 |

But it doesn't... Any ideas? I've been at this for a day and a half and it's sending me crazy.

Zekrazey1 · Post by **Zekrazey1** » Sat Apr 21, 2007 1:17 am

Algebra + search with pruning:

5 * x = 26 * y + 1

Well, 26 * y has to end in either of the digits 4 or 9 (since 5 * anything always ends in 0 or 5, talking decimal here of course). 9 is out of the question, which just leaves 4, for which we can pick any number with last digit as 4, e.g. y = 4 => x = (1 + 26 * 4)/5 => x = 21.

.

Zekrazey1 · Post by **Zekrazey1** » Sat Apr 21, 2007 1:31 am

Wait a second, multiplying them does come out to the identity.

21 10 7 2
5 17 1 1

=
21 * 7 + 10 * 1 21 * 2 + 10 * 1
5 * 7 + 17 * 1 5 * 2 + 17 * 1

=
157 52
52 27

=
26 * 6 + 1 26 * 2 + 0
26 * 2 + 0 26 * 1 + 1

=
I (given mod 26)

pcmattman · Post by **pcmattman** » Sat Apr 21, 2007 1:35 am

I can't get that:

Code: Select all

| 105 0 |
| 0 105 |

I'm seriously confused.

Zekrazey1 · Post by **Zekrazey1** » Sat Apr 21, 2007 1:37 am

How are you multiplying your matrices? What do you end up with?

pcmattman · Post by **pcmattman** » Sat Apr 21, 2007 1:45 am

Hey. I just got it! I took the inverse of the initial value and found the value of it in mod 26... I used this: http://wims.unice.fr/wims/wims.cgi.

Now, I just have to figure out why it didn't work every other time

Edit: oh. I just found out. I forgot about mod 26.

Zekrazey1 · Post by **Zekrazey1** » Sat Apr 21, 2007 1:55 am