I am implementing a protocol for authentication where parameters need to be selected with $gcd(\mu,\phi)=1$ where $\phi=(p−1)(q−1)$. What is the best way to select the parameters while implementing

  • $\begingroup$ In the context, do you know $\phi$? If yes, one way could be to select (odd) $\mu$ at random until $\gcd(\mu,\phi)=1$ is satisfied. Or if that fits, just $\mu=1$. $\endgroup$
    – fgrieu
    Dec 28, 2013 at 16:45
  • $\begingroup$ Random is the accepted method? Whether RSA uses random method? $\endgroup$
    – user5507
    Dec 28, 2013 at 16:49
  • $\begingroup$ When there is nothing else specified, random can be an accepted method. In particular, it is fine to choose an RSA exponent at random that is coprime with $\phi=(p−1)(q−1)$. If that needs to be done for unknown $\phi$, one option is to select primes $p$ and $q$ of same bit size such that $(p-1)/2$ and $(q-1)/2$ are primes, making an overwhelming majority of odd $\mu$ with $3\le\mu<N-3\sqrt N$ suitable. $\endgroup$
    – fgrieu
    Dec 28, 2013 at 17:00
  • $\begingroup$ @fgrieu, would you mind answering this question so it can get off our "unanswered questions" statistique? $\endgroup$
    – SEJPM
    Jun 28, 2015 at 18:51

1 Answer 1


I'll first assume $\phi$ is known, which would be the situation in RSA at key selection.

A common method could be to select (odd) $\mu$ at random in some appropriate interval until $\gcd(\mu,\phi)=1$ is satisfied. In the context of RSA, it is fine (if we ignore performance an interoperability issues) to choose an RSA exponent at random in $[3\dots\phi-3]$ that is coprime with $\phi=(p−1)(q−1)$.

Another option would to restrict to prime $\mu$, which increases the odds that $\gcd(\mu,\phi)=1$: for random choice of large primes $p$ and $q$, a moderate prime $\mu$ has odds $({\mu-2\over\mu-1})^2$ to be acceptable. For example, $\mu=65537$ (the most common choice for RSA) would likely be fine.

When candidates for $\mu$ are examined in prescribed order, from the choice of $\mu$ a little information leaks about $\phi$; this is usually a non-issue.

If we somewhat must arrange that $\mu$ be chosen without knowledge of $\phi=(p-1)\cdot(q-1)$, one option is to select distinct primes $p$ and $q$ of some bit size $b$ such that $(p−1)/2$ and $(q−1)/2$ are primes; in this way, any odd $\mu$ less than $b-1$ bits verifies $\gcd(\mu,\phi)=1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.