java - Find number coprime to modulus -

i've been doing research on rsa encryption system, it's pretty simple code 1 using small primes, there aren't many possibilities , performance not real issue.

here's how rsa works:

• first, generate n value, product 2 primes picked randomly:

  n = p * q 

  • then need public key, called e. can number coprime φ(n):

    mcd(φ(n), e) = 1

  • according euler function, φ(n) = (p-1)(q-1)

  • you still need private key, known d, inverse of e on modulo **φ(n).

  • so d * e = 1 (mod φ(n))

  • n , e public values, when d private key. nobody should know p or q, values possible φ(n), , use calculate d.
• to encrypt message, use m = m^e (mod n), m original message, , m encrypted one. so, can send encrypted message can read, using public values.
• to decrypt message, use d, it's inverse of e, m^d = (m^e)^d = m (mod n). message can decrypted, using d.

knowing this, encrypt message need 2 random primes, calculate n, e, d, , make our encryption , decryption methods.

---

this seems pretty easy in theory, let's turn java code:

i first choose 2 random primes, bigger number, stronger encryption. i'll choose p = 1644623 , q = 1644751. according this page, primes.

biginteger p = new biginteger("1644623"); biginteger q = new biginteger("1644751"); 

then, on init method, initialize n, e , d:

biginteger p = new biginteger("1644623"); biginteger q = new biginteger("1644751");  biginteger n; biginteger e; biginteger d;  void init() {     n = p.multiply(q);      biginteger pn = p.subtract(biginteger.one).multiply(q.subtract(biginteger.one));      e = n.subtract(pn);     while (!mcd(pn, e).equals(biginteger.one)) {         e = e.add(biginteger.one);         system.out.println(e);     }      d = e.modpow(new biginteger("-1"), pn); } 

i used biginteger instead of long, values used extremely big.

in theory, works. practically, pn = 2704992034500, checking if mcd(pn, e) = 1, , if not adding 1 e , trying again it's not option. program running since 30 minutes, @ average of 150.000 numbers / second. e = 548151505 , still not found mcd(pn, e) = 1.

---

is there way find e in reasonable time?

---

any prime number co-prime modulus, definition, don't need search one, pick prime number. since encryption key public, rsa implementations use makes easy compute modular exponentiation: 3 , 65537 = 2 ** 16 + 1 both prime, , both commonly used encryption key.