Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to solve a problem involving modulus

  1. Mar 2, 2013 #1
    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?

    A few helpful points:
    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. jcsd
  3. Mar 2, 2013 #2

    chiro

    User Avatar
    Science Advisor

    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.
     
  4. Mar 3, 2013 #3
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook