Given integers $N$ (modulus), $e$ (public exponent), and $d$ (private exponent), how would I find the primes $p$ and $q$ that compose $N$? I'm trying to do this in Python. This is homework.
1
-
$\begingroup$ Dupe crypto.stackexchange.com/questions/11509/… and crypto.stackexchange.com/questions/22374/factors-of-rsa-modulus (except the specific programming language, which is offtopic for crypto) $\endgroup$– dave_thompson_085Commented Dec 4, 2017 at 22:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If you want to recover the primes $p,q$ from $(N,e,d),$ note that $L = ed - 1$ is a multiple of the Carmichael function $\lambda(N).$
Assuming your data is from a valid RSA setting, then $N$ is odd and square-free and there is a probabilistic algorithm to compute $p,q$ from $N,L\;$ see e.g. the solutions for J. v. zur Gathen, J. Gerhard, Modern computer algebra, 2nd ed., 2003: Algorithm 18.16 (Special integer factorization) in https://cosec.bit.uni-bonn.de/fileadmin/user_upload/science/mca/solutions.pdf.
BTW: You can't factor primes (or the factorization is trivial).
answered Dec 4, 2017 at 9:08