title: Calculate primes p and q from private exponent (d), public exponent (e) and the modulus (n)
body: <p>How do I calculate the p and q parameters from e (publickey), d (privatekey) and modulus? </p>
  
  <p>I have BigInteger keys at hand I can copy paste into code. One publickey, one privatekey and a modulus.</p>
  
  <p>I need to calculate the RSA parameters p and q from this. But I suspect there is a library for that which I was unable to find with google. Any ideas? Thanks.</p>
  
  <p>This does not have to be brute force, since I'm not after the private key. I just have a legacy system which stores a public, private key pair and a modulus and I need to get them into c# to use with RSACryptoServiceProvider.</p>
  
  <hr>
  
  <p>So it comes down to calculating (p+q) by</p>
  
  <pre><code>public BigInteger _pPlusq()
      {
          int k = (this.getExponent() * this.getD() / this.getModulus()).IntValue();
  
          BigInteger phiN = (this.getExponent() * this.getD() - 1) / k;
  
          return phiN - this.getModulus() - 1;
  
      }
  </code></pre>
  
  <p>but this doesn't seem to work. Can you spot the problem?</p>
  
  <hr>
  
  <p>5 hours later... :)</p>
  
  <p>Ok. How can I select a random number out of Zn* (<a href="http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n</a>) in C#? </p>