How can you be sure that (p-1)(q-1)+1 is not prime?

[mtanti]

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?

 

[Hurkyl]

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)).

 

[saltydog]

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.