This is needed because I use a random function to generate the encryption key in RSA setting to generate random numbers and check if $\gcd$ is $1$.

  • 2
    $\begingroup$ Are you asking that probability for uniformly random $e$ and fixed $n$? If so, that probability can be computed from the list of distinct odd primes factors in the factorization of $\varphi(n)$. Use that the probability of a large random $e$ being divisible by prime $r$ is $1/r$. On the other hand, If $n$ is not fixed, or if the factorization of $\varphi(n)$ is not known, then you need some model of the distribution of $n$ or $\varphi(n)$. Notice that practice in modern RSA is to first chose $e$, then generate the factors of $n$ such that $\gcd(e,\varphi(n))=1$. $\endgroup$ – fgrieu Jan 30 '19 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.