You are Here: Home >< Maths

# I think this question is on congruences and RSA watch

1. I missed a whole load of lectures as I was ill and now I am behind on some work. I am trying to catch up but I have come across this question which I haven't got a clue how to do:

A public key code has base n = 564146777 and encoding exponent a = 282044381.

i) Factorize n and calculate ?(n)
ii) Calculate the decoding exponent x (i.e a^(-1) mod ?(n) )
iii) Decode the following received message using the letter to number equivalents in the attached table (p4). Each block corresponds to a sequence of one or two letters; thus, since 10 corresponds to A and 11 to B, 1011 stands for AB, etc.

366514996 / 506479715 / 239338918 / 85377691

For part one, I assumed factorizing it meant in terms of its primes and I got n = (45691)(46777) and so I got ?(n) to be 564088740.

Then I am completely stuck for part 2. I looked over the lecture notes and I don't have a clue what is going on. Could someone please either show me, or give me a real push (not nudge lol) in the right direction because I am really struggling with this. I am assuming that I should be able to do part 3 if I can do part 2, but if you could give me a tiny hint on how to do that I would much appreciate it.

Thank you very much
2. So for part (ii) you need to find the inverse of a mod P (where P = ?(n)).

The extended Euclidean algorithm lets you find m and n s.t. 1 = ma + nP. But then 1=ma mod P, so m is an inverse for a.

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: April 3, 2011
Today on TSR

### Summer Bucket List is Back!

Start yours and you could win £150!

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams