Timeline for Can $d$ and $e$ be the same number in RSA?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 28, 2016 at 13:06 | history | suggested | wythagoras | CC BY-SA 3.0 |
let the answer quote match the question
|
| May 28, 2016 at 12:29 | review | Suggested edits | |||
| S May 28, 2016 at 13:06 | |||||
| May 22, 2016 at 21:04 | vote | accept | eightShirt | ||
| May 22, 2016 at 9:37 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
gcd->lcm
|
| May 22, 2016 at 4:27 | comment | added | user94293 | @poncho: $\lambda(N) = \operatorname{lcm}(p-1,q-1) = (p-1)(q-1)/\gcd(p-1,q-1) = \phi(N)/\gcd(p-1,q-1)$. Public exponent $e$ should be chosen co-prime to $(p-1)$ and $(q-1)$ so that it has an inverse modulo $(p-1)$ and $(q-1)$. Being co-prime to $(p-1)$ and $(q-1)$ is equivalent to being co-prime to $\phi(N) = (p-1)(q-1)$; it is also equivalent to being co-prime to $\lambda(N) = \operatorname{lcm}(p-1,q-1)$. | |
| May 22, 2016 at 0:42 | comment | added | eightShirt | @poncho: Thanks. Just one more question: can I say 'between $1$ and $phi$ I will always have a valid candidate to be $e$' [not just here]? Why that explanation that "$e$ have to be a coprime between $1$ and $phi$" are in so many places? :-( | |
| May 22, 2016 at 0:24 | comment | added | poncho | @eightShirt: technically, negative values of $e$ could be made to work (as you can compute the inverse without knowing the factorization); of course, there's absolutely no reason to do this... | |
| May 22, 2016 at 0:23 | comment | added | poncho | @user94293: "relatively prime to $lcm(p-1,q-1)$" is yet another equivalent way of stating it. | |
| May 21, 2016 at 23:49 | comment | added | user94293 | @poncho: Relatively prime to both $p-1$ and $q-1$ (or equivalently, relatively prime to $\operatorname{lcm}(p-1,q-1)$). | |
| May 21, 2016 at 23:46 | comment | added | eightShirt | mdc = gdc. I see it here: doc.sagemath.org/html/en/thematic_tutorials/numtheory_rsa.html. "$e$ have to be a positive number that $gdc(e, phi) = 1$". Is not right? | |
| May 21, 2016 at 23:17 | history | answered | poncho | CC BY-SA 3.0 |