3
$\begingroup$

In a recent post on Crypto.SE, I argued that the probability that at least one pair of really large, uniformly random integers ($>2^{100,000,000}$) from a set of size $k$ is coprime is

$$1-(1-6/\pi^2)^{\frac{k(k-1)}{2}}$$

In the comments the point was made that taking the GCD over all integers in the set should yield a strictly better probability than the pair-wise approach I used. As the probability in this case would be $1/\zeta(k)$ as per Wikipedia, my result is clearly wrong, especially considering that "my" probability approaches $1$ strictly faster for $k>2$.

Now I have to ask:
Where's the flaw in my thought process and how can I correct it?


Here's my argumentation, so you don't have to follow the link to Crypto.SE.

The first thing to observe or assume is that the values of $r_i$ are random non-zero integers. Due to their large size (beyond $2^{100,000,000}$), I will model them as randomly distributed numbers. Next, we observe that we found the modulus, if for any pair of $r_i,r_j$, $\gcd(r_i,r_j)=1$ holds, i.e. if any pair is co-prime. As we modeled the integers randomly, this can be said with probability $6/\pi^2$ and obviously a pair is not co-prime with probability $1-6/\pi^2$. Now the question becomes, "what is the probability, that all pairs are not co-prime?" which is $(1-6/\pi^2)^{\frac{k(k-1)}{2}}$. From this we can obviously draw the conclusion that there's at least one co-prime pair among the $r_i$s with the following probability, which is also the probability that our guess $N'$ for $N$ is correct:

$$\Pr[N'=N]=1-(1-6/\pi^2)^{\frac{k(k-1)}{2}}$$

My intuition tells me that I can't take the number of pairs as exponent, because there are some cases I consider "unique" here that actually aren't.

$\endgroup$
2
$\begingroup$

You're treating this as ${k \choose 2} = k(k-1)/2$ independent events. But, they're not independent. Therefore, you can't just multiply the probabilities like that.

For instance, if we're told that $\gcd(r_1,r_2)=2$ and $\gcd(r_2,r_3)=2$, then the (conditional) probability of $\gcd(r_1,r_3)=1$ is not $6/\pi^2$; it is $0$.

$\endgroup$

Your Answer

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

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