φ(n) = (p-1)(q-1) p and q are two big numbers find e such that gcd(e,φ(n)) = 1 [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

φ(n) = (p-1)(q-1) p and q are two big numbers find e such that gcd(e,φ(n)) = 1

consider p and q to be a very large prime number (Bigint). I want to find a efficient solution for this.

[Edit] I can solve this using a brute force method. But as the numbers are too big I need more efficient solution. also 开发者_JAVA百科1< e < (p-1)(q-1)

---

Usually you choose e to be a prime number. A common choice is 65537. You then select p and q so that gcd(p-1, e)=1 and gcd(q-1, e)=1, which just required you to check that p-1 and q-1 are not multiples of e (when you (rarely) find that one of them is, you generate a new prime instead).

65537 has the advantage of allowing you to optimize the public key operation by observing that x^65537 = x^(2^16+1) = x^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2^2 * x (mod m), so you just need 16 modular squarings and a modular multiplication.

---

You have to decide how big you want e to be. This is a system decision. Commonly, e used to be fixed at 3; more usual nowadays is e=65537. In these cases, e is prime, so (as others have already pointed out) you just have to check that (p-1)(q-1) is not a multiple of e.
But some system requirements specify a 32-bit random e. This is because some cryptographers feel that flaws are more likely to be discovered in fixed-exponent RSA systems than in random-exponent systems. (As far as I know, no concrete exploitation has been discovered for fixed-exponent systems; but cryptographers are paid to be over-cautious.)
So let's say you're stuck with having to generate a random 32-bit e that is co-prime to (p-1)(q-1). The simplest solution is this: Generate a random, odd 32-bit number e. Then calculate its inverse mod (p-1)(q-1). If this inverse calculation fails, because e is not co-prime to (p-1)(q-1), then try again.
This is a reasonable, practical solution. You will need to calculate the inverse anyway, and computing an inverse doesn't take much longer than computing a gcd.
If you really need to make it as fast as you can, you can look for small prime factors of (p-1)(q-1) and trial-divide e by these factors: if you find small prime factors, then you can speed up your search for e; if you don't, then the search will probably terminate quickly.
Another reasonable soltuion is to generate a random 32-bit prime e, and check (p-1)(q-1) for divisibility by e. Whether this is allowed would depend on your system requirements. Are you setting these system requirements yourself?

---

Pick first prime number >= 3 that satisfies this. If you are looking for speed, you might use small exponent.

There might be two problems whit 2 exponents.

• You should not use small exponents to encrypt same massage whit multiple schemes. (for instance if there are tree private/public pairs whit exp = 3 you can use Gauss’s algorithm to recover plaintext.

• You should not send short messages because attacker might use only cube root to recover this.

Considering these weaknesses you might use this scheme. And as far as I know number 3 is common number for e.

By the way, brute forcing few numbers is negligible compared to checking for primality.

---

I think you may have misstated the problem; e=1 works nicely for the one you've written.

---

What you need to do then is compute de = 1 mod phi(n). This is actually very quick - you simply need to use the extended Euclidean Algorithm on e and phi n. Doing so will allow you to compute de + k\phi(n) = 1 which is to say you have computed the inverse of e under \phi(n).

Edit, Rasmus Faber is correct, you do need to verify that gcd(e, \phi(n)) = 1. The extended Euclidean Algorithm will still do this for you - you compute both the gcd and the multiples of e, phi(n). This tells you what d is, namely that d is the inverse of e, modulu phi n which tells you that t^ed = t^1 modulo phi n.

As for doing this in practice, well, I strongly suggest using a bignum library; rolling your own arbitrary precision euclidean extended algorithm isn't easy. Here is one such function that will do this efficiently for arbitrary precision arithmetic.