Suppose $p$ and $q$ are two prime numbers. How can one quickly calculate how many numbers $x$ there are such that $\gcd(x, (q-1)\cdot(p-1)) = 1$, without using brute force?
how to find co-prime numbers
1
$\begingroup$
cryptography
-
4The number is infinite; presumably you mean how many *positive* numbers *strictly smaller* than some bound; for those smaller than $(p-1)(q-1)$ you can use Euler's totient function, provided you can factor $p-1$ and $q-1$. – 2010-10-11
1 Answers
3
The answer is $\phi((q-1)(p-1))$, but to compute that you probably need to factor $p-1$ and $q-1$.
-
1For any positive integer $n$ given $\phi(n)$ the factorization of $n$ can be found in probabilistic polynomial time or deterministically under the Extended Riemann Hypothesis. See for example http://rjlipton.wordpress.com/2011/12/10/a-lemma-on-factoring/ for the main idea. – 2013-03-26