Φ (n) = (p-1) (q-1) p and q are two large numbers found by e such that gcd (e, φ (n)) = 1

Question

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

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

[Edit] I can solve this using brute force. But since the numbers are too large, I need a more efficient solution. also 1 <e <(P-1) (Q-1)

Answer 1

Usually you choose e as a prime number. The general choice is 65537. Then you 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, you generate a new number instead).

65537 has the advantage that you can optimize the performance of the public key 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 quadratic modules and modular multiplication.

Answer 2

You must decide how big you want to be. This is a system solution. Usually e is used to fix at 3; e = 65537 is currently more common. In these cases, e is simple, so (as others have already pointed out) you just need to check that (p-1) (q-1) is not a multiple of e.
But some system requirements define 32-bit random e. This is because some cryptographers believe that flaws are more likely to be detected in RSA systems with a fixed metric than in systems with an arbitrary metric. (As far as I know, no specific exploitation has been found for fixed-rate systems, but cryptographers pay for extreme caution.)
So, let's say you are stuck in generating a random 32-bit e, which is compatible with (p-1) (q-1). The simplest solution: create a random, odd 32-bit e. Then we calculate its inverse mod (p-1) (q-1). If this reverse calculation fails because e is not compatible with (p-1) (q-1), try again.
This is a reasonable, practical solution. In any case, you will need to calculate the inverse, and calculating the inversion will not take much longer than calculating the gcd.
If you really need to do this as fast as you can, you can look for small simple coefficients (p-1) (q-1) and trial separation e by these factors: if you find small basic factors, then you can speed up the search e; if you do not, the search will most likely stop quickly.
Another reasonable solution is to create a random 32-bit prime e and check (p-1) (q-1) for divisibility by e. Whether this is allowed depends on your system requirements. Do you set these system requirements yourself?

Answer 3

Select the first prime number> = 3 that satisfies this. If you are looking for speed, you can use a small indicator.

There may be two problems with two indicators.

• You should not use small exponents to encrypt the same massage with multiple patterns. (for example, if there are private / private pairs of the tree whit exp = 3, you can use the Gauss algorithm to recover plaintext.

• You should not send short messages because an attacker can only use the cubic root to recover this.

Given these shortcomings, you can use this scheme. And as far as I know, number 3 is the total number for e.

By the way, the crude forcing of several numbers is negligible compared to the primitive test.

Answer 4

I think you may have made a mistake in the problem; e=1 works great for the one you wrote.

Answer 5

What you need to do is compute de = 1 mod phi (n). This is actually very fast - you just need to use the advanced Euclidean algorithm on e and phi n. This will allow you to calculate de + k \ phi (n) = 1, i.e. you calculated the inverse of e under \ phi (n).

Edit, Rasmus Faber is correct, you need to check that gcd (e, \ phi (n)) = 1. The advanced Euclidean algorithm will still be for you - you calculate both gcd and the multiplicity e, phi (n). This tells you what d is, namely, that d is inverse to e, modulu phi n, which tells you that t ^ ed = t ^ 1 modulo phi n.

Regarding this in practice, I highly recommend using the bignum library ; Promoting your own arbitrary algorithm with an extended Euclidean value is not easy. Here is one such function that will do this effectively for arbitrary precision arithmetic.