Timeline for Is knowing the private key of RSA equivalent to the factorization of $N$?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2022 at 22:12 | comment | added | 111 | yes it works for $\lambda(N).$ In fact, there is a simple presentation of an algorithm, with input a multiple of $\lambda(N)$ and output the factorization of $N,$ (probabilistic and without assuming GRH), in Victor Shoup's book, section 10.4 [shoup.net/ntb/ntb-v2.pdf]. Also there are many reference and history about the problem. Note that the deterministic (but conditional) algorithm of Miler can be found here [dl.acm.org/doi/abs/10.1145/800116.803773]. | |
| Sep 21, 2022 at 7:06 | comment | added | Mahdi Mahdavi | Thank you for your answer. Does this algorithm work if the public-private key pair is selected in $\lambda(N)$? This algorithm is probabilistic. isn't it? I also really appreciate it if you send the paper or thesis that expresses the time order of this algorithm $O((log_2N)^4)$. | |
| Sep 20, 2022 at 13:35 | comment | added | 111 | @MahdiMahdavi Note that, if $m$ is a multiple of $\phi(N),$ then $a^{m}\equiv 1\pmod {N}$ and so you can apply the previous Probabilistic algorithm. Now, assuming GRH, you can avoid the probabilistic approach, and get a deterministic algorithm. For the latter I think you can find it in the phd of Gary Miller. | |
| Sep 18, 2022 at 19:26 | comment | added | Mahdi Mahdavi | Please mention the reference that if we know a multiple of $\phi(N)$ then we can factor $N$ in time $O((log_2N)^4)$. The order of time is important to me. | |
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/
|
|
| Jan 24, 2017 at 20:01 | history | edited | e-sushi | CC BY-SA 3.0 |
added 49 characters in body
|
| Jan 24, 2017 at 2:33 | history | answered | 111 | CC BY-SA 3.0 |