# How to solve a problem involving modulus

1. Mar 2, 2013

### hackish

Even though this deals with programming an encryption algorithm I feel this is more math based so I'm asking it here.

x=((y mod 380951)*3182) mod 380951

How can I solve for y?

1) the math involved here is limited to integers, so for example division by 3182 must result in an integer.
2) the number 380951 is a prime number.
3) the result must be smaller than 2^24
4) 3182-1 is also prime but I don't think this helps the solution.
5) x is an integer in the range of 0..2^16

I've read all the wiki pages on fermat's little theorem and the extended euclidean algorithm but the concepts they describe are beyond my math abilities.

I understand that there are multiple correct answers to this: EX:
y=291905 ;x=83172
or
y=1434758;x=83172

The first one will do and would be preferred since it has the greatest chance of fitting within the 24 bit result.

At present I've been exhaustively calculating it by trying every possible multiple of the prime number + the result / 3182 and it works so I know a solution is possible. Relating to the example above if you multiply 380951*2834+83172 gives 928841710 then divide by 3182 gives 291905.

Can anyone give steps to calculate the answer I need?

2. Mar 2, 2013

### chiro

Hey hackish and welcome to the forums.

You may want to try writing y as y = pq + r where p = 380951 and r is between 0 and 380950 inclusive.

Then do the same sort of thing for the outer modulus and bring the results together.

3. Mar 3, 2013

### hackish

Ok, someone else solved it... thanks.
Turns out you can apply (3182^(380951-2)) mod 380951 then multiply that by x, then mod 380951 and you get y.

Wow. A little math wizardry and encrypting a file now takes 250ms instead of 23 minutes.

Last edited: Mar 3, 2013