Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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$. – fgrieu Dec 28 '13 at 16:45
Random is the accepted method? Whether RSA uses random method? – user5507 Dec 28 '13 at 16:49
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. – fgrieu Dec 28 '13 at 17:00
@fgrieu, would you mind answering this question so it can get off our "unanswered questions" statistique? – SEJPM Jun 28 '15 at 18:51

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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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