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

RSA Algorithm

  1. Aug 20, 2006 #1
    How is it that you calculate e and d such that ed=(p-1)(q-1)+1? Isn't this a factoring problem?

    How can you be sure that (p-1)(q-1)+1 is not prime?
  2. jcsd
  3. Aug 20, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You're interested in ed = k(p-1)(q-1) + 1.
    The whole point is that you're looking for ed = 1 (mod phi(N)).
  4. Aug 25, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    In case you don't already know, the program 'PARI' on the web is nice for working with number theory and some of the algorithms of RSA in general. Anyway, I used it, in conjunction with Mathematica's 'PowerMod' to easily encrypt a paragraph using two 256-digit primes (found by PARI).

    Check um' out.:smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook