# RSA encryption, Number theory [duplicate]

In RSA algorithm we have the value of $$e$$ & $$d$$ exponent and also one of the prime numbers. My question is how to produce another prime number that is not equal to the first one and the digit of a prime number is 1024.

• Do I understand correctly that you have $e$, $d$, and $p$, but not $n$ or $q$, and you want to find some $q$ so that $ed \equiv 1 \pmod{\phi(pq)}$? – Squeamish Ossifrage Jun 4 '19 at 18:02
• I have just the value of e, d, p and I want to find the exact q so that ed≡1(modϕ(pq)) – Aida Jun 7 '19 at 10:25

Here's the problem: you have values $$e, d, p$$ that satisfy the relation:

$$ed - 1 = k(p-1)$$

for some integer $$k$$; what you want to do is find some other prime $$q$$ (within some size range) that satisfies the relation:

$$ed - 1 = k'(q-1)$$

(for some integer $$k'$$)

Without this first relation, finding the second one would be difficult (as we would need to find a 1024 bit factor in $$ed-1$$, and that's difficult), however by leveraging the first relation, it is practical.

Here's one way to proceed:

• Compute $$k = (ed - 1)/(p - 1)$$, and then obtain a partial factorization (that is, find all the prime factors below a smoothness bound $$M$$ of both $$k$$ and $$p-1$$); namely:

$$p - 1 = p_0 p_1 p_2 … p_n c$$

$$k = p'_0 p'_1 p'_2 … p'_{n'} c'$$

(for prime $$p_0, p_1, …, p_n, p'_0, p'_1, …, p'_{n'}$$, and integers $$c, c'$$ with no prime factors $$< M$$)

Then, iterate through the various subsets of the values $$c', p_0, p_1, …, p_n, p'_0, p'_1, …, p'_{n'}$$, for a subset which:

• The product $$q-1$$ of the elements of the subset is within the size range

• One more than the product ($$q$$) is prime.

A value $$q$$ that satisfies both above relations is a valid possibility for the prime you're looking for (and there may be multiple).

This will always succeed if there is such a $$q$$ (that is, your $$e, d, p$$ values came from a valid RSA key), and if $$\gcd( p-1, q-1 ) < M$$ (which is likely to be the case if $$p, q$$ were not specially selected to have a large gcd).